上一次写这玩意儿已经是两个月前的事了，今天突然想起这一系列的东西我还没有写完。和上次一样，我们将对另一个几何问题作出光学和力学两种解释。由于前面已经有了不少铺垫，很多东西这里就不再重复了。

  
    椭圆是平面上到给定两点的距离之和为定值的点的集合。那两个定点就叫做椭圆的焦点。椭圆有一个神奇的性质：选定椭圆上的任意一点P，把它和两个焦点A、B相连，则PA和PB与椭圆在P点处的切线有相同的夹角。换句话说，PA和PB与法线的夹角相等，即入射角等于反射角。这样的话，任意一条从A出发的光线，经过椭圆壁的反射后总会经过另一个焦点B。假如有一个餐厅是椭圆形的，你的位置恰好位于椭圆的一个焦点上。这时你突然听到不知哪里传出的一男一女谈情说爱的声音，其肉麻程度不堪入耳，并且声音格外清晰。不用怕，这是因为那对男女正好坐在另一个焦点上，他们谈话的声音再小你也听得见，因为这些声音经过房间墙壁的反射后全汇聚到你这里来了。
    你可以用解析几何证明这一结论，不过其复杂程度令人望而生畏。这是我上学期做的最恶心的一道高数题。有趣的是，这个结论用Fermat原理（光总是沿着所花时间最短的路径传播）来解释的话，根本不需要运算，几句话就说清楚了。我们需要证明这样一个几何命题，椭圆上一点P与焦点A、B的连线到过P点的切线的夹角相等。把过P点的切线作出来后，我们可以一眼看出这个论断是正确的：从点A出发的光线经切线反射后过点B，则反射点一定就是点P，因为切线上所有其他的点P'都在椭圆外，折线A->P'->B都比A->P->B长。

  
    后来，我在《数学与猜想》中看到了另外一种物理证明方法，非常神奇。这个结论的正确性可以通过一个非常简单的力学模型揭示出来。看上图，我们在两个焦点间连接一条长度为2a的绳子，绳子上挂一个重物。注意到重物是挂在绳子上的，绳结处P是可以活动的。显然，P点的轨迹形成了一个椭圆。重物有不断下落的趋势，此时重力势能转化为动能；当整个力学系统静止时，重力势能达到最小，因此最终绳结P应该位于椭圆的最低点，该点处的切线正好是一条水平线。此时绳结P受到了三个力：重物M所产生的垂直向下的力，以及左右两边的绳子的拉力。由于物体保持平衡，两个拉力的合力必须竖直向上才行。但绳子内部的张力处处相等，两个方向上的拉力大小应该一样；如果它们的合力竖直向上，那么这两个力的方向与竖直方向的夹角必然相同。于是我们得到了和上面的讨论相同的结论：椭圆上的点与两焦点的连线到法线的夹角相等。

    IMO 2001第三题：21个女生和21个男生一起参加了一场数学竞赛。结果显示，每个参赛者最多做对了6道题，并且对于任一对男生和女生，至少有一道他们都做对了的题。
    求证：存在这样的一道题，至少有三个女生和三个男生同时做对。

    当然，这个题目背景无趣而又生硬。如果是我的话，我肯定会把题目改成下面这个样子：21个女生和21个男生参加速配游戏，每个人独立地在自己的纸上写下不超过6种兴趣爱好。结果显示，对于任一对男女，他们都写下了至少一个相同的爱好。求证，存在某一个兴趣爱好，有至少三男三女都把它写上了。

    我是一个忠实于原题的好娃娃，因此还是用数学竞赛来当题目背景。对于每个问题，如果有至少3个男生答对了，就给这个问题添加一个标记“B”；如果有至少3个女生答对了，就给这个问题添加一个标记“G”。然后我们画一张21×21的表格，横行代表男生，纵列代表女生。每一个格子都代表一道对应的男女同时做对的题（不同的格子可能对应相同的题目），我们把对应的题目的“B”、“G”标记填进格子里。
    下面我们说明，每一横行里至少有11个格子标了“G”，每一个纵列里至少有11个格子标了“B”。考虑某一个特定的人，他（她）与每一个异性参赛者都有同时答对的题目，但他（她）自己最多只做出6道题。这6道题目需要“分配”给21个异性参赛者。我们希望知道最多有多少道题被不超过2个异性参赛者答对。显然，最极端的情况就是其中的5道题目每道分别被2个异性做对，剩下的第6道题被其余11个异性做对。反过来这也就是被至少三个人答对的题目最少的情况，因此每一行（列）里都有至少11个格子标有异性的标记。
    这样，我们就有了至少21*11个标有“G”的格子，和至少21*11个标有“B”的格子。但21*11*2 > 21*21，因此总有一个格子被同时标上了“G”和“B”。

