1. 先证明小於 2 不可能。 如果期望值小於 2，那一定至少有一种情况是投了一次就决定的， (若 E(X) < k 则 X 一定要在某些时候 < k 吧) 但是那种情况本身就占了 1/6 的机率了，所以不可能。 2. 接下来我们来正式攻击这个问题，先把解答空间正规化。 因为掷骰乃决定人选的唯一资讯，所以任何一种决定的情况， 一定是掷出了若干个号码，并且该组号码 (字串) 决定的人选是固定的。 那麽我们针对每个人选会被哪些字串选定来分成 7 个集合，例如： S1 = { 123, 633, 44, ... } S2 = { 55, 1244, 1245, ... } ... 这 7 个集合里的字串会有以下的性质： a) 7 个集合中不存在两个字串使得一者为另一者的 prefix (例：有 123 就没有 1234，因为掷出 123 的时候就决定了，没机会出现 1234) b) 若 n(A) 代表字串 A 的长度，则 Σ (1/6)^n(A), A \in Si = 1/7 (机率合为 1/7，题目要求) 所有符合以上条件的 S1, ..., S7 就是这个问题 solution space。 (一言以蔽之，这很接近 Huffman coding http://en.wikipedia.org/wiki/Huffman_coding ) 那麽我们要追求的就是 字串长度期望值 = Σ n(A) * (1/6)^n(A), A \in S1, ..., S7 的最小值。 3. 我们现在要来说明字串的内容并不重要，并且等长的字串是可以互换的。 假设 S1 = { ..., 1313, ... } S2 = { ..., 2345, ... } 如果我们把这两个字串互换，解答的条件依然会成立。 再假设 S1 = { ..., 1313, ... } S2 = { ..., 23451, ... } S3 = { ..., 23452, 23453, ... } S4 = { ..., 234541, 234542, 234543, ... } 如果我们把 1313 换成 2345，然後全部的 2345* 都换成 1313*，解答也依然成立。 4. 现在要用 3. 的引理来创造无穷递降法的条件。 假设存在一个解，其中某个 Si 集合中，长度为某 k 的字串有 6 个以上， 例如 S1 = { ..., 4432, 4516, 1461, 1123, 4215, 4142, ... } 那麽我们可以利用 3. 的结论把这六个字串的 prefix 换成一样的： S1 = { ..., 4432, 4431, 4433, 4434, 4435, 4436, ... } (因为 4432 的存在, 4/44/443 都不可能存在, 故 4516 → 4431 一定换得到) 然後我们可以把这六个字串合并，变成 S1 = { ..., 443, ... } (因为掷出 443 之後下一个掷出什麽都一样是选到 S1) 这时候我们得到了另一个解，而它的投掷数期望值变小了。所以原本的解并非最佳解。 也就是说若最佳解存在，它的七个集合中的任一个里，同样长度的字串不会超过 5 个。 5. 考虑 S1 中 长度为 t 的有 Nt 个，那麽 N1 * 6^-1 + N2 * 6^-2 + ... = 1/7 (S1 中的机率合要是 1/7) 如果 N1, N2, ... 都不超过 5，那就只有唯一解了──因为它就是 1/7 的六进位小数。 1/7 = 0.0505050505... 而我们手上的解正好就是如此，所以证明了它是最佳解。 6. 故表达这个解最简单的型式是： 掷骰的点数 (0~5) 依序代表某六进位小数的位数，一旦掷到确定该数会落在 (0, 1/7), (1/7, 2/7), (2/7, 3/7), ... , (6/7, 1) 的其中一个区间即停止。 根据 3.4. 两点，所有的最佳解都可以经由置换字串变成这个标准解。 这个解与这个证明可以推广到任意 n 面骰，决定任意机率分布 P1, ..., Pm 的 m 个人。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.168.222.242