作者grassboy2 (小胖子．吳草兒)
看板Math
標題[機統] 河邊撿石頭問題，撿到最大顆的機率？
時間Thu Aug 12 12:05:39 2021
河道上有 n 個石頭，依序去看，看到一顆你覺得最大顆的石頭就撿，
只有一次機會，只能撿一顆，放棄的石頭不能回頭撿
用什麼方法撿，可以盡可能讓撿到的石頭是最大顆的？
解法A：
先看完前 n/2 顆石頭，後 n/2 顆石頭只要遇到比前 n/2 顆都大的話就撿
假設有 n 顆石頭，第二大顆出現在前一半的機率是 50%，
最大顆出現在後一半的機率是 50%
所以這個策略共有 50%*50% = 25% 的機率撿到最大顆
最近看過有影片在討論這個問題
https://www.youtube.com/watch?v=GXjlYWw7ZPI
裡面也有完整算式導出答案是 37%
不過從這個影片回頭檢視解法A的策略
假設最大顆出現在第 (n/2)+1 顆，機率 1/n*( (n/2)/(n/2 ))
： (n/2)+2 ： 1/n*( (n/2)/(n/2 + 1 ))
： (n/2)+3 ： 1/n*( (n/2)/(n/2 + 2 ))
： ：
： ：
假設最大顆出現在第 (n/2)+(n/2) 顆，機率 1/n*( (n/2)/(n/2 + (n/2 - 1) ))
故採解法 A 的策略，撿到最大顆的機率為上面所有機率加總
即
1/2 * (1/(n/2) + 1/(n/2+1) + 1/(n/2+2) + ... + 1/(n-2) + 1/(n - 1))
= 1/2 * (ln(n) - ln(n/2))
= 1/2 * ln(2)
= 0.3465...
也就是 34.7% 的機率
為什麼策略A用兩種不同的思路算機率，會得出差異如此大(25% vs 34.7%)的結果？
有人可以協助點出算出 25% 的盲點嗎？
謝謝 m(_ _)m
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.92.241 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1628741141.A.9B7.html
1F：推 LPH66 : 解法 A 沒算到前 n/2 顆出了不是第二大 08/12 12:29
2F：→ LPH66 : 但後 n/2 中第一個比較大的就是最大的狀況 08/12 12:29
3F：→ LPH66 : 例如前半有第三大, 但第二大排在最大的後面 08/12 12:30
！！懂了！！
原來有這個盲點！太感謝了m(_ _)m
4F：→ LPH66 : 啊, 我是在說 25% 算法的問題沒錯 @@ 08/12 12:35
5F：推 arrenwu : 其實我不太懂這問題的「策略」長什麼樣子 08/12 13:07
6F：→ arrenwu : 不然只是要最大機率，不就把n科都看完選最大的？ 08/12 13:07
7F：→ Ricestone : 走過去不能回頭 只能撿一次 08/12 13:07
8F：→ Ricestone : 這就麥穗問題 08/12 13:08
9F：→ mantour : 37%的解法的前提是假設石頭大小跟排列順序完全無關 08/12 15:48
10F：→ mantour : 。所以還有進階題：如果是兩人對賭，對方可以猜測 08/12 15:48
11F：→ mantour : 你可能的策略來排石頭的順序，盡量讓你拿不到最大 08/12 15:48
12F：→ mantour : 的，又因應對方可能的策略，你也可以對應的調整策 08/12 15:48
13F：→ mantour : 略，那雙方的最佳策略為何？ 08/12 15:48
降子變因不會太多嗎？我針對你針對我的策略擬定新的策略降子？
14F：→ HeterCompute: 這問題真的問到爛了，各種包裝這問題的都看過，還有 08/12 22:05
15F：→ HeterCompute: 每次看這問題都期待到底有沒有其他變形好玩 08/12 22:05
16F：推 arrenwu : 這個問題對於石頭大小相關的 Prior Distribution 08/12 22:26
17F：→ arrenwu : 是啥樣子啊？ 08/12 22:26
18F：推 LPH66 : 最一開始的問題的話就是 n! 種大小排列等機率吧 08/13 00:43
※ 編輯: grassboy2 (122.116.92.241 臺灣), 08/13/2021 11:56:48
19F：→ charlie1667 : 為什麼兩人要互相 一人排一人撿就好啦 08/13 12:05
20F：→ charlie1667 : 兩邊石頭set一樣的話等撿自己set裡最大那顆就好啦 08/13 12:07