来源：http://www.cut-the-knot.org/pigeonhole/BoysGirlsProblems.shtml

    三个人坐成一个圆圈，每个人头上戴着一顶黑色的或者白色的帽子。每个人都只能看到另外两个人头上的帽子颜色。现在，他们需要独立地猜测自己头上的帽子颜色。每个人都需要在自己的小纸条上写下“黑色”、“白色”或者“放弃”。如果说至少一个人猜对，并且没有人猜错，那他们就获胜了；只要有任何一个人猜错，或者所有人都写的“放弃”，那么他们就输了。如果在游戏开始前他们能够商量一个策略，那么最好的策略是什么？
    仔细想一下你会发现，要想保证他们百分之百地获胜是不可能的，因为游戏中大家不能交流信息，谁也不能保证自己能猜对。但是，有一种策略能保证他们有75%的几率获胜。事实上，当人数n=2^k-1时，我们有一种方法可以让获胜的概率达到(2^k-1)/(2^k)。你能想到这种策略吗？

    设身处地地想，你会想到一个很自然的策略：如果一个人看到另外两个人的帽子颜色一黑一白，那这个人就放弃（换了你你也不敢猜）；如果另外两个人的帽子颜色一样，那你就猜相反的颜色（概率上看也要大些）。我们来看一下在哪些情况下使用这样的策略能够获胜：

3个黑帽子：每个人都看到两个黑帽子，每个人都猜自己是白帽子，所有人都猜错；
2个黑帽子，1个白帽子：戴黑帽子的人看到一黑一白，于是放弃；戴白帽子的人看的是两个黑帽子，因此他将猜对，从而所有人都获胜；
2个白帽子，1个黑帽子：和上面这种情况是类似的，所有人都将获胜；
3个白帽子：和第一种情况是类似的，所有人都猜错。

    注意到只有在第一种情况和第四种情况下才会输掉游戏，这两种情况占了所有情况的2/8。于是，使用这种策略有75%的概率获胜。

    我们需要想一想，在这个看似几乎不可能获胜的游戏中，为什么这种策略会有如此高的获胜概率。最关键的就是，这种策略充分利用了胜负判断的准则：大家要错就一起错，只有一个人错怪划不来的；要获胜就只让一个人猜对，多几个人同时猜对也没用。

    根据上面的讨论，我们开始尝试把游戏的人数推广到一般的n。为了叙述方便，我们把每个人头顶上的帽子颜色依次用0和1来表示，数字1表示黑帽子，数字0表示白帽子。于是所有可能的情况就是2^n个01串。游戏开始前n个人预先约定一些“保留串”。他们的策略就是，观察其余n-1个人的帽子颜色：如果和所有的保留串都不匹配里，则放弃；如果恰好符合某个保留串，就猜自己是相反的颜色。比如，当n=3时，他们可以约定两个保留串000和111。如果实际情况是001的话，前两个人看到的是?01和0?1，不属于任何一个保留串，于是放弃；第三个人看到的是00?，正好和000相符，于是他就反过来猜自己不是那个0。注意到一些有趣的事实：如果实际情况恰好就是这些保留串之一，那大家就全猜错了；如果实际情况与所有保留串都相差两个数字以上，那大家全部放弃；如果实际情况与某个保留串恰好差一个数字，那只有一个人猜对，其余人放弃，从而获得胜利。现在的问题就是，如何寻找一个保留串集合，使得和某个保留串只差一个数字的情况尽可能的多。注意，我们必须要保证，任意两个保留串之间不能只差一个数字，这样的话才能保证发现有相符保留串的人不会面临“两可”的情况。假如你找到了t个保留串，则保证获胜的情况最多有t*n个（每个串“变一位”都有n种方法）。显然，最完美的情况就是t+t*n恰好等于总的情况数2^n。当n=2^k-1时，t+t*n是有可能恰好等于总情况数2^n的，也就是说每种可能的情况要么就是一个保留串，要么与唯一的一个保留串恰好差一位。此时，t+t*n=t(n+1)=t*(2^k)=2^(2^k-1)，t应该等于2^(2^k-1-k)。下面我们说明这t个保留串是如何生成的。
    每个保留串都由原码和校验码两部分组成。我们把n位01串的位置编号转化为二进制，二进制里只有一个数字1的位置（即左起第1,2,4,8,…位）叫做校验码，有至少两个1的位置（3,5,6,7,9,…等其余位置）上的数字称作原码。显然，原码应该有n-k位（即2^k-1-k位）。枚举2^(n-k)种原码的01组合，对于每一组原码，定义第i个校验码的值为，除了它本身以外，所有编号的二进制表达中右起第i个数字为“1”的位置上一共有奇数个1还是偶数个1（相当于把标“x”的位置上的数异或一遍）。比如，第2个校验码是1，当且仅当有奇数个位置上的原码满足，位置编号的二进制表达形如…???1?且该位置上的数值正好也是1。所有可能的原码加上它对应校验码就是我们的保留串。

  01串:     a1  a2  a3  a4  a5  a6  a7
