Matrix67 |
2009-11-14 17:29 | 
你相信吗？对于任意一个可数集，总能找出不可数个子集，使得从中任取两个集合，其中一个都是另一个的真子集。乍看之下，这似乎是不可能的。如果任两个集合之间都具有“其中一个是另一个的真子集”的关系，那它们就能构成一个“集合序列”（准确地说是全序关系），使得每个集合都是由它前面那个集合添加进若干元素得到；换句话说，我们能通过不断往一个空集中添加新的元素依次得到所有这些集合。但是如果这些集合中的元素就只有可数个，那这个“集合序列”中怎么会有不可数个集合呢？然而，涉及到无穷的问题总是那样违背直觉。下面我们只用三行字就能说明，这个命题的的确确是成立的。
Sep
2
某日夜里我突发奇想，想到用分形图形来表示各种几何级数，于是写下了上一篇日志。日志发出后我收到了相当多的回复，很多网友告诉我说，这篇日志还留下了很多空白，大有扩展的潜力和推广的空间，非常具有启发性。网友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。
Jul
20
假设我们俩各自独立地随机选取一个有无穷多个顶点的图（两点之间1/2的概率有边1/2的概率没有边）。那么，我们俩选到相同的图的概率是多少？
令人难以置信、但想通了之后又异常显然的是，两个图相同的概率为1。并且，我可以精确地告诉你，这个相同的图是什么样子的。考虑这样一个无穷大的图，我们用自然数1, 2, 3, ...给所有顶点标号，然后如果y的二进制表达中的右起第x位为1，就在顶点x和顶点y之间连一条线。比如，顶点5就和顶点1、顶点3相连。我可以证明，我们俩都100%地会选取到上述这个图。
Apr
6
你认为，是否有可能把全体正整数染成红蓝二色，使得不存在无穷等差数列，数列中的所有数都是一种颜色？如果你认为存在这样的染色方案，请给出一个构造方法；如果你认为不存在，证明之。在看下面的答案之前，不妨先仔细思考一下。
事实上，满足题意的染色方案是存在的，构造方法非常简单，非常直接，非常暴力。显然，无穷等差数列只有可数个，不妨把它们分别叫做A_1, A_2, A_3, ...。现在，如果我们能够构造两个数列r_1, r_2, r_3, ...和b_1, b_2, b_3...，使得对于每一个i，r_i和b_i都在数列A_i中，并且r数列中的每个数都和b数列中的所有数都不相同。这样，把r数列中的所有数染成红色，把b数列中的所有数染成蓝色（其它未出现的数随意染色），就能保证每个无穷等差数列都包含了至少两种颜色。
而这样的r数列和b数列显然存在，因为每一次选择新的r_i和b_i时，无穷数列A_i中都只有有限个数不能选，因此r_i和b_i永远都有选的。
Update: 地基层网友给出了一个更巧妙、更简单的构造方法：对全体正整数倍长间隔染色，即把1染成红色，2和3染成蓝色，4到7染成红色，8到15染成蓝色……。显然，当染色区间的长度大于公差时，等差数列最终都将一截一截地落在不同的染色区间中。
Apr
5
去年就看过Proofs from THE BOOK第一章中的素数无穷多的拓扑学证明，不过当时似乎并没有看懂。今天看到cut-the-knot的一篇新文章，又把Proofs from THE BOOK拿出来翻了一下，终于看明白了，果然是一个令人拍案叫绝的经典证明，可谓又一神来之笔。
定义N(a,b) = {a + nb| n∈Z}，例如N(1,3)就等于{..., -5, -2, 1, 4, 7, ...}。每一个N(a,b)实质上都是一个以b为公差的“双向无限等差数列”。我们说整数集Z上的一个子集S是开的，如果集合S为空，或者对于任意一个a∈S，总能找到一个b>0使得N(a,b)⊆S。形象地说，开集的意思就是，集合中的每一个元素都能在集合内扩展出一个无限长的双向等差数列。我们又称一个集合S是闭的，如果它是某个开集的补集。
显然，有限个开集的并集仍然是开集。
假设S_1和S_2都是开集，如果a∈S_1∩S_2，并且N(a,b1)⊆S_1，N(a,b2)⊆S_2，那么S_1∩S_2中有一个公差为b1*b2的含a的双向无限等差数列，也即a∈N(a, b1*b2)⊆S_1∩S_2。这说明，有限个开集的交集仍然是开集。
再假设C_1和C_2都是闭集。由De Morgan定律，C_1和C_2的并集就相等于它们各自的补集相交后再取补集，由定义可知它们的补集都是开集，而由上面的结论可知开集的交集仍是开集。于是，C_1和C_2的并集是某个开集的补集，这说明闭集的并仍然是闭集。类似地，闭集的交集相当于补集的并集的补集，它也仍然是闭的。
还有两点值得引起我们注意：
1. 任意非空开集都是无穷的。这由定义可以直接看出来。
2. 任一双向无限等差数列N(a,b)既是开集又是闭集。由定义可知N(a,b)是开集，而同时N(a,b)又可以看作是N(a+1,b)∪N(a+2,b)∪N(a+3,b)∪...∪N(a+b-1,b)的补集，这是有限个开集的并集的补集，说明N(a,b)也是闭集。
Mar
3
对于数轴上的一个点集，如果说在集合中任意两点之间都能够找到该集合中的另一个点，我们就说该点集处处稠密。例如，全体有理数集合就是稠密的，任意接近的两个有理数之间都存在其它的有理数（比如它们的算术平均值）。这样看来，两个处处稠密的点集似乎是不能共存的，但实际情况并非如此。我们将会看到越来越牛B的例子，它们将让我们对稠密性有一个全新的认识。
1. 在数轴上找出两个处处稠密的点集，它们互不相交。
很简单。全体有理数和全体无理数就是满足条件的两个集合。
2. 在数轴上找出两个处处稠密的不可数点集，它们互不相交。
很狡猾。集合A取全体正有理数和全体负无理数的并集，集合B取全体正无理数和全体负有理数的并集，这两个集合即可满足条件。
3. 在数轴上找出无穷多个处处稠密的点集，它们两两不相交。
令P_i表示第i个素数。则集合S_i := { √P_i + r| r为有理数 }满足条件。为了证明它们两两不相交，假设r_1 + √P_m = r_2 + √P_n，于是(r_1 - r_2)^2 = (√P_n - √P_m)^2，可得√P_m * P_n = ( P_m + P_n - ((r_1 - r_2)^2) )/2。两个素数的乘积的平方根是一个有理数，这显然是荒谬的（很多证明根号2是无理数的方法都可以证实这一点，例如这里的证法http://www.matrix67.com/blog/archives/206）。
Feb
26
如果删除字符串A中的若干字母可以得到字符串B，我们就说A包含B（熟悉相关概念的网友可能知道，有一个准确的说法叫做“B是A的子序列”，但为了避免和后面的“序列”混淆，我们不用这种说法）。例如，字符串“matrix”包含了“mix”，也包含“ati”，但不包含“it”。字符串序列aaaaa, ab, bbaa, baaaa, aa, bbacc, cbcacc, bb中的每个字符串都不包含它前面的任何一个字符串，我们称这样的字符串序列为“非生成序列”（我自己取的名字，意思是说任一字符串都不能由前面的项通过添加字母生成出来）。我们可以构造出任意长的非生成序列，例如字符串长度严格递减的序列，或者所有不同的长度为n的字符串。现在的问题是，你能构造出一个无穷长的非生成序列吗？当然，你不能使用无穷多种字母来达到这一点。
