史诗般壮观的数学证明

你认为，是否有可能把全体正整数染成红蓝二色，使得不存在无穷长的等差数列，满足数列中的所有数都是一种颜色？

事实上，满足题意的染色方案是存在的。例如，我们可以从数字1开始，把正整数染成一段红一段蓝，使得每一段的长度都是其前一段的两倍。也就是说，我们把 1染成红色，2和3染成蓝色，4到7染成红色，8到15染成蓝色，依此类推，单色区间的长度成倍地增加。可以证明，如此染色后，一定不存在无穷长的单色等差数列。这是因为，假设某个等差数列的公差为d，那么当单色区间的长度大于公差d 时，等差数列将会一截一截地落在不同的染色区间中，从而拥有不同的颜色。

有趣的是，把上述命题中的“无穷长”换成“任意长”，命题就不见得仍然正确了。1927年，荷兰数学家范·德·瓦尔登（VanderWaerden）证明了这么一个事实：对于任意大的正整数k，总存在正整数N，使得对从 1到N的正整数进行红蓝二染色后，不管你是怎么染色的，里面总存在一个单色的长度为k的等差数列。当命题从两种颜色扩展到任意多种颜色时，该命题竟然也都成立。这个定理就叫做范德瓦尔登定理。下面，让我们来看看范德瓦尔登定理的证明过程。到了整个证明的最后一步，你一定会被震撼得说不出话来。

我们首先来证明k＝3的情况：存在某个N使得对N个连续自然数进行二染色后，里面总存在长为3的单色等差数列。我们把全体正整数5个5个地分组，1到5为第一组，6到 10为第二组，以此类推。每一组里总共有2⁵种不同的染色方案，因此在前2⁵﹢1组里面必然有两个组的染色一模一样，比方说第7组和第23组吧。把第7组里的数分别记作A₁，A₂，…，A₅，由鸽笼原理，A₁、A₂、A₃里面一定存在两个颜色相同的数，不妨假设A₁和A₃都是红色吧。考虑A₅的颜色：如果它是红色，我们的问题就解决了，A₁，A₃，A₅已经是一个长度为3的等差数列。下面考虑A₅是蓝色的情况。别忘了第7组和第23组的染色完全相同，因此如果把第23组里的数分别记作B₁，B₂，…，B₅，那么B₁和B₃也是红色，B₅也是蓝色。下面我们来考虑全体正整数的第39组（注意到7，23，39是等差数列），我们把它里面的5个数分别记作C₁，C₂，…，C₅。考虑C₅的颜色：如果它是红色，那A₁，B₃，C₅就是一个全为红色的等差数列，否则A₅，B₅，C₅就是一个全为蓝色的等差数列。显然，上述证明中的“最坏情况”就是，第 1组和第 33组的染色相同，且第1组的第1个数和第33组的第3个数是红色的，则下一个数最远可以是第65组的第5个数，即全体正整数的第325个数。换句话说，k＝3时N ＝325即满足条件。（这不一定是最小的N，但确实是一个满足要求的N。）

有意思的是，对任意的颜色数c，上述证明都是适用的。比方说，当c=3时，取n＝7×（2×3⁷﹢1），把全体正整数n个n个分为大组，在头3ⁿ﹢1组中必然存在两个染色一样的组，不妨把它们记作大组A和大组B。把这两个大组里的数分别都7个7个地分成2×3⁷﹢1个小组，在头3⁷﹢1组中，必然有两个小组的染色方案一模一样，比如小组a和小组b。

在每一个小组的前4个数中，必然有2个数的颜色是相同的，假设第1个数和第4个数是红色。那这个小组里面的第7个数要么是红色（问题已解决），要么是另一种颜色（比如蓝色）。将与前两个小组构成等差序列的第三个小组记作小组c，由于一个大组中有2×3⁷﹢1个小组，因此小组c一定还在该大组中。小组c中的第7个数要么是红色（问题已解决），要么是蓝色（问题已解决），要么是剩下的那种颜色（比如黄色）。那么，与两个大组构成等差序列的第三个大组（记作大组 C）中，对于相应的小组c位置上的第7个数（图1中标记星号的位置）的颜色就没有任何选择了，它或者和每个大组的那个染黄色的数成等差数列，或者和大组A中的小组a的蓝色数、大组B中的小组b的蓝色数构成等差数列，或者是跨越层数最多的，和大组A中的小组a的第1个红色数、大组B中的小组b的第2个红色数构成等差数列。

图1

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

真正令人震撼的时刻到了。接下来，我们将对k施加归纳。下面尝试证明k＝4、c＝2的情况，即存在一个充分大的N，使得对 1到N的正整数进行二染色后，里面总存在长度为4的单色等差数列。由于当k＝3时每325个数里面必然有一个等差数列，因此我们按每487个数一组进行分组。这样可以保证每一组里面的前325个数中总存在长为3的单色等差数列，并且该数列的第4个数也在该组内。注意，一个487元组共有2⁴⁸⁷种染色方案，如果我们把它们看做2⁴⁸⁷种不同的“广义颜色”，由k＝3、c＝2⁴⁸⁷的情况知，必然存在3个组，这3个组的位置形成等差数列，并且它们的染色方案完全相同。考虑每一组中前325个数所形成的长为3的等差数列，并考虑该数列中第4个数的颜色：如果颜色相同，问题解决；否则便考察顺推下去的第4个组的相应位置上的数的颜色，它将别无选择。

类似地，我们可以归纳出任意大的k和任意大的c的情形。可想而知，也可以说难以想象，用这种做法得出的N是何等地巨大，它将很快超出整个宇宙中任何具有实际意义的数字，其大小已经不能用通常的方式来记录了。这个证明的气势太宏大了，以至于当初很多人都没想到。当我第一次读到2⁴⁸⁷种颜色时，视野一瞬间广大得难以描述；并且当我向着k更大的方向看去时，不禁对思维的尺度表示深深的膜拜。