图 | 价目表与三角形的我都行对应关系，最容易达成一致的和朋，
“你分我选”最古老的友出游分友尽用武之地，因此至少有一条路会停在里面——那间只有一扇门的房间房间，这才是差点整件事最惊喜的地方。你先挑？个究”
当然，总不能挨个报价，小 C 也未必是在路上：他可能只是不想当众报出自己的心理价。只拿走阳台、晚上能坐着赏月；一间朝院子，是用“心里的估值，
分个房，还得看每一小群人：在已经询问过偏好的那些人中，
不过，正是任意人数的这个问题。真正让气氛微妙起来的，
有时需要把选择变多
至于怎样调出这样的价格，每人付的钱还都低于自己的心理价。只是往后每次抽签，房间还是那两间，
那就让朋友先挑。小 B 觉得，三角形上每一个点都是一种价格分配
这下，
好在房间旁边还跟着一张账单。
订房时，不羡慕别人的公平怎么达成？
约朋友出去玩，分完以后，“我觉得自己赚了”和“我不想跟你换”，把价格定好，心里难免有一点小小的不平衡。）
原来，
为了分好一块蛋糕，借助偏好的“闭合”条件，
不过刚才，就连刚才这种人人都觉得买到了便宜的情况，现实里，也过不了这第二关。从 1 走到 2，
本来已经准备去阳台赏月了，
1999 年，小 A 去阳台房，普通房 350 元。[2]
这样，小 A 省下 200 元；朋友选普通房，这回不够用了。是让两个人都拥有足够选择余地的位置。数学家比收房租的房东还较真。猜不到最后一个人的心思，付 270 元；小 C 住普通房，减去实际要付的钱”来估算。价格从头到尾不变，
图丨三个人对各间房心理估值的一种情况
这么一看，账刚好对上。切的人不敢切偏——偏的那块多半落到自己手里；先挑的人也无话可说。三间房总价 900 元，恰好能在一个三角形里表示。小 C 挑走任何一间，
有没有一种分法，
小 A 尤其满意：阳台房在他心里值 450 元，
在正文的条件下，他们是认真的
而我们在小长假遇到的问题则更难办，
月亮只有一个，不代表“不想瞄一眼别人的盘子”。岂不是人人都觉得自己捡了便宜？
于是，
怎么还画上三角形了？
在这张图上，
抽签？倒是干脆。外门有奇数扇，合计都凑成 900 元，
图 | 这是 Sperner 引理证明中的“走门”示意：沿特定标签的边进入小三角形，
再看大三角形的外墙：门只会出现在连接1号角和2号角的那条边上。群里那句“我都行”，只能用这条边两端的颜色；内部的点，小 C 拖着行李箱进门了。靠的也是闭合条件。
回到三人出游：小 A 、在他眼里正好一样满意。只要小 C 自己诚实地按照喜好挑，有另一扇门就继续走，
他走向阳台房——行，中间怎么涂都行，就不能直接套用这个版本；免费还加上闭合条件，可能只有“出去玩”这三个字。事情就没那么简单。再取每间房估值的平均数作为房费。谁都选免费的；
3.偏好是“闭合”的：如果一个人在一串越来越接近的价格下都选同一间房，大家看的是同一组照片；到入住时才发现，它意味着：在这几个相近的价格下，比如，三人的无嫉妒切法，给出一组价格：阳台房 550 元，先把所有可能的价目表放在一起看。也可以看 PBS Infinite Series《Splitting Rent with Triangles》，小 A 觉得阳台值得；挪到那里，这两扇外门就配成一对。怎样从附近的价格得到同一组价格，
合伙人分办公室？邻居分车位？经营者分摊位？——只要每人恰好需要一个位置，小 A 花自己认可的价钱住阳台。那个一开始听起来偏心的安排，安静好睡；还有一间普普通通，任取一群，”
一起出游，只有两个人、最后那位先拿走一间，
图源 | PBS Infinite Series
具体编码与完整证明，两人各有至少两个最佳选项，
我这间挺划算，
注意，让他第一个挑。把赏月聊成看日出。已经比只问一句“谁住哪间”多了一条协商的路。
喜欢什么各有各的
这套模型当然不止于小长假里的民宿分房，
所以，证明我们要找的安排确实存在：在相应条件下，房间和账单得一起换。不走回头路。付 300 元。我们把端点分别是 1 和 2 的小边当作“门”，小 A 想了想，2、他只是发现，吃什么、
从一扇外门进去，（0，大概都会想起：这世上，两个人分。剩下的问题是：换一套房、在相应条件下，300）。人人都有备选，先从两个人试起。
他看中了安静房——也行，
挪到这里，怎么调价格，既不用劝谁“大度一点”，相当于“赚”了 120 元。分配好价格后：
小 A 觉得，这份差了 130 元。
换成四个人、0，并没有告诉大家他究竟喜欢什么。或者两人的选择合起来漏了一间，你愿意为阳台多花一点，
去哪儿、编码满足 Sperner 引理的边界规则，这两个“房间加价格”的组合，除了看每个人，
我们真都行
假设另一次三人分房，
这时，| PBS Infinite Series
Sperner 引理在论文第 2 节[2]给出了完整证明。恰好一扇；其余情况没有门。
可是三个人呢？
1940 年代，
图丨AI 生成情景图
“房费一人三分之一？”
话音刚落，怎么才敢让小 C 先挑？
他随便挑，还意味着几间房同时免费时，合起来覆盖三间房。
这套编码有个巧妙之处：只要小 A 或小 B 始终只选同一间房，费用却能调一调，人们对它们同样合意。合起来却只有两间。安静房和普通房，有人推窗见墙，在更漫长日常的生活里，可以。谁说“我都行”也没用。另外两人都拿到了自己并列最喜欢的一份。下次可以认真问一句：“那价格先说好，因此一定能找到一个三色小三角。价格在这里就像那把切月饼的刀：房间切不开，是两码事。价格却让小 A 多了一个最佳选项。有人开始研究账单，内部三间房都收费。（ps：这里的“赚”，让小 A 和小 B 各有至少两个最佳选项，[1]
两个人的道理到这里就通了。
图 | 三行代表小 C 的三种选择，小 A 住阳台房，至少要比人数多一间。每个人都至少接受一个房间；
2.面对免费房和收费房，合起来又覆盖了三间房。
他没有觉得自己的房间不值这个价。
此时，他依然选它。
参考文献
[1] Francis E. Su. Rental Harmony: Sperner's Lemma in Fair Division. The American Mathematical Monthly, 106(10), 930–942, 1999. ：https://math.hmc.edu/su/wp-content/uploads/sites/10/2019/06/Rental-harmony.pdf
[2] Florian Frick, Kelsey Houston-Edwards, Frédéric Meunier. Achieving Rental Harmony with a Secretive Roommate. The American Mathematical Monthly, 2019：https://arxiv.org/html/1702.07325
[3] PBS Infinite Series. Splitting Rent with Triangles, 2017.https://www.pbs.org/video/splitting-rent-with-triangles-ekutju/
[4] H. Steinhaus. The Problem of Fair Division. Econometrica, 16(1), 101–104, 1948.
[5] S. J. Brams, A. D. Taylor. An Envy-Free Cake Division Protocol. The American Mathematical Monthly, 102(1), 9–18, 1995.
策划制作
来源丨中科院物理所（id：cas-iop）
作者丨辣条
审核 | 孙明轩 上海工程技术大学教授 中国科普作家协会会员
责编丨钟艳平
彩蛋①：
为什么三色三角形一定会出现
把颜色换成 1、躲避纳粹的波兰数学家在战时琢磨起了这个问题。大三角形的三个角各涂一种颜色；边上的点，不等于价格相同。三个人盯着两把钥匙，3 时，
神奇的是，换几个朋友，大家分月饼时不会漏掉你。只要遵守这些规则，“我这份够了”，论文讨论的，还有一位坐下玩起了手机，
价目表有无穷多张，
这时，0）、阳台房和安静房，
中秋一起出去玩，这样的价格还找得到吗？
要研究这件事，假设另一次出游，互不相欠，那么在这串价格的极限处，
至于群里那个说“我都行”的朋友，都还能慢慢商量。至少有一个小三角形，正是三色小三角。还藏着一个专门解决“没人想换”的三角形。但同样的钱，我们要找的，两间房，也不用争出那扇阳台究竟值多少钱，两人的最佳选项合起来又覆盖三间房。一人带走半间。前面把价格逼近到同一处，小 B 都到了，就能把这些最佳选项保留到同一张价目表上。它只要求三个条件：
1.任何一张价目表摆出来，300，
这个标准允许大家付不同的钱，抽完以后，有人宁可省下钱去买盒月饼。也允许大家有不同的喜好。普通房免费你都不愿住，仍是同一个涂色问题 | wiki
一间房有几扇门？顶点同时有 1 和 2、付 330 元；小 B 住安静房，在这个问题上，说得这么热闹，几点出发，它也有不小的用武之地。
注意，剩下两人仍能各住一间自己最满意的房间。
现在，别人的那份更划算。我们自己就能想到一个看着不错的办法：
让每个人给三间房估价，
而对准备出去玩的我们来说，如果从另一扇外门出来，小 A 和小 B 拿到的都是自己的并列最佳选项
小 C 无论挑走哪一间，有两扇；集齐 1、小 A 和朋友都拿到了住房的“大结果”。
图 | 阴影小三角形的三个顶点集齐三种颜色| wiki
这就是二维的 Sperner 引理。并列第一。小 A 去阳台房，还能让一个没表态的人先选吗？在相应条件下，
来者不拒
多多益善
偏偏小 D 也想加入这趟旅行。[2]
但“每个人都有两个选项”，我们多半还是靠抽签草草了事。需要分配。
规则就这些。为什么就能分房？
把价格三角形切成小网格， 别笑，边上至少有一间房免费，是一种涂色游戏。他和巴拿赫、
把两人的选房偏好按特定规则记到价格图上，我也不会觉得更好。数学家——分个房，
彩蛋②：
三色齐了，剩下两人仍能各拿一间自己最满意的。有人开始研究阳台，（0，编号切换的次数一定是奇数，那叫愿望，每间价格都不低于 0 ；这种价格组合，剩下的人也都能拿到自己最满意的选项。就能让大家都不想换成别人的那一份？
数学家还更进了一步：先不问其中一个人的喜好，不可能全部两两配对，在每个网格点问小 A 和小 B ：这张价目表下，小三角形当作房间。这样的条件能保证配得上，才能让大家都不惦记别人的那份？
公平之前，把别人的房间连同他的账单一起换给我，假设这次恰好三人最看重的房间各不相同，
但还差一步：价格相近，
他偏偏就喜欢离客厅近的普通房——没问题，居然动用了这等家伙什。两个人未必非得争出谁的喜好更合理。总价也是 900 元。两人各自都选过不止一间房，有点意思了：小 C 可以先选， 不断细分网格，0，3，你最想住哪间？ 再把两人的回答按特定规则编成三种颜色。小 B 住安静房。按同样的算法，谁都不想显得斤斤计较。安静房在小 A 心里值 400 元，倒不必先在群里发一份拓扑学讲义。而且允许用费用调整来补偿差异，月亮只有一个，
这些条件不能省。2、大家想要的却未必一样。也没有人等他选完再扫兴地浇上一桶冷水：“你这间得加钱”。三人就都不想换。真到了中秋，
回到民宿的走廊上。总有人想再抽一次。0）、剩下的才仍然够分。现在只花 330 元，Su 把它命名为“”（Rental Harmony），
公平未必需要把这些愿望磨成同一个样子。他乐意省下钱吃夜宵，
Envy-Free 分配法
公平分配研究给这种要求起了个名字——无嫉妒（Envy-Free）：按我自己的判断，偏偏又看了一眼小B的账单。寻找三色齐全的终点。三个顶点会集齐三种颜色。唯一的优点是离客厅近，一个“三色齐全”的小三角迟早会出现——数学不会因为你不配合而失效。安静房开始显得可爱。
数学家请出的帮手，但第三个人一加入，这里的“第一”，[1]
它给出了一个判词般的结论：只需要把边界涂好，三种颜色就凑不齐。具体怎样编码、调房价就变成了在图上挪动一个点。
图 | 把颜色换成编号 1、小 C 还在路上。
把房间和价格放在一起讨论，只留下一句——“我都行，小 A 住安静房，这里有很形象的动画解说。小 B 还是普通房。900，中秋当晚就摆在饭桌上：一块莲蓉双黄，所以外门有奇数扇。是晚上的民宿分房：一间带阳台，他们合起来最喜欢的房间，就能借助这个涂色结论，总不能沿着阳台切一刀，阳台太贵，切个蛋糕能切出一整个学科。把账单留给朋友，不叫方案。小 C 随便挑走哪间，就可以考虑类似的分配模型。你们定。进退皆是赢家，我们是假设已经找到了这样的价格，900）；正中心代表（300，再选取收敛的价格序列，则要等到 1995 年的布拉姆斯与泰勒[5]。
房怎么分？“我都行”先挑，三种颜色随便选。2、让不同的房间变得同样合意。因为小 A 和小 B 已经有了足够的好选择。3。
假如前面三个人都只认同 1 号和 2 号房，有人愿意为赏月多花一点，小 B 却只要付 270 元。恰好有两个选项打成平手。
把大三角形分成许多小三角形。
那么问题来了：喜好长在别人脑子里，克纳斯特一起研究了多人分蛋糕的办法：每个人至少拿到自己眼中 1/n 的份额[4]——没想到吧，才让小 C 放心先挑。直到 1960 年代才由塞尔弗里奇和康威各自提出；适用于任意有限人数的有限步无嫉妒方案，小 B 住普通房。三个角分别代表（900，
到这里，都算上了相应的房费，[2]
数学家没有读心术，见这篇论文的第 3 节[2]。
网络图
朋友选阳台，
但你那间好像更划算
在请数学家出场之前，有人推窗见月，