三个人坐成一个圆圈，每个人头上戴着一顶黑色的或者白色的帽子。每个人都只能看到另外两个人头上的帽子颜色。现在，他们需要独立地猜测自己头上的帽子颜色。每个人都需要在自己的小纸条上写下“黑色”、“白色”或者“放弃”。如果说至少一个人猜对，并且没有人猜错，那他们就获胜了；只要有任何一个人猜错，或者所有人都写的“放弃”，那么他们就输了。如果在游戏开始前他们能够商量一个策略，那么最好的策略是什么？
    仔细想一下你会发现，要想保证他们百分之百地获胜是不可能的，因为游戏中大家不能交流信息，谁也不能保证自己能猜对。但是，有一种策略能保证他们有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串，只要它不是我们的保留串，我都有办法只变动一个数字让原码和校验码相符（从而变成一个保留串）。我们可以观察一下，由原码算出来的校验码和实际的校验码有哪些不同。如果只有一位校验码不同，直接把它改过来就是了；如果有多位校验码不同，那就找出改动哪一位原码可以让这些校验码同时取反。从位置编号的二进制的角度来考虑，这样的一位原码显然是唯一存在的。同时，我们可以保证任两个保留串之间都相差至少两个数字，即便你的原码只改动一位，校验码必然也会随之变化。前面已经说过，保留串的个数有2^(2^k-1-k)个，只有这2^(2^k-1-k)种情况下才会输掉游戏。因此，我们最初的问题就解决了：当人数n=2^k-1时，获胜的概率达到1 - [2^(2^k-1-k)/2^(2^k-1)]，即(2^k-1)/(2^k)。
    顺便说一句，上面的编码方式叫做Hamming编码，是一种数据传输的校验方式。

参考资料：http://cornellmath.wordpress.com/2007/09/20/hat-guessing-puzzles-the-revenge/ （会意字，从啬从土）

  
    有这样的一类组合游戏，对于任一个游戏局面，游戏双方的合法决策都完全一样，游戏对战双方的唯一区别就是看谁先走。这样的游戏叫做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/

  

- 我讨厌“快速增长5厘米”之类的垃圾邮件
- 操！我他妈的连向量都还不是呢！

来源：http://brownsharpie.courtneygibbons.org/?p=508
另，可爱的叉烧妖MM给我推荐了一个有意思的东西，大家可以去看看。

    最近，Claudio Baiocchi提出了这样一个问题：用相同形状的多联骨牌拼成完全对称图形，问对于哪些多联骨牌问题是有解的。这个问题最早出现在Erich Friedman今年一月的Math Magic里。令人吃惊的是，所有不超过6联的骨牌都是有解的。Erich Friedman自己找到了大多数的解，Corey Plover也找出了一些解，其余的解则是George Sicherman发现的。
    单联到6联的骨牌个数分别为1, 1, 2, 5, 12, 35。它们的解分别如下：

Monomino:


Domino:


Trominoes:


Tetrominoes:


Pentominoes:


Hexominoes:

    小学奥赛的经典题目：两个人轮流在黑板上写一个不大于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游戏，我们也可以用类似的方法证明后手不可能有必胜策略（但在这里并不能说明先手一定必胜）。比如对于井字棋游戏，假设后手有必胜策略，那先手就随便走一步，以后就装成是后手来应对。如果在哪一步需要先手在已经下过子的地方落子，他就再随便走一步就是了。这种证明方法成立的前提就是，多走一步肯定不是坏事。事实上，对于所有这种“多走一步肯定不是坏事”的且决策对称的游戏，我们都可以证明后手是没有必胜策略的。

1. Goldbach猜想是说，任一大于等于4的偶数一定能表示成两个质数之和。关于质数，我们还有这样一个有趣的结论：对于任何整数n>1，存在质数p满足n<=p<2n。这个结论对Goldbach猜想是很“有利”的，因为它是Goldbach猜想的一个必要条件。倘若对于某个正整数n，n和2n之间没有质数，那么偶数2n就不能表示为两个质数之和了，因为所有可以用的质数都比n小，再怎么也加不出2n来。注意，如果这个结论错了，猜想也就被推翻了；但如果这个结论对了，猜想也不一定是对的。但即使这样，我们仍然习惯性地认为，验证了推论的正确性后猜想的可靠程度也或多或少的有了些提高，换句话说猜想为真的可能性更大了。这种思维合理吗？

