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

我们知道，存在这样一种全体正整数的红蓝二着色方案，其中没有任何无穷长的等差数列满足数列中的所有数颜色都一样。它的构造非常暴力。有趣的是，把上述命题中的“无穷长”换成“任意长”，命题就不见得仍然正确了。事实上，Van der Waerden定理(http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem)告诉我们，对于任意大的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更大的方向看去时，不禁对数字表示深深的膜拜。