[傳說] 在美國， 20分鐘內能回答出這道題的人，年薪超過10萬(+解答)

[micht]

在美國， 20分鐘內能回答出這道題的人，年薪超過10萬

5個海盜搶到了100顆寶石，每一顆都一樣的大小和價值連城。
他們決定這麼分：
1。抽籤決定自己的號碼（1，2，3，4，5）
2。首先，由1號提出分配方案，然後大家5人進行表決，當且僅當超過半數的人同意時
，按照他的提案進行分配，否則將被扔入大海喂鯊魚。
3。如果1號死後，再由2號提出分配方案，然後大家4人進行表決，當且僅當超過半數
的人同意時，按照他的提案進行分配，否則將被扔入大海喂鯊魚。
4。以此類推

條件：
每個海盜都是很聰明的人，都能很理智的判斷得失，從而做出選擇
問題：
最後的分配結果如何？

提示：
海盜的判斷原則： 1.保命 2.儘量多得寶石3.儘量多殺人

（哈 有興趣的朋友可以解一解....)

解答已貼 http://www.formosamba.com/phpBB3/viewtopi ... 6256#66256

[imagenooks]

如果是一號的話

把 100 顆鑽石 分成四份 給 2 3 4 5 海盜

有寶石拿當然同意 ...

:D

[fiona]

如果我是五號我肯定不要拿平均數
嘿嘿嘿~~~

[Allenr]

在美國， 20分鐘內能回答出這道題的人，年薪超過10萬

5個海盜搶到了100顆寶石，每一顆都一樣的大小和價值連城。
他們決定這麼分：
1。抽籤決定自己的號碼（1，2，3，4，5）
2。首先，由1號提出分配方案，然後大家5人進行表決，當且僅當超過半數的人同意時
，按照他的提案進行分配，否則將被扔入大海喂鯊魚。
3。如果1號死後，再由2號提出分配方案，然後大家4人進行表決，當且僅當超過半數
的人同意時，按照他的提案進行分配，否則將被扔入大海喂鯊魚。
4。以此類推

條件：
每個海盜都是很聰明的人，都能很理智的判斷得失，從而做出選擇
問題：
最後的分配結果如何？

提示：
海盜的判斷原則： 1.保命 2.儘量多得寶石3.儘量多殺人

（哈 有興趣的朋友可以解一解....)

這一題好玩啊，我這邊剛好上完Game theory，不過這一題的難度大概會比後天的期末考還難一些...，我剛試了一下，
花了11分鐘，不知道答案對不對，不過不管你算不算得出來，
相信我：10萬美金的年薪可沒這麼好拿 XD

解題法: 畫decision tree，反向推論

Ph1: 只有4和5活著時，無論4提出甚麼方案，4都死定了

Ph2: 承上，所以4絕對不會讓3死. 也就是說3可以提出以下這個方案:

海盜 3 4 5
寶石 100 0 0

而仍得到3 和 4的票過關

Ph3: 承上，4和5當然會很不爽，所以如果2的方案能讓4和5分到超過0顆寶石，2就不用死，於是
2會提出以下方案:

海盜 2 3 4 5
寶石 98 0 1 1

注意，反正3一定反對2的存活，所以乾脆不用分給3任何寶石，此時2的方案會得到 2, 4, 5的票過關

Ph4: 承上， 3 4 5還是不夠爽，所以1就有活命的機會：只要他的方案能帶給2345中任兩人更大的好處就行:

海盜 1 2 3 4 5 海盜 1 2 3 4 5
寶石 97 0 1 2 0 或 寶石 97 0 1 2 0

此時3是鐵票，加上1自己就有兩票，所以1只要給4和5中任何1人超過1顆寶石就可爭取到那關鍵一票。

結果:

海盜 1 2 3 4 5 海盜 1 2 3 4 5
寶石 97 0 1 2 0 或 寶石 97 0 1 2 0


不可思議嗎? 我也這麼覺得，如果我算錯了請不要笑我。畢竟人家Nash拿到諾貝爾獎前還發了一陣瘋...

[維尼]

天啊
還用 game theory 來解
真猛 :)

