趣题：均匀分布且和为常数的n个变量

2009 年 5 月 3 日 / 16 条评论

不知道大家有没有幻想过，数学中是否存在这样一个牛B的问题，发表出来后十几年硬是没有一个人解开；后来某人惊奇地发现，它有一个极其精妙的解答，整个解决过程只需要几句话就能说清楚，但它实在是太巧妙了，这么多年就没有任何人想到。最近我就遇到了这样的事情。3月份UyHiP的题目非常有趣，整个证明几句话就完了，但想到解法的却只有一人。
题目描述也极其简单。对于哪些n，存在一种生成n个随机变量的算法，使得它们在0和1之间均匀分布，且它们的和是一个常数？更进一步，如果这n个变量中任意k个都相互独立，满足要求的k最大是多少（表示成关于n的函数）？

当然，这道题目我也没想出来。答案公布前，我思考了很久，最后还是放弃了。显然n是偶数时这样的算法是存在的，例如当n=6时，只需要先独立地选取3个随机变量X_1, X_2, X_3，然后令X_4 = 1 – X_1，X_5 = 1 – X_2，X_6 = 1 – X_3即可。这可以保证6个变量之和总为3，且它们均匀地分布在[0,1]区间里。但是当n是奇数时，满足要求的算法就未必存在了。例如当n=3时，不妨让X_1和X_2随机取，X_3等于1.5 – X_1 – X_2。这种算法似乎很和谐，问题就出在X_3有可能不在0和1之间。那么，重复执行该操作直到返回一个落在[0,1]里的X_3呢？这样的话变量又不是均匀分布的了，这将让变量更容易取到中间去，因为X_1和X_2太小或太大往往算不出合法的X_3（下图是Mathematica模拟的结果）。我试图从“n个变量的和的期望值是n/2”出发，证明和为1.5的3个变量不可能均匀分布在0到1之间。不过，最终还是没有找到突破口。

经典证明：列表染色与可选择数（上）

2009 年 4 月 27 日 / 10 条评论

四色定理告诉我们，给地图上的每个区域涂一种颜色，为了使相邻的区域有不同的颜色，我们总共只需要4种颜色就够了。不过，万一有些省装怪，偏不喜欢分配给它的颜色该咋办？这下问题就变得有意思起来了。为了满足不同省市的要求，国家测绘局可以在为地图染色前先让每个省市列出自己能够接受的几种颜色，染色时就只从每个省市给出的候选颜色中取色。我们把每一个使得相邻区域的颜色互不相同的染色方案叫做一种列表染色(list coloring)。现在的问题是，至少要求每个省市列出多少个候选颜色才能使合法的列表染色总是存在，不管这些颜色列表是什么？如果每个省市列出k种颜色就足够了，我们就称该地图是可k选择的(k-choosable)。或许大家会想，k=4就够了吧，毕竟四色定理保证了只使用4种颜色一定能实现合法的染色，而在列表染色问题里总的颜色很可能还不止4种，同时相邻区域的公共颜色数量也将减少。但是，数学家们早就注意到，能够k着色的平面图不见得就一定可以k选择。例如，下面这个图显然可以二着色，但它就不是二选择的——如果每个区域的颜色列表如图中所示，则不存在满足要求的列表染色。因此，人们普遍认为，并不是每个平面图都是可4选择的。

不过，数学家们一直没能找到不可4选择的平面图。1993年，Voigt发现了第一个不能4选择的平面图，它有238块区域。构造方法非常具有启发性，从里面能看到不少数学思维方法。

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

2009 年 4 月 17 日 / 10 条评论

我们知道，存在这样一种全体正整数的红蓝二着色方案，其中没有任何无穷长的等差数列满足数列中的所有数颜色都一样。它的构造非常暴力。有趣的是，把上述命题中的“无穷长”换成“任意长”，命题就不见得仍然正确了。事实上，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即满足条件。

趣题：对全体正整数红蓝二着色使之不含单色无穷等差数列

2009 年 4 月 6 日 / 15 条评论

你认为，是否有可能把全体正整数染成红蓝二色，使得不存在无穷等差数列，数列中的所有数都是一种颜色？如果你认为存在这样的染色方案，请给出一个构造方法；如果你认为不存在，证明之。在看下面的答案之前，不妨先仔细思考一下。

事实上，满足题意的染色方案是存在的，构造方法非常简单，非常直接，非常暴力。显然，无穷等差数列只有可数个，不妨把它们分别叫做A_1, A_2, A_3, …。现在，如果我们能够构造两个数列r_1, r_2, r_3, …和b_1, b_2, b_3…，使得对于每一个i，r_i和b_i都在数列A_i中，并且r数列中的每个数都和b数列中的所有数都不相同。这样，把r数列中的所有数染成红色，把b数列中的所有数染成蓝色（其它未出现的数随意染色），就能保证每个无穷等差数列都包含了至少两种颜色。
而这样的r数列和b数列显然存在，因为每一次选择新的r_i和b_i时，无穷数列A_i中都只有有限个数不能选，因此r_i和b_i永远都有选的。

Update: 地基层网友给出了一个更巧妙、更简单的构造方法：对全体正整数倍长间隔染色，即把1染成红色，2和3染成蓝色，4到7染成红色，8到15染成蓝色……。显然，当染色区间的长度大于公差时，等差数列最终都将一截一截地落在不同的染色区间中。

经典证明：素数无穷多的拓扑学证明

2009 年 4 月 5 日 / 24 条评论

去年就看过Proofs from THE BOOK第一章中的素数无穷多的拓扑学证明，不过当时似乎并没有看懂。今天看到cut-the-knot的一篇新文章，又把Proofs from THE BOOK拿出来翻了一下，终于看明白了，果然是一个令人拍案叫绝的经典证明，可谓又一神来之笔。

    定义N(a,b) = {a + nb| n∈Z}，例如N(1,3)就等于{…, -5, -2, 1, 4, 7, …}。每一个N(a,b)实质上都是一个以b为公差的“双向无限等差数列”。我们说整数集Z上的一个子集S是开的，如果集合S为空，或者对于任意一个a∈S，总能找到一个b>0使得N(a,b)⊆S。形象地说，开集的意思就是，集合中的每一个元素都能在集合内扩展出一个无限长的双向等差数列。我们又称一个集合S是闭的，如果它是某个开集的补集。
    显然，有限个开集的并集仍然是开集。
    假设S_1和S_2都是开集，如果a∈S_1∩S_2，并且N(a,b1)⊆S_1，N(a,b2)⊆S_2，那么S_1∩S_2中有一个公差为b1*b2的含a的双向无限等差数列，也即a∈N(a, b1*b2)⊆S_1∩S_2。这说明，有限个开集的交集仍然是开集。
    再假设C_1和C_2都是闭集。由De Morgan定律，C_1和C_2的并集就相等于它们各自的补集相交后再取补集，由定义可知它们的补集都是开集，而由上面的结论可知开集的交集仍是开集。于是，C_1和C_2的并集是某个开集的补集，这说明闭集的并仍然是闭集。类似地，闭集的交集相当于补集的并集的补集，它也仍然是闭的。

    还有两点值得引起我们注意：
    1. 任意非空开集都是无穷的。这由定义可以直接看出来。
    2. 任一双向无限等差数列N(a,b)既是开集又是闭集。由定义可知N(a,b)是开集，而同时N(a,b)又可以看作是N(a+1,b)∪N(a+2,b)∪N(a+3,b)∪…∪N(a+b-1,b)的补集，这是有限个开集的并集的补集，说明N(a,b)也是闭集。