这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题：是否有可能在平面上画不可数个不相交的 8 ？答案是否定的。证明方法非常简单。对于任意一个 8 字形，在两个洞里各取一个有理点 P 、 Q （由于平面上的有理点是稠密的，这是总能办到的），则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交，因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的，因此 8 字形的数量也是可数的。
注意到，平面上显然能够容下不可数个不相交的直线段，也显然能够容下不可数个不相交的圆（比方说一系列同心圆）。在 Mathematical Puzzles 一书里， Peter Winkler 提出了这样一个问题：我们能在平面上写下不可数个不相交的字母 Y 吗？
给定 n 个村庄的位置，要想把他们全部连通，最少需要修建多长的公路？这个问题被称为 Steiner 问题，是由数学家 Jakob Steiner 提出来的。注意，和最小生成树不同的是，公路是可以在中间汇合、分岔的。目前已经知道，Steiner 问题是 NP-hard 的，在规模很大的情况下，不能有效地得出最优解来。
然而，大自然却是无敌的，它可以迅速秒杀这样的难题。由于肥皂膜总会试图让自己的表面积最小，利用肥皂膜实验，我们可以轻易获得 Steiner 问题的解。我在很多书上都看到过肥皂膜实验的方法，不过却从没见过真正的实验视频。今天我终于看到了这样的视频，把它搬进墙来，和大家分享。这个视频也很好地解释了一个普遍存在的误区：说肥皂膜实验一举解决了 NP 问题是不恰当的，因为这个实验只能找到极小值，并不能找到最小值，运气不好的话，实验结果会是失败的。
一个公司里有 n 个员工，其中某些员工之间有“好友”的关系（这是一个对称的关系）。每天早晨来到公司，员工们都会从茶和咖啡中选择一样作为早饮。此时，每个员工都会观察自己的朋友们都在喝啥：如果超过一半的人都在喝茶，第二天他自己也会跟着喝茶；如果超过一半的人都在喝咖啡，第二天他自己就会跟着喝咖啡；如果喝茶喝咖啡的人数各占一半（仅当他有偶数个朋友时才会发生这种情况），则第二天他的决策不变，继续喝自己今天喝的东西。
由于 n 个员工一共只能产生 2n 种不同的早饮组合，因此总有一天大家喝的东西会和过去的某一天一模一样，从而产生循环。证明：循环的长度不超过 2 。
某公司有 n 间办公室。每间办公室都有一盏灯，拉动它的开关即可改变电灯的状态。某些办公室之间存在“业务相关”的关系（这是一个对称的关系）。一个办公室可以和 0 到任意多个办公室相关。愚人节那天，有人在大家上班之前偷偷对办公室的电灯开关做了手脚：拉动任何一个办公室的电灯开关，都会同时改变该办公室以及所有相关办公室的电灯状态。初始时，所有灯都是关着的。证明：等到大家来上班后，总能用有限次的开关，最终把所有办公室的灯都打开。
数学之美不但体现在漂亮的结论和精妙的证明上，那些尚未解决的数学问题也有让人神魂颠倒的魅力。和 Goldbach 猜想、 Riemann 假设不同，有些悬而未解的问题趣味性很强，“数学性”非常弱，乍看上去并没有触及深刻的数学理论，似乎是一道可以被瞬间秒杀的数学趣题，让数学爱好者们“不找到一个巧解就不爽”；但令人称奇的是，它们的困难程度却不亚于那些著名的数学猜想，这或许比各个领域中艰深的数学难题更折磨人吧。
作为一本数学趣题集， Mathematical Puzzles 一书中竟把仍未解决的数学趣题单独列为一章，可见这些问题有多么令人着迷。我从这一章里挑选了一些问题，在这里和大家分享一下。这本书是 04 年出版的，书里提到的一些“最新进展”其实已经不是最新的了；不过我也没有仔细考察每个问题当前的进展，因此本文的信息并不保证是 100% 准确的，在此向读者们表示歉意。
这篇文章很长，大家不妨用自己喜欢的方式马克一下，一天读一点。
大家或许还记得 Quake III 里面的一段有如天书般的代码，其中用到的神秘常量 0x5F3759DF 究竟是怎么一回事，着实让不少人伤透了脑筋。今天，我见到了一段同样诡异的代码。
下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 0 。比如， 123 456 的二进制表达是 1 11100010 01000000 ，因此这个程序给出的结果就是 6 。
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
熟悉位运算的朋友们可以认出， v & -v 的作用就是取出右起连续的 0 以及首次出现的 1 。当 v = 123 456 时， v & -v 就等于 64 ，即二进制的 1000000 。怪就怪在，这个 0x077CB531 是怎么回事？数组 MultiplyDeBruijnBitPosition 又是什么玩意儿呢？
23. 一些硬币互不重叠地放在桌上。四色定理告诉我们，若要对硬币进行染色，使得挨在一起的硬币颜色不同的话，最多只需要四种颜色就可以了。存在至少需要四种颜色的构造吗？
答案：存在。如图，若只允许三种颜色的话， A 的颜色必须与所有阴影硬币颜色相同， B 的颜色也必须与所有阴影硬币颜色相同， A 、 B 将会同色。
Matrix67 |
2011-11-09 13:26 | 