我想先問一下
如果最後只剩4號跟5號兩個海盜
4號的提議5號不接受
他也要自己跳下去嗎?

[sharonstone]

stone:cc呀...我有一題猜謎很有趣...你來試試
cc(即我之前分享的搞笑個人報作者):好啊...
stone:(copy and paste)
cc:.....只有一個人得到全部的寶石嗎?
stone:根據判斷原則...最後答案不會只有一個人得到...也不會是每人拿20顆
cc:(不到一分鐘)....1必定提出「1-98；2-0；3-1；4-0；5-1」的方案並順利通過
stone:.....
cc:股溝說的...
stone:誰是股溝?
cc:google咩...XDXDXD..."據統計，在美國，在20分鐘內能回答出這道題的人，
平均年薪在8萬美金以上。"
stone:是喔...我版本是10萬咧...
cc:我想我是8元美金吧....XD

[Allenr]

天啊
還用 game theory 來解
真猛 :)

我想先問一下
如果最後只剩4號跟5號兩個海盜
4號的提議5號不接受
他也要自己跳下去嗎?

當且僅當超過半數的人同意時
，按照他的提案進行分配，否則將被扔入大海喂鯊魚。

[Allenr]

stone:cc呀...我有一題猜謎很有趣...你來試試
cc(即我之前分享的搞笑個人報作者):好啊...
stone:(copy and paste)
cc:.....只有一個人得到全部的寶石嗎?
stone:根據判斷原則...最後答案不會只有一個人得到...也不會是每人拿20顆
cc:(不到一分鐘)....1必定提出「1-98；2-0；3-1；4-0；5-1」的方案並順利通過

怪怪滴, 5號若只拿到一顆，他應該寧可先宰掉1號，反正之後2號還是會給他一顆寶石，既然期望值相等，基於多殺人原則，1號是拿不到5號的票的吧?

[reohuang]

沒錯喔~我想allenr的說明是對的喔~

97-0-1-2-0或是97-0-1-0-2都可以成立
(allenr上面的post不小心把數字post成一樣的啦)

[micht]

解答：


這道題是典型的博弈類問題，通過對題乾的分析，我們知道它是一個完全信息的表態博弈問題，因為在解此題時用倒推法，由簡到繁，通過對簡單的模型的分析，從而導出其一般規律。

　　 １）假設只有４，５兩個人來分配，則４號會提出全部占有寶石，而５號無論選同與反對都不會得到一個子，也不會對結果造成影響，同時４、５號都能保命。

　　　那麼４、５號無論如何都不會被處死，在保全了生命後，為使自己利益的最大化，５號會想盡辦法來保全３號的生命以求得到寶石。

　　　　　　　海盜名稱：４　　　　５

　　　　　　　得寶石數：１００　　０

　　　　２）假設有３、４、５三個人來分配，三個人來表決，則５號只要能得到一顆寶石就會支持３號的決定（因為第１步分析得），這樣，３號會做出這樣的分配方案，自己得９９顆寶石，５號得１顆寶石，則無論４號做出什麼決定對結果都不會有影響。大家注意，這樣的策略使４號得不到寶石。

　　　　　　　海盜名稱：３　　　４　　　５

　　　　　　　得寶石數：９９　　０　　　１

　　　　３）假設有２、３、４、５四個人來分配，決策將建立在前一部的基礎之上，２號所提出的方案必須得到其他三個人中的任意一個的支持就能保全自身的生命，同時保證利益最大。首先我們應該清楚一點，無論２號提出什麼方案都得不到３號的支持，他只有在４、５號之間得到至少一個人的支持才能保證自己不被處死，但為了保證利益的最大化，他又只能支付一個人寶石。

　　　　　如果選５號為２號的同盟，則他需要支付至少２顆寶石才能得到５號的支持，（因為如果只給５號碼１顆寶石，５號會分析贊成２號的決定只能得到１顆寶石，反對２號的決定也可以得到３號分配的１顆寶石，那麼５號為了滿足自己多殺人的慾望，還是會反對２號，所以２號只有支付２顆寶石給５號才能得到他的支持）。

