下面是 IBM Ponder This 2013 年 5 月的谜题：写一个程序来计算 f(x) = 1 + x + x2 + x4 (mod 2233393) 。你的程序只能使用以下三种语句，其中等号表示赋值，变量 2 和变量 3 的位置都可以用常量来代替：
(1) 变量 1 = 变量 2 + 变量 3
(2) 变量 1 = 变量 2 * 变量 3
(3) 变量 1 = 变量 2 mod 变量 3
很容易想到，一种最基本的解法如下：
a = x * x
b = a * a
c = a + b
d = c + x
e = d + 1
f = e mod 2233393
这道谜题则要求你找到另外一种解法，它必须同时满足下面两个额外的要求：
(1) 最多使用两次变量与变量之间的乘法运算（但允许多次变量与常量之间的乘法运算）
(2) 最后两次运算分别是一次变量与变量之间的乘法运算和一次取余运算
通信复杂度（communication complexity）主要研究这么一类问题： A 持有数据 x ， B 持有数据 y ，他们想要合作计算某个关于 x 和 y 的二元函数值 f(x, y) ，那么在渐近意义下，两人至少需要传输多少 bit 的数据。最近着迷于通信复杂度，看到了几个与通信复杂度有关的问题，和大家分享一下。下面就是其中之一。
A 、 B 的手中各有一个 {1, 2, …, n} 的子集。两人想知道，如果把他们手中的数全都放在一块儿，那么这些数（可能会有重复的数）的中位数是多少。然而， A 、 B 两人远隔千里，他们之间通信的成本非常高。因此，他们想在通信线路上传输尽可能少的信息，使得最终两人都知道中位数的值。在这里，为了简便起见，我们直接定义 m 个数的中位数是第 ⌈ m / 2 ⌉ 小的数，因而如果 m = 2k ，那么中位数就应该直接取第 k 小的数。
其中一种最笨的方法是， A 把手中的所有数全部发给 B 。由于发送一个不超过 n 的正整数最多会用到 log(n) 个 bit ，而 A 手里的数最多有 O(n) 个，因此 A 传给 B 的信息量就是 O(n · logn) 。于是， B 就得到了足够多的信息，可以直接计算中位数了，算好后再把结果告诉 A ，此时又要耗费 log(n) 个 bit （但它并不会成为通信量的瓶颈）。因此，在这种方案中，总的通信复杂度就是 O(n · logn) 。事实上，传送一个 {1, 2, …, n} 的子集只需要一个 n 位 01 串就够了，因而我们可以把通信复杂度降低到 O(n) 个 bit 。
利用下面的办法，我们可以实现 O(logn · logn) 的通信复杂度。首先， A 、 B 分别告诉对方自己手中有多少个数，这一共会耗费 O(logn) 个 bit 。接下来，两人在区间 [1, n] 上进行二分查找。假设到了某一步，中位数被限定在了区间 [i, j] 里，那么 A 就计算出 k = (i + j) / 2 ，数一数自己手中有多少个数比 k 小，然后告诉 B ，由 B 再来数数自己这边又有多少个比 k 小的数，从而判断出 k 作为中位数来说是偏大了还是偏小了，并把判断出来的结果返回给 A 。根据情况，区间 [i, j] 将被更新为 [i, k] 或者 [k, j] ，两人在新的区间上继续二分下去。整个算法将会持续 O(logn) 轮，每一轮都会传输 O(logn) 的数据，因此总的通信复杂度是 O(logn · logn) 。
另一方面，通信复杂度至少是 Ω(logn) 的。这是因为，如果规定 A 和 B 最多只能交流 k 个 bit ，那么整个交流历史最多就只有 k 次分岔的机会，到最后最多只能产生 2k 个不同的分支；但事实上中位数有可能是 1 到 n 中的任何一个，共有 n 种不同的可能，因此 2k 必须大于等于 n 。这说明 k 必须大于等于 log2(n) ，也就是说两个人总会有必须要交流 log2(n) 个 bit 才行的时候。
一个有意思的问题自然而然地诞生了：我们所得的上界和下界仍然有差距。究竟是刚才的算法还不够经济，还是刚才证明的结论还不够强呢？
还想说明一点的是，两个人商量算法的过程，或者其中一个人把算法告诉另一个人的过程，这可以不算进通信复杂度里。事实上，把它们算进通信复杂度里也没关系，因为它们反正都是 O(1) 的。
这是一个非常有趣的问题，它出自 UyHiP May 2013 的谜题。
假设你有 n 枚外观完全相同的硬币，它们的重量分别为 1g, 2g, 3g, …, ng 。有意思的是，这一次，你已经知道了各枚硬币的重量，而且你也已经把重量值标在了这些硬币上。但是，由于我不知道各枚硬币的重量，因此我希望你能向我证明，你所标的重量值是正确的（我知道这些硬币的重量是从 1 克到 n 克，我只是不知道哪个硬币对应哪个重量）。
你唯一能用的工具就是一架天平。每一次，你可以任意选择一枚或多枚硬币，放在天平的左侧，再从剩下的硬币中任意选择一枚或多枚硬币，放在天平的右侧（注意，你只能在天平上放硬币，不能放别的东西）。一个有意思的问题是，为了向我证明你所标的重量值都是对的，你最少需要使用多少次天平？
显然，为了证明 n 枚硬币的重量标签的正确性，我们最多需要称 n – 1 次。先把硬币 1 放在左边，把硬币 2 放在右边，让对方看到硬币 1 确实比硬币 2 要轻。接下来，向对方验证硬币 2 确实比硬币 3 更轻，硬币 3 确实比硬币 4 更轻，等等。称完 n – 1 次后，我们就相当于给出了 n 枚硬币的轻重顺序，因而它们只有可能分别是 1 克 、 2 克 、 3 克……。
我们还能做得更好吗？不妨让我们看看 n 比较小的情况。例如，当 n = 4 的时候，利用上述方法可以 3 次完成验证，那么只用 2 次可以完成验证吗？仔细一想，你会发现真的可以！其中一种方法就是，先把硬币 1 和硬币 2 放在左边，把硬币 4 放在右边。由于两枚硬币的重量之和小于第三枚硬币，这只可能是 1 + 2 < 4 ，因此对方会相信，左边两枚硬币分别是 1 和 2 ，右边那枚硬币是 4 ，没放上去的那枚硬币是 3 。对方唯一不知道的就是，在左边两枚硬币中，究竟谁是 1 ，谁是 2 。于是，我们只需要再称一下硬币 1 和硬币 2 ，问题就解决了。
不妨把证明 n 枚硬币重量标签的正确性最少需要的称重次数记作 B(n) 。我们的问题就是：判断 B(n) 是以什么级别增长的。
下面这个问题来自于 IMO 2010 中的第 5 题。桌子上有 B1 、 B2 、 B3 、 B4 、 B5 、 B6 共六个盒子，初始时每个盒子里面都有一枚硬币。允许以下两种操作：
(1) 选择一个非空的盒子 Bj （1 ≤ j ≤ 5），从 Bj 里拿走一枚硬币，然后在 Bj+1 里添加两枚硬币。
(2) 选择一个非空的盒子 Bk （1 ≤ k ≤ 4），从 Bk 里拿走一枚硬币，然后交换 Bk+1 和 Bk+2 里面的硬币数（这两个盒子里的硬币数都有可能是 0 ）。
是否有可能通过有限次操作，使得最后 B1 、 B2 、 B3 、 B4 、 B5 都是空的，并且 B6 里面恰好有 2010 ^ (2010 ^ 2010) 枚硬币（符号 ^ 表示乘方）？
1996 年 9 月 10 日，《旧金山纪事报》的体育版上登载了《巨人队正式告别 NL 西区比赛》一文，宣布了旧金山巨人队输掉比赛的消息。当时，圣地亚哥教士队凭借 80 场胜利暂列西区比赛第一，旧金山巨人队只赢得了 59 场比赛，要想追上圣地亚哥教士队，至少还得再赢 21 场比赛才行。然而，根据赛程安排，巨人队只剩下 20 场比赛没打了，因而彻底与冠军无缘。
有趣的是，报社可能没有发现，其实在两天以前，也就是 1996 年 9 月 8 日，巨人队就已经没有夺冠的可能了。那一天，圣地亚哥教士队还只有 78 场胜利，与洛杉矶道奇队暂时并列第一。此时的巨人队仍然是 59 场胜利，但还有 22 场比赛没打。因而，表面上看起来，巨人队似乎仍有夺冠的可能。然而，根据赛程安排，圣地亚哥教士队和洛杉矶道奇队互相之间还有 7 场比赛要打，其中必有一方会获得至少 4 场胜利，从而拿到 82 胜的总分；即使巨人队剩下的 22 场比赛全胜，也只能得到 81 胜。由此可见，巨人队再怎么努力，也不能获得冠军了。
在美国职业棒球的例行赛中，每个球队都要打 162 场比赛（对手包括但不限于同一分区里的其他队伍，和同一队伍也往往会有多次交手），所胜场数最多者为该分区的冠军；如果有并列第一的情况，则用加赛决出冠军。在比赛过程中，如果我们发现，某支球队无论如何都已经不可能以第一名或者并列第一名的成绩结束比赛，那么这支球队就提前被淘汰了（虽然它还要继续打下去）。从上面的例子中可以看出，发现并且证明一个球队已经告败，有时并不是一件容易的事。为了说明这一点，我们展示一组虚构的数据（这是在 1996 年 8 月 30 日美国联盟东区比赛结果的基础上略作修改得来的），如下表所示。
| Team | 胜 | 负 | 余 | 纽约 | 巴尔的摩 | 波士顿 | 多伦多 | 底特律 |
| 纽约 | 75 | 59 | 28 | 0 | 3 | 8 | 7 | 3 |
| 巴尔的摩 | 72 | 62 | 28 | 3 | 0 | 2 | 7 | 4 |
| 波士顿 | 69 | 66 | 27 | 8 | 2 | 0 | 0 | 0 |
| 多伦多 | 60 | 75 | 27 | 7 | 7 | 0 | 0 | 0 |
| 底特律 | 49 | 86 | 27 | 3 | 4 | 0 | 0 | 0 |
其中，纽约扬基队暂时排名第一，总共胜 75 场，负 59 场，剩余 28 场比赛没打，其中和巴尔的摩还有 3 场比赛，和波士顿还有 8 场比赛，和多伦多还有 7 场比赛，和底特律还有 3 场比赛（还有 7 场与不在此分区的其他队伍的比赛）。底特律暂时只有 49 场比赛获胜，剩余 27 场比赛没打。如果剩余的 27 场比赛全都获胜的话，是有希望超过纽约扬基队的；即使只有其中 26 场比赛获胜，也有希望与纽约扬基队战平，并在加赛中取胜。然而，根据表里的信息已经足以判断，其实底特律已经没有希望夺冠了，大家不妨自己来推导一下。