最近，一道 Google 校园招聘面试题红遍了整个中文网络：
现在北京有一套房子，价格 200 万，假设房价每年上涨 10% ，一个软件工程师每年固定能赚 40 万。如果他想买这套房子，不贷款，不涨工资，没有其他收入，每年不吃不喝不消费，那么他需要几年才能攒够钱买这套房子？
A. 5年
B. 7年
C. 8年
D. 9年
E. 永远买不起
并不让人感到意外，这道题的答案选 E 。这背后的数学道理就是，线性的增长速度毕竟是赶不上指数级的增长速度的。我用 Mathematica 画了一个简单的图，按照题目所给数据模拟了 50 年内的房价和收入情况。可见，尽管底数仅仅是 1.1 ，指数级增长的威力也一如既往的令人震撼。
唉⋯⋯什么时候工资也能成比地增长就好了。
《来自圣经的证明》收集了数十个简洁而优雅的数学证明，迅速赢得了大批数学爱好者的追捧。如果还有一本《来自圣经的算法》，哪些算法会列入其中呢？最近，有人在 StackExchange 上发起了提问，向网友们征集那些来自圣经的算法。众人在一大堆入围算法中进行投票，最终得出了呼声最高的五个算法：
第五名： BFPRT 算法
1973 年， Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集体出动，合写了一篇题为 “Time bounds for selection” 的论文，给出了一种在数组中选出第 k 大元素的算法，俗称"中位数之中位数算法"。依靠一种精心设计的 pivot 选取方法，该算法从理论上保证了最坏情形下的线性时间复杂度，打败了平均线性、最坏 O(n^2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于骨掌股掌之间，构造出了一个当之无愧的来自圣经的算法。
最近看到几个有趣的数学谬证，想写下来与大家分享；结果写到这个又想到那个，一写就写个没完，于是想到干脆做一篇谬证大全，收集各种荒谬的证明。
如果你有什么更棒的“证明”，欢迎来信与我分享，我会更新到这篇日志中。我的邮箱是 matrix67 at tom.com ，或者 gs.matrix67 at gmail.com 。
1=2？史上最经典的“证明”
设 a = b ，则 a·b = a^2 ，等号两边同时减去 b^2 就有 a·b - b^2 = a^2 - b^2 。注意，这个等式的左边可以提出一个 b ，右边是一个平方差，于是有 b·(a - b) = (a + b)(a - b) 。约掉 (a - b) 有 b = a + b 。然而 a = b ，因此 b = b + b ，也即 b = 2b 。约掉 b ，得 1 = 2 。
这可能是有史以来最经典的谬证了。 Ted Chiang 在他的短篇科幻小说 Division by Zero 中写到：
There is a well-known “proof” that demonstrates that one equals two. It begins with some definitions: “Let a = 1; let b = 1.” It ends with the conclusion “a = 2a,” that is, one equals two. Hidden inconspicuously in the middle is a division by zero, and at that point the proof has stepped off the brink, making all rules null and void. Permitting division by zero allows one to prove not only that one and two are equal, but that any two numbers at all—real or imaginary, rational or irrational—are equal.
这个证明的问题所在想必大家都已经很清楚了：等号两边是不能同时除以 a - b 的，因为我们假设了 a = b ，也就是说 a - b 是等于 0 的。
晚饭之后一起来动动脑吧。纸上有两条夹角很小的直线 a 、 b ，它们在纸外交于一点 O 。在纸上还有一点 P ，大致位置如上图所示。请你利用圆规和（没有刻度的）直尺作出一条同时过 O 、 P 的直线。当然，你不能把图作到纸张外面去。
我一直觉得，数学中的各种常数是最令人敬畏的东西，它们似乎是宇宙诞生之初上帝就已经精心选择好了的。那一串无限不循环的数字往往会让人陷入一种无底洞般的沉思——为什么这串数字就不是别的，偏偏就是这个样呢。除了那些众所周知的基本常数之外，还有很多非主流的数学常数，它们的存在性和无理性同样给它们赋予了浓重的神秘色彩。今天，就让我们一起来看一看，数学当中到底有哪些神秘的无理常数。
√2 ≈ 1.4142135623730950488
古希腊的大哲学家 Pythagoras 很早就注意到了数学与大千世界的联系，对数学科学的发展有着功不可没的贡献。他还创立了在古希腊影响最深远的学派之一—— Pythagoras 学派。 Pythagoras 学派对数字的认识达到了审美的高度。他们相信，在这个世界中“万物皆数”，所有事物都可以用整数或者整数之比来描述。
第一个无理数 √2 的发现者就是一位 Pythagoras 学派的学者，他叫做 Hippasus 。据说，一日 Hippasus 向 Pythagoras 提出了这样的问题：边长为 1 的正方形，对角线长度能用整数之比来表示吗？ Pythagoras 自己做了一些思考，证明了这个数确实无法用整数之比来表示。由于这一发现触犯了学派的信条，因此 Pythagoras 杀害了 Hippasus 。
利用勾股定理可知，这个数是方程 x^2 = 2 的唯一正数解，我们通常就记作 √2 。 √2 可能是最具代表性的无理数了，我们之前曾经介绍过很多 √2 的无理性的证明。无理数的出现推翻了古希腊数学体系中的一个最基本的假设，直接导致了第一次数学危机，整座数学大厦险些轰然倒塌。
无理数虽说无理，在生产生活中的用途却是相当广泛。例如，量一量你手边的书本杂志的长与宽，你会发现它们的比值就约为 1.414 。这是因为通常印刷用的纸张都满足这么一个性质：把两条宽边对折到一起，得到一个新的长方形，则新长方形的长宽之比和原来一样。因此，如果原来的长宽比为 x : 1 ，新的长宽比就是 1 : x/2 。解方程 x : 1 = 1 : x/2 就能得到 x = √2 。
目前，我正在《新知客》杂志上主持一个趣题栏目。每月杂志发行后，我将在 Blog 上同步更新。点击 这里 可以查看往期题目。
推理
1. 在每一个小题中，我们都列出了八种物品，其中前面四种物品都有一个共同点，而这个共同点是后面四种物品所不具有的。请您找出这个共同点来。
(1) 小肠、地毯、水蜜桃、贵宾犬 | 牙刷、足球、藤椅、冰块
(2) 电线、棋子、指示灯、扇形图 | 闹钟、绳子、条形码、井字棋
(3) 电池、钥匙、酵母、书签 | 火柴、魔方、药瓶、订书机
2. 小 A 站在甲、乙两地之间的某个位置，他想乘坐出租车到乙地去。他看见一辆空车远远地从甲地驶来，而此时整条路上并没有别人与他争抢空车。我们假定车的行驶速度和人的步行速度都是固定不变的，并且车速大于人速。为了更快地到达目的地，小 A 应该怎样做呢？你认为下面哪种思路是正确的？
(A) 由于车速大于人速，小 A 应该尽可能早地上车，充分利用汽车的速度优势。因此，小 A 应该迎着空车走上去，提前与车相遇。
(B) 为了尽早到达目的地，小 A 应该充分利用时间，马不停蹄地赶往目的地。因此，他应该自己先朝目的地走一段路，再让出租车载他走完剩下的路程。
这段唯美的视频似乎是由大千世界中的各种场景毫无意义地拼接而成的，而事实上却并非如此。视频中的片段是精心选择的，它们描述了生活中最常见的一些单词。这就给大家留下了一个小小的谜题：这段视频究竟是以哪些单词为主题的？你能找全吗？
Matrix67 |
2010-09-29 12:30 | 