　　　　　如果選４號為２號的同盟，則出現另一個結果。在上一步中，４號沒有得到一顆寶石，所以只要２號能滿足他一顆寶石，就能取得他的支持。

　　　　　　　海盜名稱：２　　　　３　　　４　　　５

　　　　　　　得寶石數：９８ 　　０　　　０　　　２

　　　　或

　　　　　　　海盜名稱：２　　　　３　　　４　　　５

　　　　　　　得寶石數：９９　　　０　　　１　　　０

　　　　　做為理性的個體，為求自身利益的最大化，２號會選擇與４號結為同盟，這是最穩定的結構。

４）假設１、２、３、４、５號共同參與表決，則由１號提出分配方案。

　　　　　則１號需要與其它四個當中的至少兩個人結為同盟，但是為了自身利益最大化，他只可能選擇其中的２位結為同盟。那麼他會選哪兩個呢？

　　　　　

　　　　　１號有兩種選擇

　　　　　第一、與２號建立同盟，但自己卻要犧牲至少９９顆寶石（我們清楚，做為２號他已經有了第３）步當中的分配方案來保全生命，並且使自已的利益最大化。只有當１號分配給他的寶石達到或者超過９９顆時，他才會願意與１號結為同盟並且支持他的方案，否則就會反對。）。這樣他自己手上還有１顆寶石，但這一顆並不屬於他，因為根據前面的分析，１號必須有２位同盟，它還得尋找一位同盟才能保住性命。

　　　　　　　　根據第３）步１號可以決定將剩下的１顆寶石給３號４號或者５號，如果給３號會出現這樣的結果

　　　　　　　　海盜名稱：１　　　２　　　　３　　　４　　　５

　　　　　　　　得寶石數：０　　　９９　　　１　　　０　　　０

３號為什麼不會反對呢？如果反對了１號的決定，則輪到２號來分配寶石時，３號將一個子也得不到。所以３號將會很願意與１號結為同盟。

　　 如果給５號會出現這樣的結果

　　　　　　　　海盜名稱：1 ２　　　　３　　　４　　　５

　　　　　　　　得寶石數：0 ９９　　　０　　　０　　　１

此時５號會很樂意與１號結晶為同盟。注：３號對５號並沒有說服力，因為如果５號否定了１號的方案，則１號只有向３號提出結盟，這樣５號不能得到一顆寶石。

如果給４號會出現這樣的結果

　　　　　　　　海盜名稱：１　　　２　　　　３　　　４　　　５

　　　　　　　　得寶石數：０　　　９９　　　０　　　１　　　０

此時４號可能不會與１號結為同盟。因為第３）步當中的穩定狀態４號也只能得到１顆寶石，前後兩種狀態中４號都沒有生命危險，也只得到１顆寶石，但此種狀態下，可以滿足他多殺人，所以４號會反對與１號結為同盟。

　　　綜上所述，在理性的１號選擇了與２號建議同盟後，他只需要再與３、５號當中的一名結為同盟便可以保住性命，但結果是１號得不到一顆寶石。

　　　　　第二、不與２號建立同盟。

　　　　　　　　此處１號需要在３、４、５號當中尋找２位同盟者，在第３）步中我們清楚，在２號提出的方案中，３、４、５號分別分得０、１、０顆寶石，所以理性的１號會可以選擇的同盟有３種組合。

　　　　　　　　如果與３、４號結為同盟　　　　則１號需要支付的寶石數為３顆，其中３、４號分別得１、２顆。

　　　　　　　　如果與４、５號結為同盟　　　　則１號需要支付的寶石數為３顆，其中４、５號分別得２、１顆。

　　　　　　　　如果與３、５號結為同盟　　　　則１號需要支付的寶石數為２顆，其中３、５號分別得１、１顆。

　　　　　　　　綜上所述，在不與２號建立同盟的情況下，１號會選擇與３、５號結為同盟。這樣１號得９８顆寶石。


所以綜合考慮所有的情況後，我們得到１號會選擇與３、５號結為同盟，這樣的分配結果為：

　　　　　海盜名稱：１　　　２　　　　３　　　４　　　５

