经典证明：扫雷是NP完全问题

2008 年 7 月 4 日 / 26 条评论

曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。
首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的这篇文章。

    上图就是一条带有Boolean值的线路。注意到x和x’中有且仅有一个有雷。如果（沿线路方向）前一个格子有雷，我们就说这条线路状态为True；反之如果后一个格子有雷，那么这条线路所传递的Boolean值就是False。每条线路的起始端都如下图左所示，其中符号*表示该格里必然有雷，x和x’中同样是有且仅有一个有雷，但到底是哪一个里面有雷谁也说不清楚。线路是可以拐弯的，如下图右所示，这可以保证转角后Boolean值相同。

经典证明：质数无穷多与两个更强的命题

2008 年 6 月 18 日 / 13 条评论

又回来更新啦！虽然还有两门课没考，但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚，结果考试时一看卷子，仍然没一道会的题目。不定项选择多选少选均不得分，都是些文学常识题，给四篇我从没见过的小说名字问哪些是第一人称叙事，或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
先强烈推荐一本好书。前几天在TopLanguage看到有牛人推荐Proofs from THE BOOK这本书，当即决定买了下来。这几天复习累了我都在看这本书，真的是很好很强大，里面汇集了很多著名问题的经典证明，包括很多我一直想找但没找到的证明。好了不多废话了，下面进入正题。

很早以前，我们曾经研究过质数，证明了质数有无穷多个。后来，我们又学到了另外两种证明质数无穷多的方法。这两种方法的基本思路相同：寻找一个无穷大的集合，里面的数两两互质。只用有限个质数明显不能得到无穷多个两两互质的数，于是我们立即可知质数必然有无穷多个。今天，我们将证明两个比质数无穷多更强的定理。这两个证明都出自Proofs from THE BOOK的第一章。

    定义函数π(x)为“小于等于x的质数有多少个”。无妨规定x为一个正整数。我们将用初等微积分方法证明当x趋于无穷时π(x)也趋于无穷并给出π(x)的一个下界。我们将说明，对于所有x，π(x)>=log(x)-1，即x以内的质数至少有log(x)-1个。
    为了说明这一点，让我们考虑所有不超过x的质数的倒数的等比级数(1 + 1/p + 1/p^2 + ..)的乘积，即。
    回忆等比级数的公式，则我们有：

    第二行的一些变换非常巧妙。第二行中间的不等号是一个关键，用到了一个基本事实：第k个质数显然比k大。最后的连乘中前一项的分子和后一项的分母正好抵消，最后消完了就只剩了一个π(x)+1。
    另一方面，想像一下把(1+1/2+1/4+…)(1+1/3+1/9+…)(1+1/5+1/25+…)…展开的样子，很显然展开后的每一项都是一个所有质因子都不大于x的数的倒数，即Σ(1/m)，其中m取所有仅含1..x范围内的质因子的数。显然，原本就比x小的数，其质因子当然不可能超过x，这就是说从1到x的所有正整数都是属于m的。利用一些微积分的基本知识，我们可以立即得出Σ(1/m) >= 1+1/2+1/3+…+1/x >= log(x)。地球人都知道，log(x)是没有上界的，于是质数的个数也没有上界。
    这里还有一个类似的问题，大家可以对照着看看。

经典证明：Cantor-Bernstein-Schroeder定理

2008 年 6 月 11 日 / 15 条评论

明天考英语，单词还没背。先冒死更新一个^_^
我们称一个从集合A到集合B的映射是“单射”的，如果A中的任两个相异元素都不会映射到B里的同一个元素。如果一个A→B的映射是单射的，并且B里的所有元素都被射了（满射），那么这个映射就是“双射”的。Cantor-Bernstein-Schroeder定理是说，假如存在一个从集合A到集合B的单射函数f，以及一个从集合B到集合A的单射函数g，那么A与B之间一定存在一个双射函数（即能建立起一一对应的关系，两个集合有相等的势）。这个结论并不是显然的。对于无穷集合，我们可以构造出很多这样的例子，两个映射A→B和B→A都是单射，但都不是满射的。例如，给定一个正方形和正方形外的一条直线，把正方形放到直线上滚一圈所形成的对应关系是一个从正方形上的所有点到直线上的点的一个单射函数，而连接直线上的点和正方形一边中点后与正方形的另一个交点构成了一个从直线到正方形的单射关系（如图）。那么，根据Cantor-Bernstein-Schroeder定理，我们一定可以找到一种函数，使得直线上的所有点和正方形上的所有点有一一对应的关系。

趣题：构造1到n-1的排列使得前缀和模n仍为一个排列

2008 年 6 月 2 日 / 5 条评论

对于哪些n，存在一个1到n-1的排列S_1, S_2, …, S_n-1，使得T_1, T_2, …, T_n-1也是一个1到n-1的排列，其中，

T_1 = S_1 mod n,
T_2 = (S_1 + S_2) mod n,
T_3 = (S_1 + S_2 + S_3) mod n,
…….
T_n-1 = (S_1 + S_2 + … + S_n-1) mod n.

《什么是数学》读书笔记（二·上）：从自然数到实数

2008 年 5 月 22 日 / 13 条评论

今天，我们将从一系列公理开始，从自然数的产生一直说到实数理论的完善。你或许会对数学的“科学性”有一个新的认识。注意，本文的很大一部分内容并非直接来源《什么是数学》，这篇文章可以看作是《什么是数学》中有关章节的一个扩展。

    自然数是数学界中最自然的数，它用来描述物体的个数，再抽象一些就是集合的元素个数。在人类文明的最早期，人们就已经很自然地用到了自然数。可以说，自然数是天然产生的，其余的一切都是从自然数出发慢慢扩展演变出来的。数学家Kronecker曾说过，上帝创造了自然数，其余的一切皆是人的劳作。 (God made the natural numbers; all else is the work of man.)
    随着一些数学理论的发展，我们迫切地希望对自然数本身有一个数学描述。从逻辑上看，到底什么是自然数呢？历史上对自然数的数学描述有过很多的尝试。数学家Giuseppe Peano提出了一系列用于构造自然数算术体系的公理，称为Peano公理。Peano公理认为，自然数是一堆满足以下五个条件的符号：
   1. 0是一个自然数；
   2. 每个自然数a都有一个后继自然数，记作S(a)；
   3. 不存在后继为0的自然数；
   4. 不同的自然数有不同的后继。即若a≠b，则S(a)≠S(b)；
   5. 如果一个自然数集合S包含0，并且集合中每一个数的后继仍在集合S中，则所有自然数都在集合S中。（这保证了数学归纳法的正确性）

形象地说，这五条公理规定了自然数是一个以0开头的单向有序链表。
自然数的加法和乘法可以简单地使用递归的方法来定义，即对任意一个自然数a，有：
a + 0 = a
a + S(b) = S(a+b)
a · 0 = 0
a · S(b) = a + (a·b)

其它运算可以借助加法和乘法来定义。例如，减法就是加法的逆运算，除法就是乘法的逆运算，“a≤b”的意思就是存在一个自然数c使得a+c=b。交换律、结合率和分配率这几个基本性质也可以从上面的定义出发推导出来。
Peano公理提出后，多数人认为这足以定义出自然数的运算，但Poincaré等人却开始质疑Peano算术体系的相容性：是否有可能从这些定义出发，经过一系列严格的数学推导，最后得出0=1之类的荒谬结论？如果一系列公理可以推导出两个互相矛盾的命题，我们就说这个公理体系是不相容的。Hilbert的23个问题中的第二个问题就是问，能否证明Peano算术体系是相容的。这个问题至今仍有争议。