Alice 的手中有 n 件物品，每件物品的价值都是一个 1 到 n 之间的整数； Bob 的手中也有 n 件物品，每件物品的价值也都是 1 到 n 之间的整数。现在，两人想要进行一次等值的交易，即 Alice 从自己手中拿出至少一件物品， Bob 从自己手中拿出至少一件物品，使得两人所拿出的物品总价值相等。求证：这是总能办到的。
2月14日：送给你的礼物
* 需要 WebGL 支持
Hofstadter的非线性递推数列
在著名奇书 Gödel, Escher, Bach: An Eternal Golden Braid 的第五章中，为了展现出递推序列的神奇之处，作者 Douglas Hofstadter 定义了这么一个递推序列： G(n) = n – G(G(n – 1)) ，其中 G(1) = 1 。这个序列的前 30 项如下：
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| G(n) | 1 | 1 | 2 | 3 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 8 | 8 | 9 | 9 | 10 | 11 | 11 | 12 | 12 | 13 | 14 | 14 | 15 | 16 | 16 | 17 | 17 | 18 | 19 |
这个数列通常被称作 Hofstadter G-sequence 。它有什么特别的地方呢？如上图，如果把每个标号为 n 的结点都连接到标号为 G(n) 的结点下方，这样的话你将会得到一棵树。从第二行开始算起，各行的结点个数依次为 1, 1, 2, 3, 5, 8, 13, … 正好是著名的 Fibonacci 数列（头两个数都是 1 ，从第三个数开始，每个数都是前两个数之和）。如果我们把第 i 个 Fibonacci 数记作 Fi 的话，上面的规律可以重新表述为：当 n ≥ 2 时，这棵树的第 n 行的结点总个数为 Fn-1 。另外，这棵树的前 n 行的结点总数（也就是第 n 行最右边那个结点的编号）正好等于 Fn+1 ，也是一个个的 Fibonacci 数。对照上面两个事实，你会惊奇地发现，莫非 F1 + F2 + … + Fn-1 + 1 总是等于 Fn+1 ？事实的确如此，上面这个式子对于所有大于等于 2 的正整数 n 均成立。
五个有趣的拓扑变换问题
如果你喜欢上次的空间想象能力挑战，你一定会喜欢 V. V. Prasolov 的 Intuitive Topology 一书。书中的第一章有五个非常经典的“拓扑变换”类谜题，在此与大家分享。注意游戏规则：我们假设所有物体都是用橡胶做成的，可以随意地拉伸、挤压、弯曲，但不允许切断、粘连等任何改变图形本质结构的操作。
1. 能否把左图连续地变形为右图？
2. 能否把左图连续地变形为右图？
跨越千年的RSA算法
数论，数学中的皇冠，最纯粹的数学。早在古希腊时代，人们就开始痴迷地研究数字，沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后，几千年来的数论研究成果突然有了实际的应用，这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》，但受篇幅限制，只有一万字左右的内容。其实，从数论到 RSA 算法，里面的数学之美哪里是一万字能扯完的？在写作的过程中，我查了很多资料，找到了很多漂亮的例子，也积累了很多个人的思考，但最终都因为篇幅原因没有加进《程序员》的文章中。今天，我想重新梳理一下线索，把所有值得分享的内容一次性地呈现在这篇长文中，希望大家会有所收获。需要注意的是，本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释，一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述，可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后，希望大家能够积极指出文章中的缺陷，我会不断地做出修改。
======= 更新记录 =======
2012 年 12 月 15 日：发布全文。
2012 年 12 月 18 日：修改了几处表达。
2021 年 9 月 13 日：根据 Chang 的指正做了修改。
======== 目录 ========
（一）可公度线段
（二）中国剩余定理
（三）扩展的辗转相除
（四）Fermat 小定理
（五）公钥加密的可能性
（六）RSA 算法