多年以前，要想进入莫斯科国立大学的数学系，你必须通过四项入学考试；头两个都是数学考试，一个笔试，一个面试。在面试中，学生和考官都是一对一的，考官可以自由向学生提出任何他喜欢的问题。那时，为了筛选出他们不想要的应试者（主要是犹太人），很多考官都会出一些题目描述简单有趣、解答过程极其巧妙而又出人意料的问题。这些问题极具杀伤力，民间戏称其为“棺材问题”(coffin problems)。下面这个问题就是其中一个“棺材问题”：
考虑一个空间四边形A1A2A3A4，它的四条边A1A2, A2A3, A3A4, A4A1都与一个给定的球相切。求证，这四个切点共面。
为了更好地理解这个问题，考虑一个菱形的钢架沿对角线折叠，或者一个正四面体钢架去掉相对的两条棱。把这个空间四边形当成一个碗去接一个球，你会发现这个球卡在空间四边形中掉不下去了，此时它与四条边都相切。凭借我们的生活经验，我们很容易提出这个猜想：四个切点是共面的。
证明
趣题：选取最少的质数集合构成发散的部分调和级数
调和级数是指无穷级数1 + 1/2 + 1/3 + 1/4 + …，即取遍所有正整数n所得到的Σ1/n。虽然n趋于无穷时1/n趋于0，但这个无穷级数却是发散的。一个经典的证明是，把1/3和1/4都缩小到1/4，把1/5、1/6、1/7和1/8都缩小成1/8，把1/9到1/16这8个数全部缩小为1/16，以此类推，这样就可以得到无穷多个1/2，它们的和显然是无穷大的。
现在，让我们把所有的质数划分为若干个子集，其中质数p属于编号为floor(p/1000)的那个子集（floor()是取下整的意思）。现在，你可以用这样的方式来定义一个“部分的”调和级数：先选出一些质数集合出来，然后列出所有这样的数，它所有的质因子都落在你选的集合里。显然，这样的数有无穷多个，它们的倒数和就形成了一个部分调和级数。例如，选择子集①和子集②，我们可以得到一个无穷级数Σ1/n，其中n取所有这样的数，它可以表示为大于等于1000小于3000的质数的乘积。
前面我们已经看到，选择所有的集合所构成的无穷级数是发散的。现在的问题是，要想得到一个发散的级数，最少需要选取多少个集合？
分享一些有趣的面试智力题（上）
偶然进了这个页面，看到几个原来没见过的面试智力题。顺带也翻译一些比较少见、可能有人没见过的题目写在这里。有几个题目在国内流传相当广，什么n个人怎么分饼最公平，屋里的三个灯泡分别由哪个开关控制，三架飞机环游世界，用火柴和两根绳子测量45分钟之类的题目，火星得已经可以考古了，这里就不再说了。个别题目本Blog原来有过详细的介绍，这里也不再提了。
1. 考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？
答案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。
2. 用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单词本身又被转回来了。
3. 用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位（例如，”abcdefg”移动3位就变成了”defgabc”）。
答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。
4. 一个矩形蛋糕，蛋糕内部有一块矩形的空洞。只用一刀，如何将蛋糕切成大小相等的两块？
答案：注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半，它们的差当然也是相等的。
5. 一块矩形的巧克力，初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1×1的小巧克力？
答案：N x M – 1次显然足够了。这个数目也是必需的，因为每掰一次后当前巧克力的块数只能增加一，把巧克力分成N x M块当然需要至少掰N x M – 1次。
Read more…
《什么是数学》读书笔记（一）：反证法、数学归纳法与唯一分解定理
期中告一段落。除了下下星期要交的现文史论文以外，最近似乎又清闲了不少，又有功夫在这里写点东西了。当然，我宝贵的时间也没有荒废在论文、作业和考试上。几乎每一堂古汉课和现文史课我都在读《什么是数学》，进度算是相当快了。这可能是我近几年读的所有书中给我带来的收获最大的一本。最近好几个人问我，有什么牛B一点的数学书没。我毫不犹豫地脱口而出，《什么是数学》。如果我要去一个荒岛上，只能带三本书，我会选择《算法导论》、《组合数学》和《什么是数学》。如果叫我舍弃一样，我估计会扔掉《组合数学》。如果还得再丢弃一本，我只好忍痛丢下《算法导论》了。
读《什么是数学》的收获太多了。在这里，我只更新一些我原来不知道，又很有趣的东西。如果你希望迅速对此书有一个全面的了解，千万不要错过dd牛的《什么是数学》笔记。
阅读《什么是数学》的前面几章时，你经常会跟随着书中的文字重新看待一个显而易见的结论，然后对这个结论有了一个全新的认识。比如，书中曾提到，为什么数学归纳法是合理的？我已经知道n=1时结论成立，也知道若n=k成立则n=k+1结论也成立，那么对于任意一个给定的正整数t，n=t时的结论是成立的，因为经过有限次迭代后最终我们总可以到达n=t的情况。但是，为什么我们敢断言对所有这无穷多个n，结论都是成立的？显然，你不能说“我们可以迭代无穷多次”，一个有限的证明过程当然不允许有无限多个步骤。因此，为了说明对于所有正整数n结论都成立，我们不得不使用反证法把“无穷”变成“有穷”。我们假设对于某些n，这个结论是不成立的。那么，这里面一定存在一个最小的数p，它使得结论不成立。由于我们已知n=1时结论成立，因此p一定是大于1的。但n=p是“最早”使结论不成立的情形，因此n=p-1时结论一定为真。这就与我们已知的第二个条件“若n=k成立则n=k+1结论也成立”矛盾了。因此我们说，对于所有正整数n，结论都是成立的。
这个推理过程中用到了另一个显而易见的结论：对于一个非空的正整数集C，C中一定存在一个最小的元素。这又是为什么呢？你可能会说，废话，把所有元素拿出来两个两个的比，一定能比出一个最小的数来。这种说法是错误的。注意到集合C有可能有无穷多个元素，你是比不完的。为了更清晰地认识这个结论，我们只需要注意到，如果把条件换成“有理数集C”或者“实数集C”，结论就不再成立了，因为集合{1, 1/2, 1/3, 1/4, …}显然不存在一个最小的数。可以看到，上述结论是否成立是和数的稠密性紧紧相关的。事实上，为了说明正整数集C中存在最小元素，我们任意从集合中取出一个元素n，那么1, 2, …, n这有限多个数当中一定存在一个最小的数，它在这个集合C中。它就是整个集合的最小数。对于稠密的有理数点和实数点，这个证明显然不再适用。
Read more…
趣题：对数字进行编码使其按字典序排列后仍然有序
如果你经常使用“file5.txt”、“梁静茹23.mp3”、“AdultVideo153.avi”一类的文件名，你会发现在给文件名排序时，这种命名方式存在很大的弊端。很大一部分程序直接用字典序给文件名排序，因此file10.txt会排到file2.txt前面，尽管事实上10比2大。你是否想过，有没有什么办法能给数字编码，使得它们按字典序排序后仍然保持原有的大小顺序，并且编码的方法足够简单，编码之后原来的数字仍可以一目了然？一种简单的方法就是加前缀0，这样就保证了002在010前面，file005.txt也不会排到file100.txt的后面。它有一个缺点就是，你必须预先知道需要编码的数字最多有多少位，否则一旦新添进一个位数更多的数，前面所有的数必需要全部重新编码（加更多的前缀0）。另一个比较明显的缺点就是，这种编码方式过于冗长，添加进去的数字0最多可能与最大数的位数相当，多数情况下都远远超过了待编码的数自身的长度。我们更希望，编码时添加进去的“辅助码”不要超过这个数字本身的长度。由于数字n本身的长度是log(n)，因此我们需要保证冗余部分不超过log(n)。你能找到满足这些条件的一种编码方式吗？
注意到，当数字位数相同时，数值小的数按字典序排列时也排在前面。问题的关键就是，你需要找到一种编码方式，它可以标识出数字的位数，并且这种标识可以保证数字按位数从小到大排序。于是我们想到用“一进制编码”为每一个数加上一个“位数标识”。我们在每个数前面加上和这个数字本身的位数一样多的”1″，中间用一个”0″隔开。这样，所有三位数都是1110???的形式，所有四位数都是11110????的形式，这样按字典序排序时，三位数一定都排在四位数的前面。对应的解码方法也相当简单，只需要取第一个”0″后面的数字就行了。忽略常数的话，这种编码方式的冗余长度为log(n)，和数字本身的长度相当，基本上符合我们的要求。