在著名奇书 Gödel, Escher, Bach: An Eternal Golden Braid 的第五章中，为了展现出递推序列的神奇之处，作者 Douglas Hofstadter 定义了这么一个递推序列： G(n) = n - G(G(n - 1)) ，其中 G(1) = 1 。这个序列的前 30 项如下：

    这个数列通常被称作 Hofstadter G-sequence 。它有什么特别的地方呢？如上图，如果把每个标号为 n 的结点都连接到标号为 G(n) 的结点下方，这样的话你将会得到一棵树。从第二行开始算起，各行的结点个数依次为 1, 1, 2, 3, 5, 8, 13, ... 正好是著名的 Fibonacci 数列（头两个数都是 1 ，从第三个数开始，每个数都是前两个数之和）。如果我们把第 i 个 Fibonacci 数记作 F_i 的话，上面的规律可以重新表述为：当 n ≥ 2 时，这棵树的第 n 行的结点总个数为 F_n-1 。另外，这棵树的前 n 行的结点总数（也就是第 n 行最右边那个结点的编号）正好等于 F_n+1 ，也是一个个的 Fibonacci 数。对照上面两个事实，你会惊奇地发现，莫非 F₁ + F₂ + ... + F_n-1 + 1 总是等于 F_n+1 ？事实的确如此，上面这个式子对于所有大于等于 2 的正整数 n 均成立。

查看更多 »

    如果你喜欢上次的空间想象能力挑战，你一定会喜欢 V. V. Prasolov 的 Intuitive Topology 一书。书中的第一章有五个非常经典的“拓扑变换”类谜题，在此与大家分享。注意游戏规则：我们假设所有物体都是用橡胶做成的，可以随意地拉伸、挤压、弯曲，但不允许切断、粘连等任何改变图形本质结构的操作。

    1. 能否把左图连续地变形为右图？

 
    2. 能否把左图连续地变形为右图？

查看更多 »

    数论，数学中的皇冠，最纯粹的数学。早在古希腊时代，人们就开始痴迷地研究数字，沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后，几千年来的数论研究成果突然有了实际的应用，这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》，但受篇幅限制，只有一万字左右的内容。其实，从数论到 RSA 算法，里面的数学之美哪里是一万字能扯完的？在写作的过程中，我查了很多资料，找到了很多漂亮的例子，也积累了很多个人的思考，但最终都因为篇幅原因没有加进《程序员》的文章中。今天，我想重新梳理一下线索，把所有值得分享的内容一次性地呈现在这篇长文中，希望大家会有所收获。需要注意的是，本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释，一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述，可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后，希望大家能够积极指出文章中的缺陷，我会不断地做出修改。

======= 更新记录 =======

2012 年 12 月 15 日：发布全文。
2012 年 12 月 18 日：修改了几处表达。

======== 目录 ========

（一）可公度线段
（二）中国剩余定理
（三）扩展的辗转相除
（四）Fermat 小定理
（五）公钥加密的可能性
（六）RSA 算法

查看更多 »

    Ptolemy 定理是平面几何中非常漂亮的定理：圆内接四边形的对边乘积之和等于对角线的乘积。具体地说，如果把一个圆内接四边形的四条边顺次记为 a 、 b 、 c 、 d ，把两条对角线的长度记为 e 和 f ，那么一定有 a · c + b · d = e · f 。 Ptolemy 是一个非常重要的定理，由它出发可以得出很多推论。例如，在圆内接矩形上应用 Ptolemy 定理，可以立即得到勾股定理。下面是另外两个可以用 Ptolemy 定理来解决的问题：证明余弦定理，以及构造两两间的距离都是整数的点集。

     William Derrick 和 James Hirstein 在最近的 The College Mathematics Journal 上给出了下面这个 Ptolemy 定理的无字证明，你能看明白吗？