2. 长期以来，人们都在思考：对任一给定的平面图进行染色，要想使得有公共边的区域颜色不同，最少需要多少种颜色。四色猜想（现在已经是四色定理了）认为，只需要最多四种不同的颜色就足够了。我们可以随便画一些图进行验证，每一次检验后我们都会或多或少地更加相信结论的正确性。你可以尝试寻找下面的图1、图2和图3的合法解，检验一下猜想是否正确。验证哪一个图更有价值？你或许会这样回答：验证第一个图毫无价值，因为它显然有可行的染色方案；验证第三个图最有价值，因为它看上去最像反例，证实了它确实有解后，你会更加坚信四色猜想的正确性。1975年的4月1日，杂志Scientific American的数学专栏作家Martin Gardner宣布他找到了一个四色猜想的反例（图4）。当然，这只是一个愚人节的笑话。寻找图4的解非常困难，以致于看上去几乎是不可能的。一旦你成功找出了图4的解，对四色猜想的信任程度可就不只提高一点点了。“对猜想的某个结论进行验证，结论越是不可思议，证实以后原猜想的可靠程度就提高得越多”，这种思维是合理的吗？
  


  
3. 你认为，是否有可能把一个直角三角形分成若干个锐角三角形？你很可能花了一节古代汉语课的时间苦思冥想，结果直角三角形没搞出来，倒是碰巧把一个正方形分成了8个锐角三角形。虽然你仍不知道一个直角三角形是否能分成若干个锐角三角形，但你找到了一个正方形的解，你会强烈地感觉到直角三角形也是有解的。这是什么原因呢？注意到，如果三角形能分的话正方形一定能分，但反过来却不一定。不过，这里面还有一些更微妙的关系：我们倾向于相信如果连直角三角形都没法分，正方形应该更没法分了。既然现在正方形已经解决了，那三角形也就快了。“B是A的结论，且没有A的B很不可靠，则证实了B可以极大地提高A的可信度”，这种思维合理吗？

4. 关于“如果他错了，那我对的概率就更大了”的思维。A、B两人被一个实际问题难住了，双方就问题中的两个变量的变化关系争执不休。A认为，函数图像画出来应该是一个开口朝上的二次函数；B则认为，函数图像应该是一个正弦函数。注意到一个有趣的事实：这两种猜测满足矛盾率，但不满足排中率。就是说，有可能A和B都错了，但是A和B不可能都对。紧接着他们发现，这个函数存在至少一个极大值，A的猜测显然是错的。虽然这并不能表明B的猜测就是对的，但我们能不能说B猜对的概率变大了？








    下面的内容是G.Pólya的Mathematics and Plausible Reasoning Vol 2里的精华：用概率来分析合情推理模式。我们可以用概率知识来描述上面这些合乎情理的推测。如果你还不知道什么叫做条件概率，建议你先看一看这篇文章。
    注意到P(A)*P(B|A)永远等于P(B)*P(A|B)，它们都等于P(A∩B)。如果B是A的一个推论，那么有P(B|A)=1（若A为真则B必为真）。于是我们有P(A)=P(B)*P(A|B)。这里，P(A|B)有一个形象的意义：结论B的证实可以使我们对A的信任改变多少。假如P(A|B)不变，则如果等式右边的P(B)增加了，P(A)也会增加。这也就说明了我们的第一个合情推理模式：对猜想的一个结论更加信任，对猜想本身也更加信任。
    这个式子还能告诉我们更多的东西。把P(B)除过去，我们有P(A|B)=P(A)/P(B)，其中等式左边的P(A|B)表示的仍然是证实了B以后A为真的概率，也就是验证B结论的价值。我们很清楚地看到，P(B)处于分母的位置。那么，结论B本身为真的概率越小，证实了B后对A的影响也就越大。
    注意P(B)=P(A∩B)+P(～A∩B)=P(A)*P(B|A)+P(～A)*P(B|～A)，而B是A的一个结论，即P(B|A)=1。于是，等号右边变为P(A)+[1-P(A)]*P(B|～A)。利用前面的结论，我们用P(A)/P(A|B)代替等式左边的P(B)，则有P(A|B)=P(A)/[P(A)+[1-P(A)]*P(B|～A)]。可以看到，如果P(B|～A)越小，则P(A|B)越大。这就是说，在没有A的前提下B成立可能性越小，证实了B之后A为真的可能性就越大。
    最后，我们看一看A和B不相容的情况。此时，P(A∩B)=0，于是
