今天的趣题来源于 IBM Ponder This 三月份的谜题。
大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒药瓶子的二进制编号中，右起第二位是 0 ⋯⋯每只老鼠的死活都能确定出 10 位二进制数的其中一位，由此便可知道毒药瓶子的编号了。
现在，有意思的问题来了：如果你有两个星期的时间（换句话说你可以做两轮实验），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。
先给大家看两个“单词等式”：
ACT + DEAL = DONE
COIN + TRY = DIAL
除了意义上说得通以外，从另外一个角度来看，这两个等式也是成立的。大家能猜到是什么吗？
有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。有一个不可思议的结论：你可以在两步之内还原出整个多项式！这是如何做到的呢？
首先，输入 1 ，于是便得到整个多项式的所有系数之和。不妨把这个系数和记作 S 。下一步，输入 S + 1 ，于是黑匣子返回
an * (S + 1)n + an-1 * (S + 1)n-1 + … + a1 * (S + 1) + a0
把这个值转换成 S + 1 进制，依次读出每一位上的数，它们就是多项式的各项系数了。
来源：http://rjlipton.wordpress.com/2010/12/20/some-mathematical-gifts/
这个有趣的问题曾经以另一形式出现在了这个 Blog 里，见 这里 的 35 题。
或许有人会对算式 5^2 = 25 有一种特别的偏好——等式左右两边都用到了相同的数字，让人深感奇妙。类似的算式还有很多，例如
5^(6 - 2) = 625
(4 / 2)^10 = 1024
((86 + 2 * 7)^5 - 91) / 3^4 = 123456789
我们自然而然地提出了这样一个问题：这样的算式究竟有多少呢？答案是：无穷多。只需要借助本文一开始提到的算式 5^2 = 25 ，我们就能轻易构造出无穷多个同样满足这种神奇性质的算式来：
50^2 + 0 = 2500
500^2 + 0 + 0 = 250000
5000^2 + 0 + 0 + 0 = 25000000
......
现在，让我们来看看另一类更加精妙的算式：等式两边的数字顺序也完全一样！
- 1 + 2^7 = 127
(3 + 4)^3 = 343
16^3 * (8 - 4) = 16384
这样的算式是否仍然有无穷多个呢？
不知道大家有没有幻想过，数学中是否存在这样一个牛B的问题，发表出来后十几年硬是没有一个人解开；后来某人惊奇地发现，它有一个极其精妙的解答，整个解决过程只需要几句话就能说清楚，但它实在是太巧妙了，这么多年就没有任何人想到。最近我就遇到了这样的事情。3月份UyHiP的题目非常有趣，整个证明几句话就完了，但想到解法的却只有一人。
题目描述也极其简单。对于哪些n，存在一种生成n个随机变量的算法，使得它们在0和1之间均匀分布，且它们的和是一个常数？更进一步，如果这n个变量中任意k个都相互独立，满足要求的k最大是多少（表示成关于n的函数）？
当然，这道题目我也没想出来。答案公布前，我思考了很久，最后还是放弃了。显然n是偶数时这样的算法是存在的，例如当n=6时，只需要先独立地选取3个随机变量X_1, X_2, X_3，然后令X_4 = 1 - X_1，X_5 = 1 - X_2，X_6 = 1 - X_3即可。这可以保证6个变量之和总为3，且它们均匀地分布在[0,1]区间里。但是当n是奇数时，满足要求的算法就未必存在了。例如当n=3时，不妨让X_1和X_2随机取，X_3等于1.5 - X_1 - X_2。这种算法似乎很和谐，问题就出在X_3有可能不在0和1之间。那么，重复执行该操作直到返回一个落在[0,1]里的X_3呢？这样的话变量又不是均匀分布的了，这将让变量更容易取到中间去，因为X_1和X_2太小或太大往往算不出合法的X_3（下图是Mathematica模拟的结果）。我试图从“n个变量的和的期望值是n/2”出发，证明和为1.5的3个变量不可能均匀分布在0到1之间。不过，最终还是没有找到突破口。
首先呢，让我们来一个牛B函数大回顾。这下我不知道要赚多少的PV。你能否构造一个函数f(x)，使得：
它是一个阶梯状的连续函数？
它是除常函数之外的没有最小正周期的周期函数？
该函数只在一点连续？
该函数在[0,1]和(0,1)之间形成一一对应？
该函数某一点导数为正，但该点邻域不构成单增区间？
平面上任意小的圆内均包含函数上的点？
另外还有一些可能是众所周知（所以没在Blog里写过）的函数，比如处处连续但处处不可导的函数、在有理点处处不连续在无理点处处连续的函数等等。
好了，现在呢，又一个牛B东西出现了。你能不能想出这样一个函数f，它的定义域和值域都是R，并且对于任意小的区间l=(u,v)，这个函数都能把(u,v)满射到整个R上。换句话说，是否存在这样的函数f(x)，对于任意一个实数t以及任意一个区间(u,v)，总存在一个x满足u<x<v且f(x)=t。
Matrix67 |
2011-05-27 12:27 | 
