PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[問題] 用硬幣決定

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (小維)時間15年前 (2010/08/14 15:15), 編輯推噓8(8推 0噓 19→)
留言27則, 7人參與, 最新討論串1/1
之前出現過「八人抽籤，如何利用骰子公平決定」的問題。 (答案是利用骰子有八個角，挺妙。) 新問題駕到！ 請問如何利用一枚公正硬幣，從七人中公正抽出一人呢？ ps.若有ＯＰ(或數學版出現過)請見諒。 pps.忽然領悟到，解答使用的原理可以產生任意機率！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.164.15.143
推
08/14 15:24, , 1F
丟三次 共八種情況 其中一情況為重來一次
08/14 15:24, 1F
→
08/14 16:38, , 2F
13人、17人......都能比照辦理?
08/14 16:38, 2F
推
08/14 17:51, , 3F
如果沒有限定要最少次數 幾個人都可以吧
08/14 17:51, 3F
→
08/14 17:52, , 4F
13個人就丟4次16種情況 多的3種為重來
08/14 17:52, 4F
這樣處理亦可... 拿硬幣投擲。容易證明一直到第N次才出現正面的機率是 (1/2)^N ___ 再把 1/7 化為 2進位小數 1/7 = (0.001) 現在約定每個人投擲硬幣 2 直到第 k 次出現正面，若k≡1 (mod 3) 則算抽中，這樣的機率恰為1/7 (考慮公平，第二個抽的人應該改成1/6，第三人改成1/5...依此類推。) 其餘機率都可以比照辦理，二進小數循環可以表達所有有理數，因而 ____ 例如1/5 = (0.0011) ，代表「抽中」的事件為 k ≡ 0 or 3 (mod 4)。 2 ※ 編輯: jurian0101 來自: 218.164.15.143 (08/14 18:24)
推
08/14 20:52, , 5F
原 PO 的方法太麻煩了，反正都一樣沒辦法保證次數上限
08/14 20:52, 5F
→
08/14 20:53, , 6F
沒必要採用這麼複雜的作法，上面簡單的就行了
08/14 20:53, 6F
並不是。雖然計算二進位不見得好算，但無論什麼機率，投擲次數的期望值都只有兩次。 更何況絕大部分情況不需要真的把整個循環節算出來。
推
08/15 10:38, , 7F
第 一題: 用八面骰...
08/15 10:38, 7F
→
08/15 11:04, , 8F
樓上讓我一陣寒風吹過...
08/15 11:04, 8F
※ 編輯: jurian0101 來自: 218.164.17.56 (08/15 13:47)
推
08/16 02:11, , 9F
不對。你所謂「期望值兩次」是指「判斷特定一個人有沒
08/16 02:11, 9F
→
08/16 02:11, , 10F
有被選中」而言，假如他沒被選中，你還是要繼續擲、直
08/16 02:11, 10F
→
08/16 02:11, , 11F
到有人被選中為止。具體來說，用你的方法，「從七個人
08/16 02:11, 11F
→
08/16 02:11, , 12F
當中選出一人」全部操作完畢後總共擲硬幣次數的期望值
08/16 02:11, 12F
→
08/16 02:11, , 13F
會是八次，可是若用上面的簡單方法，總共只要擲 24/7
08/16 02:11, 13F
→
08/16 02:11, , 14F
次，甚至還不到四次。是故你的方法從期望值的觀點也是
08/16 02:11, 14F
→
08/16 02:11, , 15F
相對麻煩的。
08/16 02:11, 15F
→
08/16 02:13, , 16F
更正一下，你的方法的期望值應該是 54/7，因為最後一
08/16 02:13, 16F
→
08/16 02:13, , 17F
個人就不用再擲了，直接選中
08/16 02:13, 17F
→
08/16 02:19, , 18F
再更正一下，應該是 52/7，因為用你的方法處理 1/2 機
08/16 02:19, 18F
→
08/16 02:20, , 19F
率的時候比較特別，投擲期望值只有一次而非兩次。
08/16 02:20, 19F
→
08/16 02:23, , 20F
結果你的方法恰比簡易法期望多擲四次
08/16 02:23, 20F
推
08/16 05:25, , 21F
用硬幣決定公正的七人有那麼難嗎??
08/16 05:25, 21F
→
08/16 05:25, , 22F
就假設再多一個虛擬的人, 湊到八人...
08/16 05:25, 22F
→
08/16 05:26, , 23F
然後擲硬幣三次決定, 若是中那個虛擬的人就重來...
08/16 05:26, 23F
→
08/16 05:26, , 24F
這樣就可以公平了....
08/16 05:26, 24F
推
08/16 13:14, , 25F
從同樣的地方丟到地上7次，看哪次滾最遠 XD
08/16 13:14, 25F
_ _ 最近跟Project Euler 打交道，思路變的很制式化的樣子 \ ∪ " 其實我誤會上面講的「投到第八種狀況則重來」是每個人都各投三次的意思， 事實上是大家分一分，一共投三次即可。想到上面我的作法時，我主要是得意說 不管來幾個人都可以用套用同一種作法 (懶惰鬼一名) ，後來想想其實按照數目 順序給每個人安排情況 ...好像更簡單呢？ (啊咧，不也用二進位就好了嗎~~ 電腦懂我不懂，可謂盲點。) 的確，無論什麼情形，我的所謂"簡易法"都是比較麻煩，總不是最優化的。 (這也難怪我會寫出一大堆疊床架屋摧毀CPU的程式碼~~) 謝謝大家的指教。 (∪_∪) ※ 編輯: jurian0101 來自: 218.164.17.133 (08/16 17:00)
推
08/16 19:48, , 26F
我想你的方法只有在一個情況下會勝出，就是當你需要決
08/16 19:48, 26F
→
08/16 19:49, , 27F
定一個無理數機率的時候……但生活上應該沒那種狀況
08/16 19:49, 27F
‣ 更多 jurian0101 的文章
文章代碼(AID): #1CPaAQ-y (puzzle)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 jurian0101 的文章
文章代碼(AID): #1CPaAQ-y (puzzle)