下面是 2013 年 9 月 IBM Ponder This 的谜题。

    A 和 B 在赌场玩一个游戏，他们要协同作战与庄家对抗。游戏一轮一轮地进行，每一轮的规则都是一样的：首先 A 赌 0 和 1 当中的某个数字，然后 B 再赌 0 和 1 当中的某个数字，最后庄家给出 0 和 1 当中的某个数字；如果所有的三个数字都相同，则 A 和 B 获胜，否则庄家获胜。游戏前， A 和 B 可以商量一个对策，但游戏一旦开始，除了下赌注本身之外，两人不能再有其他任何形式的交流了。

    容易看出，如果 A 和 B 都随机下注，他们只有 25% 的获胜概率。然而，如果两人事先约定，在每一轮中， B 总是跟着 A 下注， A 赌什么 B 就赌什么，那么他们获胜的概率就会提高到 50% 。但是，不管采用哪种方案，在最坏情况下，两人都有可能一次也不能获胜。

    有意思的事情出现了。在游戏开始前两人商量策略的时候，两人突然意识到， B 有办法偷到庄家将会在游戏中使用的 01 序列。也就是说，游戏开始后，每一轮里庄家要出什么， B 都将会知道。但是，一旦 B 拿到了这个 01 序列， B 就不能和 A 交流了。在这样的条件下，两人能做得比刚才更好吗？能！比如说，两人可以保证在最坏情况下也有至少 50% 的获胜次数： B 可以在第 1, 3, 5, 7, … 轮游戏中赌下一轮庄家将会出的那个数（这相当于暗示了 A 下一轮赌什么），两人便能保证在第 2, 4, 6, 8, … 轮游戏中获胜了。

    我们的问题是：假设游戏一共有 9 轮，设计一种策略使得 A 和 B 能够保证至少 6 次胜利。

Read more…

    还记得小时候有一道经典奥数题，大概是让你把两个数字 1 、两个数字 2 、两个数字 3 和两个数字 4 排成一个 8 位数，使得其中两个数字 1 之间正好夹着 1 个数字，两个数字 2 之间正好夹着 2 个数字，两个数字 3 之间正好夹着 3 个数字，两个数字 4 之间正好夹着 4 个数字。稍作尝试便可得出正确答案： 4, 1, 3, 1, 2, 4, 3, 2 。如果把逆序后的数列视作本质相同的数列，那么上面这个答案是唯一的。这个问题是由 C. Dudley Langford 在 1958 年提出的，因此我们把它叫做 Langford 数列。

    当 n = 3 时， Langford 数列也是唯一的： 2, 3, 1, 2, 1, 3 。我小时候曾经没日没夜地试图寻找 n = 5 时的 Langford 数列，结果却怎么也找不到。后来才知道， n = 5 时的 Langford 数列根本就不存在。这是为什么？你能证明这一点吗？

Read more…

    在一棵树中，任意两个顶点之间的路径都是唯一的。如果一棵树有 n 个顶点，那么这棵树总共会有 n(n-1)/2 条路径（每两个顶点都会确定出一条路径来）。 1975 年， John Leech 提出了这么一个问题：有多少顶点数为 n 且边上带权的树，使得图中所有 n(n-1)/2 条路径的权值之和正好是 1, 2, …, n(n-1)/2 ？Leech 本人给出了五个这样的例子，其中四个如下图所示，顶点数 n 分别为 2 、 3 、 4 、 4 。第五棵满足要求的树拥有 6 个顶点，把它找出来将会是一个不小的挑战，感兴趣的读者不妨尝试一下，本文最后会公布答案。 Leech 注意到了 n = 5 时是无解的，但却并没有给出一个解释。

    1977 年， Herbert Taylor 给出了一个非常漂亮的解释：如果一棵树满足上述要求，那么顶点数 n 一定是形如 m² 或者 m² + 2 的数。让我们来看一看这个精妙的证明。

Read more…

    这是一个非常有趣的问题，它出自 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) 是以什么级别增长的。

Read more…

    考虑这么一个 14 位数 02565413989732 ，如图所示，它的数字先逐渐变大，然后开始变小，再变大，再变小，再变大，再变小。我们就说，它一共包含了 6 个单调区间。我们的问题就是：一个 n 位数平均有多少个单调区间？为了避免歧义，我们假设任意两位相邻的数字都不相同，因而像 77765589911 这样的数我们就不考虑了。另外，大家可能已经注意到了，我们允许这个 n 位数以数字 0 开头。因而，更精确地说，我们的问题是：相邻数字都不相同的、允许以 0 开头的所有 n 位数当中，平均有多少个单调区间？

    这个题目来自 1987 年 IMO 候选题。

Read more…