为了随机地并且概率均等地生成一个 1 到 6 之间的整数，通常的做法就是抛掷一个正方体的骰子。不过，这并不是唯一的办法。如果你有一枚公正的、正反概率相同的硬币，以及一枚不公正的、正反概率之比为 1 : 2 的硬币，那么你也能概率均等地生成一个 1 到 6 之间的整数。首先抛掷那枚不公正的硬币，那么结果有 1/3 的概率是正面朝上，有 2/3 的概率是反面朝上。如果出现了正面朝上的情况，那么令 i = 1 ；如果出现了反面朝上的情况，那么就再抛掷那枚公正的硬币，掷出正面则令 i = 2 ，掷出反面则令 i = 3 。最后，再抛掷一次公正的硬币，如果正面朝上则令 j = 0 ，如果反面朝上则令 j = 3 。容易看出， i + j 的值有 1, 2, 3, 4, 5, 6 这六种可能，它们出现的概率是均等的，都是 1/6 。

有人或许会说，用硬币模拟骰子哪有那么复杂，只用一枚公正的硬币就能办到：连续抛掷三次硬币，并且规定掷出“正正正”代表数字 1 ，掷出“正正反”代表数字 2 ，“正反正”为 3 ，“正反反”为 4 ，“反正正”为 5 ，“反正反”为 6 ，掷出“反反正”和“反反反”则重来，这不就行了吗？不过，这种方法有一个局限性：它不能保证整个过程在有限步之内完成。而我们刚才的方法中，总的步骤数有一个上限：三步之内必然完成。

我们的问题是：是否对于所有的正整数 n ，都能找到两枚合适的硬币，使得借助它们便能在有限步之内概率均等地产生一个 1 到 n 之间的整数？

Read more…

一个圆内接八边形，各边长度依次为 2, 2, 2, 2, 3, 3, 3, 3 。求这个八边形的面积。

Read more…

假设平面上有 1 + 2 + 3 + … + n 个小球，每个小球的质量都是 1kg 。它们排成了一个三角形阵，具体地说，它们排成了一个倒置的、以 (0, 1) 为顶点的等边三角形。这个三角形阵作为一整个物体，它的重心的 y 坐标是多少？我们有两种不同的求解方法。

Read more…

大家或许知道 Fibonacci 数列 1, 1, 2, 3, 5, 8, … 有一个非常漂亮的性质：数列中的相邻两项之比将会越来越接近黄金比例 (1 + √5) / 2 ≈ 1.618 。事实上，如果我们用 F(n) 来表示第 n 个 Fibonacci 数的话，那么当 n → ∞ 时，我们有 F(n + 1) / F(n) → (1 + √5) / 2 。

不过，可能有人并不知道，如果把 Fibonacci 数列的前两项换成两个其他的正整数（但保持 Fibonacci 数列的递推关系不变），由此所得的广义 Fibonacci 数列当中，相邻两项之比仍然会趋近于 (1 + √5) / 2 。比方说，如果数列的前两项为 7, 2 ，那么整个数列的前 15 项以及相邻两项之比的情况如下：

7, 2, 9, 11, 20, 31, 51, 82, 133, 215, 348, 563, 911, 1474, 2385, …
 
2 / 7 = 0.28571429…
9 / 2 = 4.5
11 / 9 = 1.2222222…
20 / 11 = 1.8181818…
31 / 20 = 1.55
51 / 31 = 1.6451613…
82 / 51 = 1.6078431…
133 / 82 = 1.6219512…
215 / 133 = 1.6165414…
348 / 215 = 1.6186047…
563 / 348 = 1.6178161…
911 / 563 = 1.6181172…
1474 / 911 = 1.6180022…
2385 / 1474 = 1.6180461…

更神奇的是，即使最前面这两个数当中有一个负数或者都是负数，相邻两项之比的趋势依旧不变！举个例子，若数列的开头两项是 20 和 -13 ，则有：

20, -13, 7, -6, 1, -5, -4, -9, -13, -22, -35, -57, -92, -149, -241, …
 
(-13) / 20 = -0.65
7 / (-13) = -0.53846154
(-6) / 7 = -0.85714286
1 / (-6) = -0.16666667
(-5) / 1 = -5
(-4) / (-5) = 0.8
(-9) / (-4) = 2.25
(-13) / (-9) = 1.4444444
(-22) / (-13) = 1.6923077
(-35) / (-22) = 1.5909091
(-57) / (-35) = 1.6285714
(-92) / (-57) = 1.6140351
(-149) / (-92) = 1.6195652
(-241) / (-149) = 1.6174497

事实上，不管数列的开头两项是多么奇怪的两个实数（比如 -7/2, √2, … 或者 π/10, -√e, … 等等），按照 Fibonacci 式的递推关系算出后面各项，相邻两项之比几乎总会趋于 (1 + √5) / 2 ！注意，刚才我们使用了“几乎”一词，因为这个结论其实并不总是成立。今天的题目就是：请你找出至少一个反例。也就是说，你需要找出至少一个由递推关系 a(i) = a(i – 1) + a(i – 2) 生成的数列，使得当 n 趋于无穷大时 a(n + 1) / a(n) 并不趋于 (1 + √5) / 2 。

对了， 0, 0, 0, 0, 0, … 这种情况自然不算。

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…