用骰子選人當鬼 - 拼圖

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 個人。

--