信鸽原则的不应有地位(1991)

2020-07-05 04:47:05

就在我被介绍给鸽子洞原理的那一刻,我明白了它有一些非常特别的地方,因为我从他那里学到它的英国人用它的德国名字告诉我它的德语名称&das Schubfach prinzip";。后来我了解到,在其他语言中,它也有一个特殊的名字。事实上,它被某种神秘所包围,因为使用它的证明通常被认为是一些特别的东西,一些特别的巧妙的东西。例如,罗斯·洪斯伯格(Ross Honsberger)用鸽子原理的又一次胜利来结束他的一个例子,很好地反映了这种敬畏之情。(早些时候,他称它为组合学的基本工具。)。

然而,我的感觉是,这种神秘性和当我们看到鸽子原理被成功应用时的惊喜,与该原理通常表述的笨拙密切相关:它们包含大量误导性噪音,过于具体,并掩盖了该原理的算术本质。我不是写一个平均的公式,而是逐字引用文献中的一个典型的公式:

如果n个以上的对象被分配到一组n个隔间中,则某个隔间必须容纳多于一个对象";。

(人们经常会遇到更具体的n+1&34;,而不是以上的n#34;以上。)。我们将把(0)与备选方案进行比较。

对于一个非空的有限实数包,最大值至少是平均值(最小值至多是平均值)。

比较(1)和(0),我们首先观察到,分发和接收都消失了,这是正确的,因为它们只是噪音:当不涉及分发和接收过程时,例如,当我们希望根据一个月比一个星期长的事实得出结论,一个月中某个工作日出现不止一次时,鸽子洞原理同样适用。

我们观察到的第二件事是,物品和隔间消失了。这是一个巨大的进步,因为它省去了我们在所有那些(由于视觉或语言原因)物体和隔间的比喻不太合适的情况下进行痛苦识别的不必要的麻烦。例如,在前面的示例中,我们不应该谈论包含若干个星期二的一个月,而应该谈论包含若干天-月(=对象)的星期二(=隔间)。所有关于物体和隔间的比喻都是令人头疼的。

这个比喻的另一个令人遗憾的后果是它带来了一种误导性的可视化。公式(0)的形式是隐含的;相反的状态等价

如果n个隔间中的每个隔间最多包含一个对象,则它们一起最多包含n个对象";。

公式(0)让人联想到拥挤的隔间-2只或更多的鸽子挤在一个有1个鸽子的洞里-而公式(2)更让人联想到空间不足的情况。图片之间的差异掩盖了(0)和(2)等价的事实。

备注:人们区分x≤y和y≥x的情况并不少见-不是在意义上,而是在rôle中。前者表示(以y表示)x的上界,后者表示(以x表示)y的下界。我建议不要试图做出这样的区分:

它们的表述完全相同,不需要像(0)和(2)那样引起不同的内涵。(备注结束。)。

最后,传统的鸽子洞原理远没有它应有的那样普遍:用平均值和最大值来表示,(0)收益率。

这就是为什么真正比(0)强的(1)被称为广义鸽子洞原理。

作为广义鸽子洞原理派上用场的一个例子,我们现在来考虑一下德国足球彩票的问题。

类型";结果";的变量有3个可能值中的1个;类型";列";的变量由类型";结果";的13个变量组成。在下文中,伪数c和d的范围是类型";列";,而W是类型";列";的一组常量。我们被要求构造一个尽可能小的集合W,使得

(a d::(e c:c∈W:(n i:0≤i<;13:d.i=c.i)≥5)。

换句话说:W应该是这样一组列,无论我们为d选择哪一列,W都包含至少5个位置与d重合的列c。

集合W包含至少3列,因为在W中最多有2列,可以选择d,使得它与W中的列不在任何位置重合,但3列就足够了。设x,y,z是W中的三列;我们可以选择它们,使得对于范围0≤i<;13中的任何i。

是可能结果值的三倍。通过这样的选择,每个值d.i与三个{x,y,z}中的一个重合;3列中的13个重合平均产生每列4个⅓重合,因此至少1列在至少5个位置与d重合。这样,德国足球乐透的问题就解决了。

包含该示例有两个原因。首先,这是一个例子,传统的(0)是不够的,真正需要更强的(1)。其次,说明了使用鸽子洞原理经常引起惊讶的算术原因:问题陈述中的三个常数3、13和5幸运地满足了5是至少为13/3的最小整数的神奇关系。正是这个算术意外使德国足球彩票问题变得微不足道。用6代替5,我们得到了一个完全不同的问题,这个问题更难解决!用另一种方式表述同样的观察结果是,如果你能用一个像鸽子洞原理这样简单的论点逃脱惩罚,那么你就是幸运的。