我一直很喜欢有各种惊异性质的奇怪函数，比如阶梯状的连续函数、只在一点连续的函数、任意小的区间所对应的值域都是整个实数域的函数等等。在这里面，最令人吃惊的是恐怕要数在平面上处处稠密的单值函数（其实前面那个函数显然也有这样的性质）。这样的函数打破了一维和二维之间的界线，启发人们重新思考稠密性的意义。不过，有人提到，这两个函数之所以在平面上稠密，是因为它们在平行于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’+λ)（只保留和λ相同的位数），则该点必然在前面所说的范围内。
算法
密码学协议举例（五）：两个人能够在电话上打牌吗？
密码学的应用范围非常广泛。每一样简单的社交活动里都有很大的学问。考虑这样一个问题，两个人想通过一部电话打牌，但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议，并且保证游戏的公正性呢？
扑克牌的信息隐蔽性带来了很多与密码学协议相关的有趣问题。两个象棋大师可以在洗澡间一边冲澡一边大喊“炮八平五”、“马八进七”，一对围棋情侣可以在床上一边亲热一边呻吟“点三三”、“拆二”。等事情办完了，一盘精彩的棋局或许也就结束了。这些棋类游戏之所以可以“盲下”，就是因为在棋类游戏中，双方的局面信息都是完全公开的。不过，打牌就是另外一码事了。你说你出方片7，我怎么知道你有一个方片7？事先发牌？那谁来负责发牌呢？怎样发牌呢？难道我告诉你“发到你手中的是两张3一张5一张8一张9”？这样一看，两个人“盲打扑克牌”似乎是不可能的了，要么需要借助道具，要么需要第三者的帮助。不过，运用密码学知识，我们可以设计一套扑克牌协议，该协议能够实现随机的、隐蔽的、公平的发牌，并且不需要其它东西的帮助。我们以一手五张牌为例，说明如何实现“两人各摸五张牌”的程序。
经典证明：Chaitin定理 不可能编程判断代码的最简性
今天学到一个好玩的东西。仿照停机问题的研究方法，我们可以想出很多有趣的不可解问题。Gregory Chaitin曾经提出过下面这个问题。如果两段代码运行之后能够输出相同的结果，我们就称较短的代码比长一点的那个更简洁（注意，如果程序需要读入数据，读入的数据也算进代码长度）。对于一个指定的输出，一定存在一个“最简的”代码，它是所有能输出此内容的程序代码中最短的一个。在刚刚结束的TLE比赛中，参数选手拼了命地缩减每一个字符，写出来的代码一个比一个短。有人或许在想，这些代码究竟能短到什么程度？你如何才能知道你的代码已经不再有改进的空间了？受此启发，我们的问题出来了：你能否编写一个程序，使得该程序能够判断任意一段代码是否是最简的？
Chaitin定理指出，上述问题是一个不可解问题，再牛的人也不可能编写出这样的程序。证明方式与大多数此类问题一样，都是采用反证加构造的方法证明的。你能想到这个证明方法吗？
绝对是有史以来最酷的计算器！
TLE比赛结束 经典题目回顾
创意C/C++编程挑战赛Time Limit Exceeded结束，题目果然非常有创意。大家可以在这里看到比赛题目和获胜选手的代码。其中两道题很有意思，我特别喜欢。
一道叫做Compile Error的题目要求你写一个叫做multiply的类，里面包含一个mult(int a,int b)的函数，该函数用于打印出a和b的乘积。代码中不允许出现空格、“/”和“#define”。
第一个问题就是，定义一个类的语句是class multiply{…}，这个空格要怎么避免？只要你知道typedef int foo也可以写成int typedef foo，我们就可以利用typedef来消除空格，把类的定义写成class{…}typedef multiply。但这下后面又冒出一个空格来，这个空格怎么消呢？一个巧妙的方法就是利用int typedef foo,bar的语句，把类定义语句写成class{…}typedef*foo,multiply，其中*foo是一个不会用到的类型，但是它帮助我们奇迹般地消除了一个空格。巧妙利用星号可以消除很多空格，例如我们在定义mult函数时就可以写成void*mult(…){…}。最后一个难题就是，定义函数mult(int a,int b)，参数表里面的两个空格怎么办？其实办法依然很多。不少网友都用到了typeof，这样便可以把int a写成typeof(int)a了。完整的类定义如下：
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
在gcc下，即使警告全开，下面这个程序编译时也一声不吱。
#include <iostream>
using namespace std;
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
int main()
{
multiply foo;
foo.mult(23,67);
}