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