趣题:对全体正整数红蓝二着色使之不含单色无穷等差数列

    你认为,是否有可能把全体正整数染成红蓝二色,使得不存在无穷等差数列,数列中的所有数都是一种颜色?如果你认为存在这样的染色方案,请给出一个构造方法;如果你认为不存在,证明之。在看下面的答案之前,不妨先仔细思考一下。

    事实上,满足题意的染色方案是存在的,构造方法非常简单,非常直接,非常暴力。显然,无穷等差数列只有可数个,不妨把它们分别叫做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染成蓝色……。显然,当染色区间的长度大于公差时,等差数列最终都将一截一截地落在不同的染色区间中。

Read more…

经典证明:素数无穷多的拓扑学证明

    去年就看过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)也是闭集。

Read more…

再谈稠密性:令人吃惊的稠密集及其交集

    对于数轴上的一个点集,如果说在集合中任意两点之间都能够找到该集合中的另一个点,我们就说该点集处处稠密。例如,全体有理数集合就是稠密的,任意接近的两个有理数之间都存在其它的有理数(比如它们的算术平均值)。这样看来,两个处处稠密的点集似乎是不能共存的,但实际情况并非如此。我们将会看到越来越牛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)。

Read more…

趣题:构造无穷长的字符串序列使每一项都不包含它前面的项

    如果删除字符串A中的若干字母可以得到字符串B,我们就说A包含B(熟悉相关概念的网友可能知道,有一个准确的说法叫做“B是A的子序列”,但为了避免和后面的“序列”混淆,我们不用这种说法)。例如,字符串“matrix”包含了“mix”,也包含“ati”,但不包含“it”。字符串序列aaaaa, ab, bbaa, baaaa, aa, bbacc, cbcacc, bb中的每个字符串都不包含它前面的任何一个字符串,我们称这样的字符串序列为“非生成序列”(我自己取的名字,意思是说任一字符串都不能由前面的项通过添加字母生成出来)。我们可以构造出任意长的非生成序列,例如字符串长度严格递减的序列,或者所有不同的长度为n的字符串。现在的问题是,你能构造出一个无穷长的非生成序列吗?当然,你不能使用无穷多种字母来达到这一点。

Read more…

平面上处处稠密但在平行于坐标轴的直线上无处稠密的点集

    我一直很喜欢有各种惊异性质的奇怪函数,比如阶梯状的连续函数只在一点连续的函数任意小的区间所对应的值域都是整个实数域的函数等等。在这里面,最令人吃惊的是恐怕要数在平面上处处稠密的单值函数(其实前面那个函数显然也有这样的性质)。这样的函数打破了一维和二维之间的界线,启发人们重新思考稠密性的意义。不过,有人提到,这两个函数之所以在平面上稠密,是因为它们在平行于x轴的直线上都是稠密的。我们自然开始设想,有不有可能在平面上找到这样一个点集,它在平面上处处稠密,但在任意一条平行于坐标轴的直线上都无处稠密呢?
    这是可以办到的。为了简便起见,我们只考虑平面区域[0,1]×[0,1]上的点集。让我们考虑由所有满足以下条件的点(x,y)所组成的点集:x和y都是有限小数,并且小数位数是相同的。例如,点(0.0516, 0.1025)就属于这个点集,但(0.23, 0.1001)就不属于这个点集,(1/3, π/6)就更不属于该点集了。显然,对于任何一个有限小数x’,直线x=x’上都只有有限多个点;类似地,对于任意一个有限小数y’,直线y=y’上都只有有限多个点。因此,该点集在所有平行于坐标轴的直线上都无处稠密。有趣的是,该点集在整个平面区域内却处处稠密。在任意小的区间x’-ε≤x≤x’+ε,y’-ε≤y≤y’+ε中,总存在一对小数位数相同的x和y。我们只需要写出一个比ε更小的有限小数λ,然后取(x’+λ, y’+λ)(只保留和λ相同的位数),则该点必然在前面所说的范围内。

Read more…