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