P(A) = P(A∩B) + P(A∩～B)
      = P(A∩～B)
      = P(～B) * P(A|～B)
      = [1-P(B)] * P(A|～B)
    把1-P(B)除过去，就有P(A|～B)=P(A)/[1-P(B)]，显然P(A|～B)是大于P(A)的，也即排除了B的猜测后A对的可能性比原来更高了。我们还可以清楚地看到，如果我们之前越相信B，则B被驳倒后A正确的可能性提高得就越多。

  
    给定一个大圆C，里面的六个小圆均内切于圆C。如果这六个小圆中每相邻两个小圆均外切，则连接相对的内切点所成的三条线段共点。
    这是一个非常漂亮的结论。它的证明比较复杂。如果你能独立想出来的话，你就牛B了。大家不妨来挑战一下。























      
    Stanley Rabinowitz于1975给出了一个简单的初等证明。证明的关键在于下面的这个引理：圆周上有A、B、C、D、E、F六点，线段AD、BE、CF共点当且仅当AB·CD·EF=BC·DE·FA。
    引理的证明其实很简单。注意到圆周角∠CBE和∠CFE相等，圆周角∠BCF和∠BEF相等，于是△CPB∽△EPF。类似地，每一组相对的三角形都相似。于是，我们有：

  AB/DE = PA/PE
  CD/FA = PC/PA
  EF/BC = PF/PB
  PC/PE = PB/PF

    等式左边右边分别乘起来，结论也就证到了。
    引理的充分性也是类似的。假设AB·CD·EF=BC·DE·FA但三线不共点，令某两条线段（比如BE和CF）的交点为P，延长AP交圆于X，则有AB·CX·EF=BC·XE·FA，两式一比较我们就发现CX/XE=CD/DE，那只有可能是点X与点D重合。

    下面我们的任务就简单了：假如已知圆C的半径为R，圆P和圆Q外切且分别与圆C内切，半径分别为p和q，我们需要想办法求出线段AB的长度。

  
    延长AM交圆C于D，延长BM交圆C于E。△ACD和△APM都是等腰三角形，且有一个公共角∠A，因此这两个三角形相似，从而推出CD∥MP；同理，CE∥MQ。但PMQ在一条直线上，因此DCE也是一条直线。注意到圆周角∠EBA=∠EDA，且∠BAD=∠BED。于是我们发现△ABM和△EDM也是相似的，即AB/DE=AM/EM=BM/DM。但DE等于2R，于是有：
  AB/2R · AB/2R
= AM/EM · BM/DM
= AM/DM · BM/EM
= AP/CP · BQ/CQ
= p(R - p) · q(R - q)

    现在，把这个结论同时运用到六对外切圆上。假如六个圆与圆C的切点分别为A1、A2、A3、A4、A5、A6，则有：
   (A1A2 · A3A4 · A5A6)^2
=  64R^6 · r1(R-r1)·r2(R-r2)·r3(R-r3)·r4(R-r4)·r5(R-r5)·r6(R-r6)
=  (A2A3 · A4A5 · A6A1)^2
    那么A1A2·A3A4·A5A6=A2A3·A4A5·A6A1，由前面的引理我们就知道了A1A4、A2A5、A3A6三线共点。

来源：http://www.cut-the-knot.org/Curriculum/Geometry/SevenCirclesTheorem.shtml

  

官方网站：http://www.math.cmu.edu/~fho/jenn/
Windows版下载：http://www.math.cmu.edu/~fho/jenn/jenn3d_win_2008_01_15.zip

   想知道各种几何模型在超球面（四维球的球面）上的样子吗？这个程序可以把各种几何体映射到超球面上，然后用三维的方式展示出来。你会发现几何体的棱和面都是弯的，这是因为这些几何体是在四维球面中的。就像三维球表面上的赤道和两根经线组成的“三角形”一样，每条边都是弯的。

    当然，最神奇的还是在这样的空间里下围棋！
    Windows版超球面围棋程序下载：http://www.math.cmu.edu/~fho/jenn/jenngo_win.zip
    双击左键下黑子，双击右键下白子；左键拖动旋转，右键拖动遍历第四维。
    你会发现，这个空间在边界处与自身相交。