作者tml (流刑人形)
看板puzzle
標題[中譯] ProjectEuler 444 The Roundtable Lotter
時間Sun Nov 10 08:07:04 2013
444. The Roundtable Lottery
http://projecteuler.net/problem=444
有p個人圍在一圓桌前進行交換刮刮樂的遊戲。遊戲一開始每個人都會拿到一張刮刮樂，
其面額為不重複的1到p元。每個人的遊戲目的是要在離開遊戲時有最高的獎金。
首先亂數選定一個玩家作為開始，沿著圓桌依序進行遊戲，輪到一個玩家時，他可以有
以下兩種選擇：
‧刮開他的那張刮刮樂並將其面額展示給所有其他玩家看。
‧把他的刮刮樂和前面已經刮開的任一玩家交換，然後拿著那張已經刮過的刮刮樂離
開遊戲。刮刮樂被換掉的玩家則將新到手的那張刮開並展示其面額給所有在場玩家。
當每張刮刮樂都被刮開則遊戲結束，還在場的玩家只能離開並兌現自己手頭的刮刮樂。
假設每個玩家都選擇了兌現期望值最高的策略。
令E(p)代表由p個玩家開始的情況下，遊戲結束時才離開的玩家的人數的期望值。
（例如：E(111) = 5.2912當四捨五入到五位有效位數。）
N
令S (N) = Σ E(p)
1 p=1
N
令S (N) = Σ S (p)，對所有k > 1。
k p=1 k-1
請求出S (10^14)並用科學記號給出答案至10位有效位數。以小寫e作為真數與首數的
20
分隔（例如S (100) = 5.983679014e5）。
3
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.155
1F：推 LPH66:34 名入手 XD 結果前半截根本在唬人...(做完的就知道) 11/11 02:32
2F：→ LPH66:不過後半截是 Mathematica 硬上就是了 (死) 11/11 02:33
3F：→ tml:感覺給出E(111)是個滿大的提示...這值這麼小就代表大部分情況 11/11 12:30
4F：→ tml:大家都在拚命換 11/11 12:30
5F：推 utomaya:第53位...前半比較簡單 很容易就理解出最佳策略為何? 11/12 07:01
6F：→ utomaya:主要是卡在後半,這題真的是不簡單...大家都好快 11/12 07:03
7F：→ utomaya:不過這遊戲第一位player也滿衰的 永遠只能拿到一元 11/12 07:04
8F：推 LPH66:話說今天一次要出三題耶 @@ 據說是相關題所以一口氣大放送 11/17 00:37