抽屉原理应用

luyuanhong

抽屉原理应用

原创 为中华崛起而写码 海洋算法竞赛 2024 年 06 月 30 日 23:03 江苏

“不出户，知天下；不窥牖，见天道。”

了解大道的人不出门户一步，就能推知天下道理；不向窗外望一望，就能够了解大自然运行的规律。

本文讲述了抽屉原理的应用。

题  某赛事共举行 44 场比赛，每场比赛有 7 名优胜者，且任意两场比赛中恰有一个相同的优胜者，问是否存在某人为所有各场比赛的优胜者？







题  证明：在 10 个互不相同的（十进制）两位数组合的集合中，存在两个不相交的子集，这两个子集的元素之和是相等的。

我们想要得到的元素之和相同的两个子集，所以子集作为物品。

而得到的和就是抽屉。

首先我们先看看那些和，可能的最小的和是 10 ，可能的最大的和是 99+98+97+…+90=945 。

所以一共有 936 种不同的和。

一共有 2^10-1=1023 个子集，1023＞936 ，所以在 1023 个子集中，一定有两个子集的元素之和是相等的。

但是，我们依然没有证明，这两个子集是不相交的。如果有相交的，





题  是否存在正整数 n＜10^9 ，使得 n 能用超过 1000 种不同的方法，表示为三个互不相同的正整数的平方和？



题  49 个学生，解 3 个问题，每个题得分是 0 到 7 分的整数，求证：存在两个学生 A 和 B ，对每个问题，A 的得分都不少于 B 。

如果有两个学生的第 1，2 题的得分相同，设其中学生 A 的第三题的得分不低于另一位学生 B ,于是，对每一个问题，A 的得分都不低于 B ，结论成立。







我们发现在 L 型集合中，分数具有线序关系。

所以至少一个人的前两个成绩不低于另外一个人前两个成绩。

一些问题的求解需要多次运用抽屉原理，每次使用抽屉原理，都能得到一些信息。

题  10×10 的国际象棋棋盘上放置 41 个车，证明一定存在 5 个互不攻击的车。



若觉某问题或可借抽屉之理解答，则宜诚心尝试。寻得小球与抽屉，问题可速解矣。

若抽屉原理无解于问题，请勿轻言弃也。若用之而得结论，可为下一步提供线索，则再施抽屉原理。切记，已得之信息，务必留存。

海洋算法竞赛