小明和狮子同被关在一个半径为 10 米的竞技场里，狮子位于竞技场的圆心处，小明则在距离圆心 1 米的地方。两者的最大运动速度都是每秒 1 米。狮子有没有什么必胜策略，使得不管小明怎么跑，它总能在有限的时间里抓住小明？

根据 MathWorld 相关词条的描述，这个问题是由 R. Rado 在 1925 年时提出的。一个经典的“答案”是，狮子只需要始终保持自己与小明在圆盘的同一半径上即可。直觉上看，由于狮子总是处在“内圈”上，因而不管小明跑到了哪里，狮子总能轻松地与小明继续保持在同一半径上；并且，狮子总有足够的余力向小明靠近，严格减小它与小明之间的距离，除非小明是沿着半径方向径直向外跑。由于竞技场的大小是有限的，小明不可能无限地向外跑，因而狮子最终总会追上小明。但是，后来人们发现，这个解法其实是错误的，原因很简单：能不断靠近小明，不一定就能在有限的时间里抓住小明，正如 1/2 + 1/4 + 1/8 + 1/16 + … 永远不会超过 1 一样。最终， A. S. Besicovitch 为小明构造出了一个极其巧妙的策略，使得狮子无论如何都抓不到小明，从而完美地解决了这个问题。不过， MathWorld 的词条里并没有提到这个解法。你能想到这个解法吗？

Read more…

让我们来玩一个游戏。连续抛掷硬币，直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者，那么我获胜，你需要给我 1 元钱；如果是后者，那么你获胜，我会给你 1 元钱。你愿意跟我玩这样的游戏吗？换句话说，这个游戏是公平的吗？

乍看上去，你似乎没有什么不同意这种玩法的理由，毕竟“正反反”和“反反正”的概率是均等的。连续抛掷三次硬币可以产生 8 种不同的结果，上述两种各占其中的 1/8 。况且，序列“正反反”和“反反正”看上去又是如此对称，获胜概率怎么看怎么一样。

实际情况究竟如何呢？实际情况是，这个游戏并不是公平的——我的获胜概率是你的 3 倍！虽然“正反反”和“反反正”在一串随机硬币正反序列中出现的频率理论上是相同的，但别忘了这两个序列之间有一个竞争的关系，它们要比赛看谁先出现。一旦抛掷硬币产生出了其中一种序列，游戏即宣告结束。这样一来，你就会处于一个非常窘迫的位置：不管什么时候，只要掷出了一个正面，如果你还没赢的话，你就赢不了了——在出现“反反正”之前，我的“正反反”必然会先出现。

事实上，整个游戏的前两次硬币抛掷结果就已经决定了两人最终的命运。只要前两次抛掷结果是“正正”、“正反”、“反正”中的一个，我都必胜无疑，你完全没有翻身的机会；只有前两次掷出的是“反反”的结果，你才会赢得游戏的胜利。因此，我们两人的获胜概率是 3:1 ，我的优势绝不止是一点。

你或许想问，如果已知我的硬币序列是“正反反”，那么你应该选择一个怎样的硬币序列，就能保证获胜概率超过我呢？研究表明，你可以选择“正正反”，这样一来，我们两人的获胜概率将会变为 1:2 ，换句话说你将会有 2/3 的概率获胜。 Using your Head is Permitted 趣题站 2014 年 5 月的趣题对此进行了更深一步的探究。

A 、 B 两人打算玩这么一个游戏。首先， A 选择一个长度为 n 的正反序列，然后 B 再选择另一个长度为 n 的正反序列。之后，不断抛掷硬币，哪名玩家所选的正反序列最先出现，哪名玩家就获胜。我们的问题是，假如两名玩家都采取最优策略的话，对于哪些 n ，游戏对玩家 A 更有利一些（换句话说，玩家 A 拥有超过 50% 的胜率），对于哪些 n ，游戏对玩家 B 更有利一些（换句话说，玩家 B 拥有超过 50% 的胜率）。今后，为了方便起见，我们用数字 1 代表“正面”，用数字 0 代表“反面”。

Read more…

让我们先从两个小问题开始说起。第一个问题是，是否存在某个无限不循环的 01 串，使得对于任意一个正整数 n ，该 01 串中长度为 n 的子串都有且仅有 n + 1 种？