　　　　　得寶石數：９８　　０　　　　１　　　０　　　１

[reohuang]

解答：


　　 １）假設只有４，５兩個人來分配，則４號會提出全部占有寶石，而５號無論選同與反對都不會得到一個子，也不會對結果造成影響，同時４、５號都能保命。

　　　那麼４、５號無論如何都不會被處死，在保全了生命後，為使自己利益的最大化，５號會想盡辦法來保全３號的生命以求得到寶石。

有沒有人懂上面這個部分的呀？
我怎麼覺得好像不是這樣呢？

啊~我看懂啦~
要看題目的"超過"一半的人同意...有沒有包含剛好一半的狀況
這個解答是用剛好一半就成立的方式來推論的~

恩~這樣的話其實是比"超過且不包含1/2"更困難一點的~~~

[sharonstone]

這裡提供英文版的題目
http://www.1001words.com/2005/01/game-t ... uzzler.htm
解答在此...基本上跟金鋼妹提供的是大同小異
http://www.techinterview.org/Solutions/ ... 00102.html
注意這份英文版題目中說的是"at least 50%"
所以答案跟金鋼妹說的是一樣的
如果是要"more than 50%"...我則同意allenr答案XD

[Allenr]

stone:cc呀...我有一題猜謎很有趣...你來試試
cc(即我之前分享的搞笑個人報作者):好啊...
stone:(copy and paste)
cc:.....只有一個人得到全部的寶石嗎?
stone:根據判斷原則...最後答案不會只有一個人得到...也不會是每人拿20顆
cc:(不到一分鐘)....1必定提出「1-98；2-0；3-1；4-0；5-1」的方案並順利通過
stone:.....
cc:股溝說的...
stone:誰是股溝?
cc:google咩...XDXDXD..."據統計，在美國，在20分鐘內能回答出這道題的人，
平均年薪在8萬美金以上。"
stone:是喔...我版本是10萬咧...
cc:我想我是8元美金吧....XD

這個故事告訴我們: 不要盲目相信辜狗告訴你的東西

[vincemeagei]

各位大大所言皆是
但我們必須了解 下列事實

在保命為最高原則下
1號是不可能選擇一個會讓他送命的方案
讓我們排除推翻規則相戶廝殺的情形 如果如此 最會殺的獨得100顆 我們也不用浪費時間在這解題

所以這個題目應該把它簡化成
在既有的規定下 1 號如何取得其他4人中的2票 來確保自己的分配權

讓我們再分析一下這 5個人的角色

1號
最幸運者
擁有分配權
首要目的在利用其他四人的利益衝突來實現自己利益的最大化

2號
最悲情的角色
因為他擁有最優先的分配繼承權
由於他最大利益在於1號分配權的喪失 即1號的命
此人乃為1號最不可能妥協者 除非1號不要命
這角色有些類似古代的太子
最大利益在於皇帝老子葛屁 自己好登基
只是在這 1號老子不會自動葛屁
所以這優先的分配繼承權 變成他最大的負數

3 號
處於中間的邊緣人
既無分配權 因具備僅次於2號的分配繼承權而不為2號所喜 又被4.5號所猜忌 擔心他一但得權對自己的不利
無可奈何下 只有借打擊2號 做1號走狗來取得利益
也由於此效忠 屬於不得不的生存之道
1號只會賦予最小的利益 來維持其效忠
這角色類似立法院的無黨籍聯盟
當執政黨要通過法案 而票數稍嫌不足時
摸頭給糖 索其支持 但頭不會摸太久 糖也不會給太多

4 號 5 號
德高望重的周瑜和諸葛亮
對1號毫無分配權的威脅 為1號最須尋求支持的對象
可惜兩人性質過近 又無法和諧相處 導致誓不兩立
1號雖須其支持 但已有走狗3號 所以只需其一即可
被放棄者 也只有徒呼 “既生瑜 何生亮”了
此一關係 又有些近似 馬英九和宋楚愉
先有馬懼宋當選副總統影響其總統路
後有宋懼馬變泛藍共主使其變泡沫
陳水扁若有一方支持 則政令無阻