经典证明:任何正整数着色方案中都含任意长的单色等差数列

    我们知道,存在这样一种全体正整数的红蓝二着色方案,其中没有任何无穷长的等差数列满足数列中的所有数颜色都一样。它的构造非常暴力。有趣的是,把上述命题中的“无穷长”换成“任意长”,命题就不见得仍然正确了。事实上,Van der Waerden定理告诉我们,对于任意大的k,总存在一个N,使得对从1到N的正整数进行红蓝二染色后,里面总存在一个单色的长为k的等差数列。当命题扩展到任意c着色时,该命题竟然也都成立。证明主要用了鸽笼原理和数学归纳法,证明过程直观而又有趣。

    我们首先来证明k=3的情况:存在某个N使得对N个连续自然数进行二染色后里面总有长为3的单色等差数列。我们把全体正整数5个5个地分组,1..5为第一组,6..10为第二组,以此类推。每一组里总共有2^5种不同的染色方案,因此在前2^5+1组里面必然有两个组的染色一模一样,比方说第7组和第23组吧。把第7组里的数记作A_1, A_2, …, A_5,由鸽笼原理,A_1, A_2, A_3里面一定存在两个颜色相同的数,不妨设A_1和A_3都是红色吧。考虑A_5的颜色:如果它是红色,我们的问题就解决了,A_1, A_3, A_5已经是一个长度为3的等差数列。下面考虑A_5是蓝色的情况。别忘了第7组和第23组的染色完全相同,因此在第23组中,B_1, B_3也是红色,B_5也是蓝色。下面我们来考虑全体正整数的第39组(7,23,39是等差数列),我们把它记为C_1, C_2, …, C_5。考虑C_5的颜色:如果它是红色,那A_1, B_3, C_5就是一个全为红色的等差数列,否则A_5, B_5, C_5就是一个全为蓝色的等差数列。显然,上述证明中的“最坏情况”就是,第1组和第33组的染色相同,且第1组的第1个数和第33组的第3个数是红色,则下一个数最远可以是第65组的第5个数,即全体正整数的第325个数。换句话说,k=3时N=325即满足条件。


    有意思的是,上述证明不但对“二着色”成立,对所有“c着色”上述证明都适用。比方说,对于c=3时,取n=7(2·3^7 + 1),把全体正整数n个n个分为大组,在头3^n+1组中必然存在两个染色一样的组,记作大组A和大组B。把这两个大组里的数分别都7个7个地分成2·3^7 + 1个小组,在头3^7+1组中,必然有两个小组的染色方案一模一样,比如小组a和小组b。

    在每一个小组的前4个数中,必然有2个数的颜色是相同的,比如说第1个数和第4个数是红色吧。那这个小组里面的第7个数要么是红色(问题已解决),要么是另一种颜色(比如蓝色)。那么,与前两个小组构成等差序列的第三个小组(记作小组c,由于一个大组中有2·3^7+1个小组,因此小组c一定还在该大组中)中的第7个数要么是红色(问题已解决),要么是蓝色(问题已解决),要么是剩下的那种颜色(比如黄色)。那么,与两个大组构成等差序列的第三个大组(记作大组C)中,对于相应的小组c位置上的第7个数的颜色就没有任何选择了,它或者和每个大组的那个染黄色的数成等差数列,或者和大组A的小组a的蓝色数、大组B的小组b的蓝色数构成等差数列,或者最牛B的,和大组A的小组a的第1个红色数、大组B的小组b的第2个红色数构成等差数列。

    类似地,对于更大的颜色数c,我们都可以归纳证明,只不过递归分组的层数更多,底数也相应的变大。因此,我们解决了k=3且c任意大的情形。

 
    真正牛B的是对k的归纳证明。我们下面尝试证明k=4、c=2的情况。由于当k=3时每325个数里面必然有一个等差数列,因此我们按每487个数一组进行分组。这样可以保证每一组里面的前325个数中总存在长为3的单色等差数列,并且该数列的第4个数也在该组内。注意,一个487元组共有2^487种染色方案,如果我们把它们看作2^487种不同的“广义颜色”,由k=3、c=2^487的情况知,必然存在3个组,这3个组的编号形成等差数列,并且它们的染色方案完全相同。于是我们考虑每一组中前325个数所形成的长为3的等差数列,并考虑该数列中第4个数的颜色:如果颜色相同,问题解决,否则便考察顺推下去的第4个组的相应位置上的数的颜色,它将别无选择。
    类似地情况,我们可以归纳出任意大的k和任意大的c的情形。可想而知(或者说难以想象),用这种做法得出的N是何等的巨大,它将很快超出整个宇宙中任何具有实际意义的数字,其大小已经不能用通常的方式来记录了。不过,再大的N也是有限的。这个证明牛就牛在他的气势之宏大,以至于很多人都不敢想……当我读到2^487种颜色时,视野一瞬间广大得难以描述;并且当我向着k更大的方向看去时,不禁对数字表示深深的膜拜。

10 条评论

发表评论

  ×  6  =  30