十进制编号:  1   2   3   4   5   6   7

二进制编号: 001 010 011 100 101 110 111
校验码1(a1):         x       x       x
校验码2(a2):         x           x   x
校验码3(a4):                 x   x   x
保留串0:     0   0   0   0   0   0   0
保留串1:     1   1   0   1   0   0   1
保留串2:     0   1   0   1   0   1   0
保留串3:     1   0   0   0   0   1   1
保留串4:     1   0   0   1   1   0   0
   ……      ……     ……        
保留串14:    0   0   1   0   1   1   0
保留串15:    1   1   1   1   1   1   1

    我们可以说明，对于任一个n位01串，只要它不是我们的保留串，我都有办法只变动一个数字让原码和校验码相符（从而变成一个保留串）。我们可以观察一下，由原码算出来的校验码和实际的校验码有哪些不同。如果只有一位校验码不同，直接把它改过来就是了；如果有多位校验码不同，那就找出改动哪一位原码可以让这些校验码同时取反。从位置编号的二进制的角度来考虑，这样的一位原码显然是唯一存在的。同时，我们可以保证任两个

  
    有这样的一类组合游戏，对于任一个游戏局面，游戏双方的合法决策都完全一样，游戏对战双方的唯一区别就是看谁先走。这样的游戏叫做Impartial Games。像什么报数啊，取火柴啊，取石子啊，这些游戏都属于Impartial Games；而象棋、围棋等要分棋子颜色的游戏则不属于Impartial Games。共享状态的游戏几乎没有可玩性，因为游戏开始前我们就能知道谁赢谁输（如果双方均使用最佳策略）。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。
    近来有人提出一个名为Atropos的游戏，它就是一个即使计算机也很难办的Impartial Game，它能保证这个游戏仍然具有可玩性。游戏在一个Sperner三角形上进行，上图就是一个边长为7的Sperner三角形。游戏开始后，双方依次在白色的圆圈里涂上红色、绿色或者蓝色，已经涂过颜色的圆圈不能再涂色。另外，只要有可能，所涂的圆圈都必须紧挨着上次对方涂的那个圆圈。谁先涂出三种颜色都有的小三角形，谁就输掉这场游戏。

  
    注意这个游戏是不可能出现平局的。当所有白色圆圈全部涂上了颜色后，至少会出现一个红绿蓝小三角形。为了证明这一点，我们可以在所有的绿色和红色圆圈中间画一个箭头，红的在箭头右边，绿的在箭头左边。这些箭头一定组成了一条一条的路径，它们既不会交汇也不会分岔。但整个图的边界上进来的箭头有4个，出去的箭头只有3个，于是至少有一条路径在里面走死了，也即迎面碰上了蓝色的圆圈。这样，我们就找到了一个红绿蓝三色都有的小三角形。

    这个游戏虽然属于Impartial Games，但它仍然具有可玩性。从直觉上看，这个游戏中的先手后手几乎没有区别，谁也不占优势。这篇论文则严格证明了，判断Atropos游戏的最佳策略属于PSPACE-complete，这是所有使用多项式空间的问题中最难的一类，所有使用多项式空间的问题都可以（在多项式的时间内）约化到它。这说明，Atropos游戏没有什么很显然的“决窍”，即使利用计算机也很难确定最优决策。

