数学|鸽子洞原理

假设一群20只鸽子飞进一组19个鸽子洞栖息。因为有20只鸽子，但只有19个鸽子洞，这19个鸽子洞中至少有一个必须至少有两只鸽子在里面。要了解为什么这是真的，请注意，如果每个鸽子洞最多有一只鸽子，那么每个洞最多可以容纳19只鸽子。这说明了一个被称为鸽子洞原理的一般原理，即如果鸽子洞比鸽子洞多，那么必须至少有一个鸽子洞，里面至少有两只鸽子。

定理——

（一） 如果“A”是每个洞的平均鸽子数量，其中A不是整数，那么

• 至少有一个鸽子洞包含 ceil[A] （大于或等于A的最小整数）鸽子
• 剩下的鸽子洞最多只能容纳 楼层[A] （小于或等于A的最大整数）鸽子

或

二） 我们可以说，如果n+1个对象被放入n个框中，那么至少一个框包含两个或更多对象。 原理的抽象表述：设X和Y为有限集，设 成为一种功能。

• 如果X的元素比Y多，那么f不是一对一的。
• 如果X和Y的元素数相同，且f为on，则f为一对一。
• 如果X和Y有相同数量的元素，而f是一对一的，那么f是对的。

鸽子洞原理是数学中最简单但最有用的思想之一。我们将看到更多证明这个定理的应用。

• 示例–1： 如果（Kn+1）只鸽子被关在n个鸽子洞里，其中K是一个正整数，那么每个鸽子洞的平均鸽子数量是多少？

  解决方案： 每个洞的平均鸽子数量=（Kn+1）/n =K+1/n 因此，至少有一个鸽子洞将容纳至少（K+1）只鸽子，即ceil[K+1/n]，剩余的鸽子洞将容纳最多K只，即地板[K+1/n]只鸽子。 i、 例如，确保至少一个鸽洞容纳（K+1）只鸽子所需的最小鸽子数量为（Kn+1）。

• 示例2： 一个袋子里有10个红色弹珠、10个白色弹珠和10个蓝色弹珠。你必须从袋子中随机选择的弹珠的最小数量是多少，以确保我们得到4个相同颜色的弹珠？

  解决方案： 应用鸽子洞原理。 颜色数量（鸽子洞）n=3 大理石（鸽子）数量K+1=4 因此，所需的最小大理石数量=Kn+1 通过简化我们得到Kn+1=10。 验证：ceil[平均值]为[Kn+1/n]=4 [Kn+1/3]=4 Kn+1=10 i、 例如，3红色+3白色+3蓝色+1（红色或白色或蓝色）=10

鸽子洞原理强形式——

定理： 让q _1. ，q _2. , . . . , Q _N 应该是正整数。 如果q _1. +q _2. + . . . + Q _N –n+1个对象放入n个框中，则第一个框中的任一个至少包含q _1. 对象，或第二个框至少包含q _2. 物体。，第n个框至少包含q _N 物体。 这个定理的应用更重要，所以让我们看看我们如何在问题解决中应用这个定理。

• 示例–1： 在计算机科学系，学生俱乐部可以由第一年的10名成员或第二年的8名成员或第三年的6名成员或最后一年的4名成员组成。为了确保学生俱乐部的成立，我们必须从系里随机选择的最少学生人数是多少？

  解决方案： 我们可以直接从上面的公式， q _1. =10，q _2. =8，q _3. =6，q _4. =4，n=4 因此，确保成立系俱乐部所需的最低学生人数为 10 + 8 + 6 + 4 – 4 + 1 = 25

• 示例2： 一个盒子包含6个红色、8个绿色、10个蓝色、12个黄色和15个白色的球。我们必须从盒子中随机选择的最少球数是多少，以确保我们得到9个相同颜色的球？

  解决方案： 在这方面，我们不能盲目地应用鸽子原理。首先，我们将看到如果我们直接应用上述公式会发生什么。 从上面的公式我们得到了答案47，因为6+8+10+12+15-5+1=47 但这并不正确。为了得到正确的答案，我们需要只包括蓝色、黄色和白色的球，因为红色和绿色的球小于9。但我们是随机挑选的，所以我们在应用鸽子原理后加入。 i、 例如，9蓝+9黄+9白-3+1=25 因为我们是随机挑选的，所以我们可以在上述25个球之前得到所有红色和绿色的球。因此，我们加上6个红色+8个绿色+25=39 我们可以得出结论，为了随机挑选9个相同颜色的球，必须从一个盒子里挑选39个球。

参考资料： http://www2.fiit.stuba.sk/~kvasnicka/Mathematics%20for%20Informatics/Rosen_Discrete_Mathematics_和_Its_Applications_第七版。pdf 本文由 赛基兰·古德·伯拉 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。