查看更多 »

    这个 Blog 已经不止一次提到过难倒犹太人的“棺材问题”了。很多年以前，要想进入莫斯科国立大学的数学系，你必须通过四项入学考试；头两个都是数学考试，一个笔试，一个面试。在面试中，学生和考官都是一对一的，考官可以自由向学生提出任何他喜欢的问题。考官们都准备了很多“棺材问题”，这些问题的答案非常简单，但由于思路太巧妙了，以至于学生很难想到。考官便可以以“你连这个都没想到”为理由，光明正大地拒绝学校不想要的人（主要是犹太人）。之前我们曾经介绍过一个典型的“棺材问题”：空间四边形外切于给定球，求证四切点共面。去年的这个时候，我们还介绍了同样机智巧妙的 11 个问题。

    民间还流传着很多其他的“棺材问题”列表。 Ilan Vardi 曾经写过一篇题为 Mekh-Mat Entrance Examinations Problems 的论文，收集了 25 个“棺材问题”，并给出了解答。这篇论文被收录进了 You Failed Your Math Test, Comrade Einstein 一书中。 Ilan Vardi 发现，这 25 个问题的“难法”有所不同。虽然其中不乏思路奇巧的好题，但也有不少步骤繁琐（当然也有可能是还没找到好的解法）、题意不清甚至结论错误的题目。这里，我选择了其中五个有趣的题目，写下来和大家一同分享。

查看更多 »

    为了说明“同痕”这一概念直观上并不容易把握，《The Knot Book》一书中举了一个经典的例子。如下图，左图是一个有三个洞的立体图形，右图是被挖出了三条通道的立方体（但其中一个通道在另一个通道上缠绕了一圈）。令人难以置信的是，两者之间竟然是同痕的，换句话说前者可以连续地变形成为后者。你能想象出这个变换过程吗？

查看更多 »

    有 1000 枚硬币堆在一起。把它们任意分成两堆，并计算出这两堆的硬币数的乘积。然后，任意选择其中的一堆硬币，把它继续分成两个更小的堆，并计算出这两堆的硬币数的乘积。不断这样做下去，直到最后每堆都只剩一枚硬币为止。求证：把途中产生的所有乘积全部加在一起，结果是一个定值，它不随分法的改变而改变。

查看更多 »

    有一条虫子，它的整个身体由 n 节构成，每一节要么是有瑕疵的 1 ，要么是没有瑕疵的 0 ，因而整个虫子的身体结构就可以用一个 n 位 01 串来表示。你的目标是把整个虫子变成 000...00 的完美形式。每一次，你可以砍掉虫子最右侧的一节，同时虫子会在最左侧长出新的一节，以保持虫子的总长度不变。如果你砍掉的是一个 1 ，那么你可以指定虫子在最左侧长出的是 1 还是 0 ；但如果你砍掉的是一个 0 ，那么你无法控制虫子会在最左侧长出什么——它可能会长出 0 ，也可能会长出 1 ，因而你不得不假定，概率总是会和你做对，上天会竭尽全力地阻挠你。我们的问题是：不管虫子的初始状态是什么，你总能保证在有限步之内让虫子变成 000...00 吗？

    注意，这个问题可能没有你想的那么简单。显然，我们必须得把一些 1 变成 0 ，这样才能让 1 的数目逐渐减少并最终消失。但是，如果只是简单地每次都把 1 变成 0 ，最终也不见得就一定能取胜。比如，如果这条虫子是 101 ，那么去掉最右边的 1 并选择在左边长出一个 0 ，虫子会变成 010 ；再把 010 右边的 0 去掉后，如果不巧左边长出的是 1 ，那么整条虫子又会回到 101 的状态。如此反复，将永远也不能得到 000 。而更加聪明的方法则是先把 101 变成 110 ，下一步虫子将会变成 111 或者 011 ，不管是哪种情况，接下来只需要逐个把 1 变成 0 就能获胜了。运用恰当的策略才能走到终点，这无疑让问题变得更加有趣。

查看更多 »