你打开一本英文书, 随机挑选一些单词. 你需要阅读多少个单词才能确保其中至少有两个单词是以相同的字母开头的?
如果你只读 2 个单词, 它们很容易以不同的字母开头, 比如 A 和 B. 添加一个额外的单词并没有多大帮助, 因为它可能以 C 开头. 虽然不太可能, 但26个单词, 也有可能以从 A 到 Z, 不同的字母开头. 然而, 如果再添加 1个单词, 那么它的第一个字母一定已经被使用过了, 因为英语字母表中包含的字母少于 27个.
这是一个看似显而易见但非常强大的定理:
定理 1 ( 抽屉原理 )
如果将
在本例中, 我们将 27 个“物品”(单词)放入 26 个“容器”(字母)中, 因此必须为一个字母分配两个单词.
我们再看一个数论中的例子. 让我们从 1 到 100 之间随机选择 51 个不同的整数. 抽屉原理告诉我们至少有两个整数是连续的. 为什么?
假设我们从 1 开始, 将连续的整数配对, 这样就有 50 个集合 .
现在你能利用抽屉原理挑战下面这个问题吗?