同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了另一篇论文，给出了实数集不可数的另一种证明方法。此后，这个简单到不可思议的证明不断地震撼着每一个初学集合论的人：

    事实上，实数区间 (0, 1) 就已经是一个不可数的集合了。换句话说，你绝不可能用“第一个数是某某某，第二个数是某某某”的方式把 0 到 1 之间的所有实数一个不漏地列举出来。我们大致的证明思路是，假设你把实数区间 (0, 1) 里的所有数按照某种顺序排列起来，那么我总能找到至少一个 0 到 1 之间的实数，它不在你的列表里，从而说明你的列表并不全。把你的列表上的数全写成 0 到 1 之间的无限小数（如果是有限小数，可以在其后面添加数字 0 ，把它变成无限小数）：

a₁ = 0.0147574628...
a₂ = 0.3721111111...
a₃ = 0.2323232323...
a₄ = 0.0004838211...
a₅ = 0.0516000000...
.........

    那么我就构造这么一个小数，小数点后第一位不等于 a₁ 的第一位，小数点后第二位不等于 a₂ 的第二位，总之小数点后第 i 位不等于 a_i 的第 i 位。这个数属于实数区间 (0, 1) ，但它显然不在你的列表里，因为它和你列表里的每一个数都有至少一位是不同的。这样，我们就证明了实数区间是不可数的。

查看更多 »

    这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题：是否有可能在平面上画不可数个不相交的 8 ？答案是否定的。证明方法非常简单。对于任意一个 8 字形，在两个洞里各取一个有理点 P 、 Q （由于平面上的有理点是稠密的，这是总能办到的），则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交，因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的，因此 8 字形的数量也是可数的。

    注意到，平面上显然能够容下不可数个不相交的直线段，也显然能够容下不可数个不相交的圆（比方说一系列同心圆）。在 Mathematical Puzzles 一书里， Peter Winkler 提出了这样一个问题：我们能在平面上写下不可数个不相交的字母 Y 吗？

查看更多 »

    当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题（eight queens puzzle）时，他恐怕怎么也想不到，100 多年以后，这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单：把八个皇后放在国际象棋棋盘上，使得这八个皇后互相之间不攻击（国际象棋棋盘是一个 8×8 的方阵，皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步）。虽然这个问题一共有 92 个解，但要想徒手找出一个解来也并不容易。下图就是其中一个解：

    八皇后问题有很多变种，不过再怎么也不会比下面这个变种版本更帅：请你设计一种方案，在一个无穷大的棋盘的每一行每一列里都放置一个皇后，使得所有皇后互相之间都不攻击。具体地说，假设这个棋盘的左下角在原点处，从下到上有无穷多行，从左到右有无穷多列，你需要找出一个全体正整数的排列方式 a1, a2, a3, ... ，使得当你把第一个皇后放在第一行的第 a1 列，把第二个皇后放在第二行的第 a2 列，等等，那么任意两个皇后之间都不会互相攻击。

查看更多 »

    今天看到一个有趣的证明，来源在这里。

    Cantor 集是一个简单而又神奇的分形图形。把 [0, 1] 三等分，挖去中间那一段（即挖去 (1/3, 2/3) ），然后把剩下两段也都分别进行三等分，并挖去各自中间的一段。这样无限地进行下去，最后得到的极限点集就是 Cantor 集了（上面那张图不是分割线，是 Cantor 集的一个示意图）。我们通常把 Cantor 集记作 C 。Cantor 集具有很多神奇的性质：它的 Lebesgue 测度为 0，但它却包含有不可数个点；它里面的每个点都不是孤点，但它却又是无处稠密的。你可以在这里看到一些具体的分析。

    Cantor 集还有很多其他的性质。若 A 、 B 是两个集合，定义 A + B = {a + b | a ∈ A 并且 b ∈ B} ，也就是 A 中的某个元素与 B 中的某个元素相加可能得到的所有结果。下面我们将证明，C + C = [0, 2]。

查看更多 »

考虑这么一个游戏：不断在区间 [0, 1] 中概率均等地选取随机数，直到所取的数第一次比上一个数小。那么，平均需要抽取多少个随机数，才会出现这样的情况？

 
答案：记 P_i 为第 i 次才取到小于前一个数的数的概率。则我们要求的就是 P₁ + 2 * P₂ + 3 * P₃ + 4 * P₄ + … 。妙就妙在下面这个变形（在继续看下去之前你能想到吗）：

查看更多 »

    给你一张纸，要求你在上面画尽可能多的圆圈，使得所有圆圈都不相交。你最多能画多少个？
    显然，你可以画无穷多个圆圈。事实上，你可以画不可数个圆圈——只需要画出一系列半径长均为无理数的同心圆即可。由于每两个无理数之间都夹有有理数，因此任意两个圆都没挨在一块儿。

    给你一张纸，要求你在上面画尽可能多的叉，使得所有的叉都不相交。你最多能画多少个？
    你可以画无穷多个不相交的叉。画法有很多，下图便是一种方案：

    现在问题来了：你能在纸上画出不可数个叉吗？如果可以，请给出一种方案；如果不行，证明之。

查看更多 »

    你相信吗？对于任意一个可数集，总能找出不可数个子集，使得从中任取两个集合，其中一个都是另一个的真子集。乍看之下，这似乎是不可能的。如果任两个集合之间都具有“其中一个是另一个的真子集”的关系，那它们就能构成一个“集合序列”（准确地说是全序关系），使得每个集合都是由它前面那个集合添加进若干元素得到；换句话说，我们能通过不断往一个空集中添加新的元素依次得到所有这些集合。但是如果这些集合中的元素就只有可数个，那这个“集合序列”中怎么会有不可数个集合呢？然而，涉及到无穷的问题总是那样违背直觉。下面我们只用三行字就能说明，这个命题的的确确是成立的。

查看更多 »

    某日夜里我突发奇想，想到用分形图形来表示各种几何级数，于是写下了上一篇日志。日志发出后我收到了相当多的回复，很多网友告诉我说，这篇日志还留下了很多空白，大有扩展的潜力和推广的空间，非常具有启发性。网友morrowind在原日志第29楼评论说，大图形里面放置若干个相似的小图形时，并不一定要对应边与对应边相拼。考虑一个边长分别为1和根号5的矩形，它能够轻易地分成五个相同的小矩形，并且每一个都和原来的相似。这样的话，我们便又能递归地表示(1/5)^n了。只要能够递归地表示出(1/5)^n，从图形上我们总可以得出Σ(1/5)^n=1/4的结论，因为在每一个尺度下总有四个未被继续分割的区域，其中染色的区域始终占据了1/4。
    12楼的est用一个极其简单的式子给出了Σ(1/5)^n=1/4的证明：在五进制中，0.1 + 0.01 + 0.001 + 0.0001 + ... = 0.11111...，这恰好就说明了1/5 + 1/25 + 1/125 + .. = 1/4。上述两套证明方案对所有大于2的正整数n都成立，并且仔细思考你会看出它们的本质是相同的：0.11111...就是0.44444...的1/4，因为在每一个小数位上前者都是后者的1/4。

查看更多 »