※ 引述《buffalobill (水牛比爾)》之銘言：
: A,B,C三人要秘密地選擇1,2,3其中一個數字
: 然後同時公開，將被選中的數字去重複形成集合
: 比如A選2, B選1, C選1, 那麼集合就是{1,2}
: 比如A選2, B選2, C選2, 那麼集合就是{2}
: 對A,B而言，集合越大越好
: 對C而言，集合越小越好
: 問
: 1)若三人皆隨機選擇，則集合大小的期望值為？
: 2)若A可以跟B討論策略，但是C能聽到A跟B的討論
: 則有什麼策略可以最大化集合大小的期望值？
1) 19/9
三個人選三個數字，總可能性27種組合
集合大小為3的有6種
集合大小為1的有3種
剩下的都是集合大小為2的，有27-6-3=18種
期望值為 (6*3 + 18*2 + 1*3)/27 = 57/27 = 19/9
2) 試列舉幾種策略
策略 甲
A跟B說，我選1你選2，這樣我們一定不會重複
但C聽到一定不會選3，集合大小固定為2
還不如隨機...
策略 乙
A跟B說，我選1，你隨機選2跟3，這樣我們一定不會重複
但C聽到一定也選1，期望值跟甲策相同為2
策略 丙
A跟B說，我隨機選1或2，你隨機選1或3，這樣我們重複率下降
C聽到分析了一下，3/4會出現1 1/2會出現2 1/2會出現3，於是C選1
C選1的話 有1/4集合大小為1 2/4集合大小為2 1/4集合大小為3
1/4+2*2/4+3*1/4 = 2，期望值與甲乙兩策相同
策略 丁
看到甲乙丙策期望值都不如隨機
A不屈不饒又想了一下，跟B說
我1/3機率選擇1，2/3機率選擇2
你1/3機率選擇1，2/3機率選擇3
C聽到分析了一下，出現1的機率是5/9 出現2的機率是6/9 出現3的機率也是6/9＊於是不失一般性C選了2
期望值為 2*1/9 + 3*2/9 + 2*6/9 = 20/9！
終於出現了期望值高於隨機的策略了！
策略的盡頭
最後A想通了
關鍵就是
A以 1/X 機率選擇1，(X-1)/X 機率選擇2
B以 1/X 機率選擇1，(X-1)/X 機率選擇3
適當調整X的值，使得兩人的選擇中出現1的機率，等於出現2也等於出現3的機率
此時不論C如何選，集合大小的期望值為最大
出現1的機率為：AB都選1的機率+A沒選1而B選1的機率+B沒選1而A選1的機率
(1/X^2) + (X-1)/X^2 + (X-1)/X^2
=(1+X-1+X-1)/X^2
=(2X-1)/X^2
出現2的機率：(X-1)/X
出現1機率與出現2機率相等：
(2X-1)/X^2 = (X-1)/X
解得 X = ( 3±Sqrt(5) )/2
因X-1為機率要大於零，故取 X = ( 3+Sqrt(5) )/2 約 2.618
最佳策略：
A以 1/2.618 的機率選擇1，1.618/2.618 機率選擇2
B以 1/2.618 的機率選擇1，1.618/2.618 機率選擇3
看到1.618大家應該就知道這是黃金分割 φ 了
X = φ+1
假設C選1，計算期望值：
集合大小為1的機率為 1/X^2
集合大小為2的機率為 2 * 1/X * (X-1)/X = (2X-2)/X^2
集合大小為3的機率為 (X-1)^2 / X^2 = (X^2-2X+1)/X^2
1/X^2 + 2*(2X-2)/X^2 + 3(X^2-2X+1)/X^2
=(1+4X-4+3X^2-6X+3)/X^2
=(3X^2 -2X)/X^2
=3-(2/X)
=3-(2/2.618) 約 2.236 比20/9還大一些些
以上
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.234.4 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1674810431.A.CA7.html