Re: [問題] 用骰子選人當鬼

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者isnoneval (虛物之海)時間12年前 (2012/11/29 23:32)推噓5(5推 0噓 1→)

留言6則, 5人參與討論串3/10 (看更多)

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