或许这个问题来得有些突然。让我们慢慢解释一下，这个问题是怎么来的。衡量一个 01 串的复杂程度有很多办法，比方说，我们可以去考察它的“子串复杂度”（subword complexity），即子串的种类有多丰富。我们用 p_w(n) 来表示，在一个（有可能无限长的）数字串 w 当中，长度为 n 的子串一共有多少种。例如，对于无限 01 串 α = 000000… 来说，不管 n 是多少， p_α(n) 永远都等于 1 ；而对于无限 01 串 β = 001001001… 来说，我们有 p_β(1) = 2 ，并且 p_β(2) = p_β(3) = p_β(4) = … = 3 。

注意，虽然 α 和 β 这两个 01 串都是无限的，但是当 n 的值变得很大时， p_α(n) 和 p_β(n) 的值始终很小。当然，这一点也不奇怪，因为 α 和 β 是一种特殊的无限 01 串——无限循环 01 串。对于那些无限不循环的 01 串来说，这种事情就不大可能了。在数字串 γ = 01001000100001… 里，长度为 1 的子串只有 {0, 1} 共 2 种，长度为 2 的子串有 {00, 01, 10} 共 3 种，长度为 3 的子串有 {000, 001, 010, 100} 共 4 种，长度为 4 的子串有 {0000, 0001, 0010, 0100, 1000, 1001} 共 6 种……像这样继续计算下去，我们可以得到序列 p_γ(1), p_γ(2), p_γ(3), p_γ(4), … 的前面若干项：

2, 3, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, …

趋势非常明显：随着 n 的增加， p_γ(n) 的值也会跟着增加，最终可以增加到任意大。换句话说， p_γ(n) 的值没有一个上限。那么，能否找到某个无限不循环的 01 串 w ，使得 p_w(n) 的值存在上限呢？不可能！下面我们就来说明，对于任意一个无限不循环的 01 串 w 来说，不管 n 是多少，不等式 p_w(n) ≥ n + 1 始终成立。

Read more…

保加利亚单人纸牌游戏（Bulgarian solitaire）的玩法如下：

取出 45 张牌，然后把它们随意分成若干堆。接下来，从每一堆里各取一张牌，叠在一起形成一堆新的牌。不断这样做下去，如果某个时候桌面上正好有 9 堆牌，并且各堆牌数分别为 1, 2, 3, 4, …, 9 ，你就获胜了。

乍看上去，如果初始局面设定不佳，游戏很可能会陷入某个循环，从而永远无法获胜。然而， 1981 年，丹麦数学家 Jørgen Brandt 证明了，对于任意一个初始局面（包括把所有牌摆成 1 堆，以及把所有牌分成 45 堆这样的极端局面），游戏都能在有限步之内获胜。事实上，如果把 45 换成任意一个三角形数 n = 1 + 2 + … + k ，结论仍然成立。

Read more…

某个导师要和 A 、 B 两名学生玩一个游戏。导师会把 A 、 B 两名学生分别放进两间小黑屋里，每间屋子里都有一台电脑，这两台电脑之间只有一条通信线路。然后，导师会想一个正整数 n （可能会非常非常大），把它的值告诉这两名学生；再构造出集合 {1, 2, …, n} 的两个子集，分别交给这两名学生。于是，每个人都知道了 n 的值和 {1, 2, …, n} 的一个子集。两人需要合作确定出，他们手中的集合是否包含公共的元素。他们之间交流信息的唯一途径就是那条通信线路，但他们能够使用的流量是有限的。具体能够使用多少 bit 的流量，这可以由他们自己决定，但必须在游戏开始之前（也就是 n 的值确定之前）就定好并告诉导师。

和其他类似的问题一样，在游戏开始之前，两人可以商量一个对策。不过，这一回，两人商量了很久，始终无法找到一个必胜的对策。就在两人快放弃的时候，他们突然发现，两人的通信线路上存在一个“漏洞”：两人都可以不计流量地访问一台特殊的第三方机器，我们不妨把它叫做机器 O 。不过，机器 O 只能做一件事情：从 A 那儿读取一个 1 到 n 的排列，从 B 那儿读取一个 1 到 n 的排列，然后计算出这两个排列复合之后是否恰好含有一个循环，并将计算结果分别告知 A 和 B 。然后，机器 O 就会自动关机，再也不能访问了。也就是说，A 和 B 只能使用机器 O 一次。注意， A 、 B 两人是无法看到对方传给机器 O 的数据的，另外机器 O 只能用于处理 1 到 n 之间的排列，不能处理其他大小的排列。

Read more…