為什麼這篇如何 挑 石頭鄉民發文收入到精華區：因為在如何 挑 石頭這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者grassboy2 (小胖子．吳草兒)看板Math標題[機統] 河邊撿石頭問題，撿到最大顆的機率...
如何 挑 石頭 在 Valentine in Paris︱巴黎 Instagram 的精選貼文
2021-09-17 04:14:06
這個禮拜的Vlog裝潢影片已經上線了 請來Youtube觀看首播喔 這個禮拜主要想跟大家分享 1⃣️如何挑選壁爐 @planikafires 2⃣️浴室洗手台的設計 我們期待了很久的 訂製壁爐終於收到了 木工師父也幫我們安裝進去了 下一步就是請石材鐵工還有玻璃廠商來丈量 再進一步製作 因為...
河道上有 n 個石頭，依序去看，看到一顆你覺得最大顆的石頭就撿，
只有一次機會，只能撿一顆，放棄的石頭不能回頭撿
用什麼方法撿，可以盡可能讓撿到的石頭是最大顆的？
解法A：
先看完前 n/2 顆石頭，後 n/2 顆石頭只要遇到比前 n/2 顆都大的話就撿
假設有 n 顆石頭，第二大顆出現在前一半的機率是 50%，
最大顆出現在後一半的機率是 50%
所以這個策略共有 50%*50% = 25% 的機率撿到最大顆
最近看過有影片在討論這個問題 https://www.youtube.com/watch?v=GXjlYWw7ZPI
不過從這個影片回頭檢視解法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://www.ptt.cc/bbs/Math/M.1628741141.A.9B7.html
推 LPH66 : 解法 A 沒算到前 n/2 顆出了不是第二大 08/12 12:29
→ LPH66 : 但後 n/2 中第一個比較大的就是最大的狀況 08/12 12:29
→ LPH66 : 例如前半有第三大, 但第二大排在最大的後面 08/12 12:30
！！懂了！！原來有這個盲點！太感謝了m(_ _)m
→ LPH66 : 啊, 我是在說 25% 算法的問題沒錯 @@ 08/12 12:35
推 arrenwu : 其實我不太懂這問題的「策略」長什麼樣子 08/12 13:07
→ arrenwu : 不然只是要最大機率，不就把n科都看完選最大的？ 08/12 13:07
→ Ricestone : 走過去不能回頭 只能撿一次 08/12 13:07
→ Ricestone : 這就麥穗問題 08/12 13:08
→ mantour : 37%的解法的前提是假設石頭大小跟排列順序完全無關 08/12 15:48
→ mantour : 。所以還有進階題：如果是兩人對賭，對方可以猜測 08/12 15:48
→ mantour : 你可能的策略來排石頭的順序，盡量讓你拿不到最大 08/12 15:48
→ mantour : 的，又因應對方可能的策略，你也可以對應的調整策 08/12 15:48
→ mantour : 略，那雙方的最佳策略為何？ 08/12 15:48
降子變因不會太多嗎？我針對你針對我的策略擬定新的策略降子？→ HeterCompute: 這問題真的問到爛了，各種包裝這問題的都看過，還有 08/12 22:05
→ HeterCompute: 每次看這問題都期待到底有沒有其他變形好玩 08/12 22:05
推 arrenwu : 這個問題對於石頭大小相關的 Prior Distribution 08/12 22:26
→ arrenwu : 是啥樣子啊？ 08/12 22:26
推 LPH66 : 最一開始的問題的話就是 n! 種大小排列等機率吧 08/13 00:43
※ 編輯: grassboy2 (122.116.92.241 臺灣), 08/13/2021 11:56:48→ charlie1667 : 為什麼兩人要互相 一人排一人撿就好啦 08/13 12:05
→ charlie1667 : 兩邊石頭set一樣的話等撿自己set裡最大那顆就好啦 08/13 12:07