在线游戏：http://cs-people.bu.edu/paithan/spernerGame/SpernerGame.html (Java Applet)
查看更多：http://cs-people.bu.edu/paithan/spernerGame/

    小学奥赛的经典题目：两个人轮流在黑板上写一个不大于10的正整数。规定不准把已经写过的数的约数再写出来。谁最后没写的了谁就输了。问是先写的人必胜还是后写的人必胜，必胜策略是什么。
    答案很巧妙。先写者有必胜策略。他可以先写下数字6，现在就只剩下4、5、7、8、9、10可以写了。把剩下的6个数分成三对，分别是(4,5)、(7,9)、(8,10)，每一对里的两个数都不成倍数关系，且它们各自的倍数（如果出现过）必然是同时出现。因此不管你写什么数，我就写它所在的数对里的另一个数，这样可以保证我总有写的。
    今天偶然看到一个加强版，不知大家见过没有：规则不变，可以写的数扩展到所有不大于n的正整数。对于哪些n先写者必胜？证明你的结论。

    你会有一种被骗的感觉-_-b
    其实，不管n是多少，先写者总有必胜策略。考虑一个新的规则“不准写数字1”。如果加上这个新规则后先写者有必胜策略，那么这个策略对于原游戏同样适用（因为1是所有数的约数，本来就不能写）；如果在新规则下后写者必胜，则原游戏中的先写者写下数字1，然后他就变成了新规则下的后写者。于是不管怎么样，先写者总是有必胜策略。
    To 3楼：忘了提一句，只要是双方共用状态（合法的决策完全相同）的对弈游戏，其中一方肯定有必胜策略。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。

    
    Update: 感谢网友FreePeter的精彩评论。这种分析方法有一种很形象的名字叫做Strategy-stealing，它的另一个经典例子是Chomp游戏。游戏在一块矩形的巧克力上进行，巧克力被分为MxN块。两人轮流选择其中一个格子，然后吃掉这一格及它右边、下边和右下角的所有格子。最左上角的那一块巧克力有毒，谁吃到谁就输了。上图是一个可能的对战过程。我们可以用类似的方法证明先手必胜。假设后手有必胜策略，那么先手把最右下角的那一块取走。注意到接下来对方不管走哪一步，最右下角的那一块本来也会被取走，因此整个棋局并无变化，只是现在的先手扮演了后手的角色，可以用后手的那个必胜策略来应对棋局，这样便巧妙地“偷”走了后手的必胜策略。
    上面所举的例子都是双方共用状态的游戏（ICG游戏），因此至少有一方存在必胜策略。对于其它一些非ICG游戏，我们也可以用类似的方法证明后手不可能有必胜策略（但在这里并不能说明先手一定必胜）。比如对于井字棋游戏，假设后手有必胜策略，那先手就随便走一步，以后就装成是后手来应对。如果在哪一步需要先手在已经下过子的地方落子，他就再随便走一步就是了。这种证明方法成立的前提就是，多走一步肯定不是坏事。事实上，对于所有这种“多走一步肯定不是坏事”的且决策对称的游戏，我们都可以证明后手是没有必胜策略的。