稳定匹配证明疑问解析：为何男孩无法均将女孩A列为最末？

我来帮你把这部分证明的逻辑拆解清楚——你困惑的核心是「为什么不能所有男孩都把同一个女孩A评为最差」，以及证明里从这个假设推导出的「每个女孩都被至少n-1个男孩评为最差」的矛盾点，对吧？

先理清楚证明的核心思路：反证法 #

这个证明是用反证法推进的：我们先假设一个和结论相反的情况——「所有男孩都把女孩A排在自己偏好列表的最后一位」，然后推导一个不可能成立的矛盾结论，从而推翻这个假设，证明原结论正确。

第一步：为什么假设“所有男孩都把A评为最差”会推出“每个女孩都被至少n-1个男孩评为最差”？ #

假设所有男孩都把A当作最差选择，现在我们随便挑一个其他女孩B（B≠A）来分析：

• 首先，稳定匹配的定义要求：每个女孩都必须和某个男孩配对。假设B最终和男孩m配对。
• 对于剩下的n-1个男孩来说，他们的最差选择都是A，所以他们肯定都觉得B比A好（毕竟A是垫底的）。那这n-1个男孩会不会都想和B配对？
• 如果其中有两个男孩（比如m1和m2）都觉得B比自己当前的配对对象好，那麻烦就来了：假设B觉得m1比自己的现任m好，那m1和B就构成了不稳定对——m1想离开自己的配对对象，B也想离开m，这直接违反了稳定匹配的定义（稳定匹配里不能有这样的不稳定对）。
• 要避免这种不稳定对的出现，对于女孩B来说，最多只能有1个男孩不把她当作最差选择（也就是这个男孩是B的最终配对对象）。剩下的n-1个男孩必须都把B当作最差选择——不然就会出现多个男孩想和B配对，进而产生不稳定对。
• 把这个逻辑推广到所有女孩身上，就得出了「每个女孩都被至少n-1个男孩评为最差」的结论。

第二步：为什么这个推导出来的结论是矛盾的？ #

现在我们算一笔简单的“名额账”：

• 每个男孩只能选1个“最差女孩”，所以n个男孩总共只有n个最差名额。
• 如果每个女孩都被至少n-1个男孩评为最差，那n个女孩总共需要的最差名额至少是 n*(n-1)。

你看，当n≥2时，n*(n-1) 肯定大于n（比如n=3时，32=6>3；n=2时，21=2=n，但这时候另一个女孩B会被0个男孩评为最差，和推导的结论矛盾）。这就出现了一个不可能的情况：需要的名额远超实际存在的名额，或者像n=2时，推导的结论和实际情况直接冲突。

总结一下 #

假设“所有男孩都把A评为最差”会推导出一个在数量上不可能成立的结论，所以这个假设必然是错的——也就是说，不可能所有男孩都把同一个女孩评为最差。

内容的提问来源于stack exchange，提问作者shiva