趣题:随机选取两个无穷大的图,求两者相同的概率
假设我们俩各自独立地随机选取一个有无穷多个顶点的图(两点之间1/2的概率有边1/2的概率没有边).那么,我们俩选到相同的图的概率是多少?
令人难以置信,但想通了之后又异常显然的是,两个图相同的概率为1.并且,我可以精确地告诉你,这个相同的图是什么样子的.考虑这样一个无穷大的图,我们用自然数1, 2, 3, ...给所有顶点标号,然后如果y的二进制表达中的右起第x位为1,就在顶点x和顶点y之间连一条线.比如,顶点5就和顶点1,顶点3相连.我可以证明,我们俩都100%地会选取到上述这个图.
IBM Ponder This史上最难谜题:给出谜底猜谜面
2009年2月份IBM Po