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

    我一直很喜欢有各种惊异性质的奇怪函数，比如阶梯状的连续函数、只在一点连续的函数、任意小的区间所对应的值域都是整个实数域的函数等等。在这里面，最令人吃惊的是恐怕要数在平面上处处稠密的单值函数（其实前面那个函数显然也有这样的性质）。这样的函数打破了一维和二维之间的界线，启发人们重新思考稠密性的意义。不过，有人提到，这两个函数之所以在平面上稠密，是因为它们在平行于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…

    今天学到一个好玩的东西。仿照停机问题的研究方法，我们可以想出很多有趣的不可解问题。Gregory Chaitin曾经提出过下面这个问题。如果两段代码运行之后能够输出相同的结果，我们就称较短的代码比长一点的那个更简洁（注意，如果程序需要读入数据，读入的数据也算进代码长度）。对于一个指定的输出，一定存在一个“最简的”代码，它是所有能输出此内容的程序代码中最短的一个。在刚刚结束的TLE比赛中，参数选手拼了命地缩减每一个字符，写出来的代码一个比一个短。有人或许在想，这些代码究竟能短到什么程度？你如何才能知道你的代码已经不再有改进的空间了？受此启发，我们的问题出来了：你能否编写一个程序，使得该程序能够判断任意一段代码是否是最简的？
    Chaitin定理指出，上述问题是一个不可解问题，再牛的人也不可能编写出这样的程序。证明方式与大多数此类问题一样，都是采用反证加构造的方法证明的。你能想到这个证明方法吗？

Read more…

    概率论给我们带来了很多匪夷所思的反常结果，条件概率尤其如此。网络上每一次有人发帖提出与条件概率有关的悖论时，总会引来无数人的围观和争论，哪怕这些问题的实质都是相同的。
    来看两道简单的组合数学问题：

       1. 四个人打桥牌。其中一个人说，我手上有一个A。请问他手上有不止一个A的概率是多少？
       2. 四个人打桥牌。其中一个人说，我手上有一个黑桃A。请问他手上有不止一个A的概率是多少？

    这两个问题看起来很像，实际算法大不相同。在第一题问题中，

       手上一个A也没有 有 C(48,13) 种情况
       手上有至少一个A 有 C(52,13) – C(48,13) 种情况
       手上恰好有一个A 有 C(48,12) * 4 种情况
       手上有至少两个A 有 C(52,13) – C(48,13) – C(48,12) * 4 种情况

    根据条件概率公式，手上有超过一个A的概率为(C(52,13) – C(48,13) – C(48,12) * 4) / (C(52,13) – C(48,13)) = 5359/14498 ≈ 37%

Read more…

    上次说到维度时，有人提到了如何理解四维空间的问题。这是一个非常有趣的话题，可是我一直没有用心写一下。前段时间网上出了一部片子叫做Dimensions: a walk through mathematics，据称里面详细介绍了四维空间。我本以为推荐一下这个片子就能少写一篇又臭又长的日志了的，没想到下下来看了之后发现该片奇差，不了解四维空间的人看了半天估计还是不了解四维空间。最近放假比较闲，打算慢慢来扯一下。如果你以前从来没细想过四维空间的话，相信今天你会有一种超凡脱俗的感觉。
    现在，假设我是一个二维世界的人，我不能理解什么是“高度”，什么是“体”，什么是“空间”。你想向我描述三维世界中的立方体。你该怎么说呢？你或许会从立方体的展开图开始谈起：图(a)就是一个立方体的展开图，如果我们剪一个这种形状的纸板，我们可以把它折成一个正方体。我开始好奇了。

Read more…