今天在写一个稿件时又翻阅了一下Erich Friedman的Math Magic，发现了一个有趣的东西——场地大小为n的推箱子游戏所需要的最少步数最坏情况是多少。下面这个构造说明，最坏情况至少也是指数级的。
首先，让我们来看看该构造中的一个基本单元：
这个构造中共有6个箱子，且它们都已经在目的位置上了。不难看出：
1. 假如你人在这个区域之外，你只可能从右上角的出入口进入该区域，从其它地方进去都会导致死局
2. 从右上角进入后你只能往下走，进入1区；走左边的话直接导致死局
3. 你可以通过2区前往3区，但若从3区左上角的出口出去了，则2区动过的箱子将永远无法回到原位（除非你原路返回）
4. 你可以通过2区前往3区，并把3区左边的那个箱子左移一格，再返回2区；这样下次你再从右上角进入该区域时便可以直接经过3区从左上角出去
5. 最后你只能从4区离开
这里有一个有趣的问题：在集合{1, 2, …, n}中选取尽可能多的子集，使得任意两个子集的交集有且仅有一个元素。例如，当n=7时，选取{1,2,3,4}、{4,5,6,7}、{1,7}这3个集合可以满足条件。子集数还可以更大一点吗？最大是多少？给出一种构造，然后证明这个数目不可能更大了。
当n=7时，仅仅取3个子集实在是太弱了。一种最简单的办法就可以让子集数达到6，只需取{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}即可。再仔细观察，我们发现这个结果还可以进一步改进：我们还可以再往里面添加进一个子集{1}，使得这7个子集两两间仍然恰有一个公共元素。这下我们似乎不能再往里面添加任何新子集了。我们还可以做得更好吗？一个新的思路是在{1,2}、{1,3}、{1,4}、{1,5}、{1,6}、{1,7}里面加上{2,3,4,5,6,7}，这同样可以让子集数达到7个，可惜我们仍然无法再往里面添加新的子集了。经过若干次尝试后，我们逐渐开始确信，在集合{1, 2, …, n}里面最多只能选出n个两两恰有一个公共元素的子集，并且构造方法无外乎上面两种。这一猜想不但与直觉相符，而且貌似也很好证明。你或许会从一些看似很直观的结论出发开始证明：“显然不可能有两个大小为1的子集”，“选取多个元素个数大于2的子集显然不划算”……但牛B就牛B在，偏偏就有这样一种子集数为n的取法，每个子集里都有不止两个元素，但仍然保证任意两个子集间恰有一个公共元素：
{1,2,3}、{1,4,5}、{1,6,7}、{2,4,7}、{3,4,6}、{3,5,7}、{2,5,6}
这一个例子对我们的猜想足以构成威胁：子集数为n真的已经到极限了吗？证明结论有那么容易吗？看来，情况貌似比我们想象中的要复杂得多。
大学生活混起来很快，不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆，因此今年我主动去报了名（上次是被人给拖去的）。今年有点装怪，题目数量不变，但时间缩短为4个小时。原计划是从8:00做到12:00，结果可能是因为我们所在的7号机房迟迟没有开门，时间临时改成了8:15到12:15。总的来说，今年的题目比去年要糟糕得多，但也不乏一些精彩的题目。
和去年一样，第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁，我猜不少队伍都卡在这儿了吧。
后来我完全打翻前面的全部思路，猛然想到了一个具有决定意义的想法：街道的选取唯一地决定了整个路线。例如，假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的，其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此，我们可以用排列组合直接计算出答案来。向上走的路是五选二，向右走的路是七选三，向下走的路是四选三，向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是，计算所有的路线数只需要从小到大枚举拐弯的次数，每一次计算都是常数的，总复杂度是O(n)的；整个算法的瓶颈反倒是O(n^2)的组合数预处理，不过这个复杂度完全可以承受。
我们知道，存在这样一种全体正整数的红蓝二着色方案，其中没有任何无穷长的等差数列满足数列中的所有数颜色都一样。它的构造非常暴力。有趣的是，把上述命题中的“无穷长”换成“任意长”，命题就不见得仍然正确了。事实上，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即满足条件。
概率论并不仅仅是用来算算概率的。有些时候，概率论远比我们想象中的更强大。
考虑这样一个问题。考虑集合X上的一个集合族，集合族中的所有集合大小均为d。我们说这个集合族是可以二染色的，如果对X的元素进行适当的红蓝二着色之后，每个集合里面都包含了两种颜色的元素。例如，当d=3时，{1,2,3}, {1,2,4}, {1,3,4}, {2,3,5}就是可二染色的，把1、2染成红色，把3、4、5染成蓝色，则每个集合里都含有两种颜色。是否存在d=3的不可二染色集族呢？这样的集族当然是存在的，例如取集合{1,2,3,4,5}的全部C(5,3)个元素个数为3的子集，则无论如何染色，总会有一个集合里面的元素全是一种颜色。上述推理立即告诉我们，对于一个给定的d，一定存在一个集合个数为C(2d-1, d)的不可二染色集族。这个数目还能再少吗？我们想知道，不可二染色集族中的集合个数最少可以少到什么地步。一个极其简单的证明给出了一个下界：集族的大小一定大于2^(d-1)。当d=3时，你一辈子也不能构造一个不可二染色集族，里面只含4个集合。
为了证明这一点，不妨对X中的所有元素进行随机着色，每个元素取成红色和蓝色的概率均等。那么，一个元素个数为d的集合中，所有元素均为一种颜色的概率就应该是1/2^(d-1)。如果集族内的集合个数只有不到2^(d-1)个，那么即使“集合中是否只有一种颜色”是互相独立的，这些事件的并（至少有一个集合内只有一种颜色）的概率也不超过2^(d-1) * 1/2^(d-1) = 1，何况这些事件还不是独立的，因此存在单色集合的概率必然小于1。这个概率值小于1说明什么？这说明，“至少有一个单色集合”并不是必然事件，一定有一种染色方案使得每个元素里都含两种颜色，换句话说该集族可以被二染色。