小学奥赛的经典题目：两个人轮流在黑板上写一个不大于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

    你认为是否有可能存在这样一个函数f：在平面上随便画一个圆，圆里面总能够找到函数图像上的一个点？继续看下去前，不妨先仔细思考一下。

    为了说明任一圆内都包含函数上的点，我们只需要说明对于平面上任意给定点(x,y)，对于任意小的d都能在函数上找到一点，使得其横坐标落在x±d的范围内且纵坐标落在y±d内。这样的话，任意给出一个圆后，我都能保证圆的内接正方形里有点。
    我们构造这个函数f的基本思路是，构造一个将全体有理数映射到全体有理数的函数。注意到有理数是可数的，我们可以用这里的方法将全体有理数和自然数建立一一对应关系。也就是说，我们有了一个定义域为全体自然数、值域为全体有理数的一对一函数R(x)，它所对应的函数值是第x个有理数。下面我们开始着手定义我们要求的函数f(x)。函数f(x)的定义域是全体有理数，定义域里的每个x都可以表示成n/m的形式（化到最简），于是我们可以令f(x)=f(n/m)=R(m)。对于任意的y和d，在y±d里肯定存在一个有理数，假如按照上面的对应来看它是第m个有理数（即R(m)），下面我们就想办法说明我们总能够找到一个n，使得n/m在x±d的范围内。当然，如果运气不好m值很小的话我们就挂了，我们很自然地想到，这个m值应该越大越好，最好能重新定义一个值域为全体有理数的函数，对任一给定的有理数我们都能找出任意大的m对应到它。然后我们想到定义一个多对一的、定义域和值域都是自然数的函数H(x)：
x    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 …
H(x) 1  1  2  1  2  3  1  2  3  4  1  2  3  4  5 …

    重新定义f(x)=f(n/m)=R(H(m))，这样的话任意给定一个有理数，我们可以找到任意大的m使得R(H(m))等于这个有理数。当m足够大时，m(x-d)和m(x+d)之间一定会出现一个整数n，则此时n/m在x±d的范围内。
    但我们又遇到一个问题：要是找到的那个n始终不能和m互质（表明没化到最简）咋办？我的直觉是，这种极端的情况应该是不存在的，当m充分大时，总有一个满足要求的n/m出现。但我没有严格证明它。其实，我根本不需要去证明它；这个题目有趣就有趣在，我这个函数f是可以随便构造的。你或许在想，要是分母m为质数就好了。那好，我就可以强迫分母m为质数。定义一个定义域为全体质数，值域为全体正整数的函数P(x)，它表示x是第几个质数：
x    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 …
P(x) –  1  2  –  3  –  4  –  –  –  5  –  6  –  – …

    重新定义f(x)=f(n/m)=R(H(P(m)))，现在我们能够找到任意大的质数m使得R(H(P(m)))等于指定的有理数。当m足够大时，m(x-d)和m(x+d)之间一定会出现两个相邻的整数p和q，由于m是质数，p和q之间总有一个数与m互质（不可能都是m的整倍数），我们需要的n也就找到了。

满足要求的函数有很多。这只是其中一种构造方法。大家能不能再想一些更有趣的构造来？
来源：http://www.douban.com/group/topic/2561708/
参考网友yushih的解答

最近重新整理了日志Tag。如果你喜欢这篇文章，不要错过这里的惊奇数学事实，你会看到更多难以置信的数学结论。

    无穷个囚犯面向数轴的正方向依次就座，第i个囚犯坐在数轴上坐标为i的地方，他可以看见所有坐标大于i的囚犯头顶上的帽子。看守给每个囚犯戴上黑色或白色的帽子，然后依次叫每个囚犯猜测自己头上的帽子颜色，猜对了的予以释放。另外一点和原来不同的是，囚犯们不能听到其他人的猜测。另外注意到，由于每个人前面都有无穷多个人，因此囚犯们无法通过数他前面的人数来判断出自己的位置，于是我们不得不加上一句：每个人都知道他后面有多少人（即他是第几个被问的）。同样地，事先所有囚犯可以商量出一个策略。你认为这下囚犯们还有什么好办法没？
    这下囚犯已经不能通过自己的猜测来通风报信了，似乎每个人都只能瞎猜，任何人都无法保证自己能猜对。你相信吗，居然有这样的策略，它可以保证除了有限个囚犯之外，其他囚犯全部释放！
    考虑所有可能的颜色序列（你可以简单地想像成01串）。我们说两个颜色序列“无穷远相等”，如果经过了有限多项之后，余下的无穷多项完全相同（即存在某个数x，使得两个串在各自的第x位后面完全重合）。这种关系显然满足自反性、对称性和传递性，是一种等价关系。因此，按照这种有限位后对应相等的关系，我们可以把所有可能的颜色序列划分为一个个等价类。它们的交集为空（两个等价类如果有交集，由传递性它们立即并成了一个更大的等价类），并集为全集（若某序列不属于任何等价类，则它自己就是一个新的等价类），是全集的一个划分。你能想象出一个等价类大致是什么样子的吗？假如把同一个等价类里的所有序列对齐并排放在一起，你从前往后走过去的时候会发现这些序列“越来越相像”。你走得越远，你会发现越来越多的序列开始变得互相重合；当你走到无穷远时，所有的序列都变成一个样了。
    囚犯们事先在每一个等价类中选一个代表元，然后把所有等价类的代表元背下来。到时候，每个人都能够看到他前面无穷多个人的帽子颜色，并且知道他自己在整个序列的位置，于是能立即判断出他们现在所处的颜色序列在哪个等价类里。接下来，他们只需要按照事先背好的代表元来猜就行了。由“无穷远相等”的定义，经过有限次猜测后最终这个代表元会和他们所处的序列重合，于是除了前面有限多个人以外，以后无穷多个人都可以保证猜对。

    你是否觉得这种“策略”很不合理，虽然从逻辑上看每一步推理都是无懈可击的？有人认为，这是选择公理带来的悖论。选择公理是说，给你一系列的集合（可能有无穷多个），那么我们总可以在每一个集合里取出一个元素来。这并不是显然正确的。你不可以依次考虑每个集合，从里面随便取出一个元素来，因为集合个数有可能无穷多个（甚至不可数），这样的操作将永无止境，不允许出现在数学推理过程中。我们需要定义一套系统，使得它对于给定的每一个集合都适用，这样我们就可以“一下子”处理完所有的集合。换句话说，对于一组数量任意多的集合，我们需要定义一个函数f，使得对其中任一集合S，f(S)为S里的一个元素。我们称函数f为选择函数。例如，给出自然数集的所有子集，选择函数f可以定义为“集合中的最小元素”；给出实数集的所有有限长的区间，则选择函数f可以定义为“区间的中点”。但对于某些情况，目前还没有办法用之前已有的公理系统定义出合适的选择函数。比如，目前仍然不清楚，对于实数集的所有非空子集是否存在一个选择函数。但选择函数的存在是很多数学推理的前提假设。因此，我们有必要承认选择公理，构成新的公理体系（即ZFC公理体系）。于是在今后的数学推理中，我们可以假设存在这样一个超级选择函数f，它就是专门用来干这破事的。承认选择公理有可能推出一些与生活经验背道而驰的结论，最著名的就是Banach-Tarski悖论：你可以把一个三维球体分成有限多块，然后拼接组合成两个和原来一样大的球体。上面所提到的100囚犯问题加强版则是选择公理带来的另一个悖论。

参考资料：http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong （墙就是强）