五個囚犯先後從100顆綠豆中抓綠豆。抓得最多和最少的人將被處死,不能交流,可以摸出剩下綠豆的數量,誰的存活幾率最大?

提示:1、他們都是很聰明的人;2、他們的原則是先求保命,再去多殺人;3、100顆不必都分完,但要保證每人至少抓一顆;4、若有重複的情況,則也算最大和最小,一併處死。


謝邀。

這道題怎麼做,取決於我們如何從數學的角度理解題干中這句話:
「他們的原則是先求保命,再去多殺人」。

我的理解是:

  1. 每個人採取方案,使得剩下的人在採取最佳方案的時候,自己的存活概率最大;
  2. 如果有多種方案使得自己的存活概率最大且相同,則採取殺死人最多的方案;

假設我的理解正確,那麼,這道題將會有一個可怕的答案。

定義: m_{n} 為第 n 個人取走的綠豆數,而 M_{n} 為前 n 個人取走的總綠豆數


引理 1
n 個人 (1leq nleq 3) 取過綠豆時,如果被取走的綠豆數滿足
20n<M_{n}<95+n
則第 n+1 個人應該取 m_{n+1} =minleft( 96-M_{n}+n,left[ frac{M_{n}-1 }{n}  
ight]   
ight) 顆綠豆』

證明:

這個方案,可以確保自己不死,同時剩下未取豆子的人死亡概率最大。

其中:

  • 96-M_{n}+n 是確保剩下的人至少有一顆綠豆可選,且自己至少取了 2 顆;
  • left[ frac{M_{n}-1 }{n}  
ight]   是確保自己取的綠豆數至少比前面取的最多的人少 1 ;

由於 M_{n}>20n, 有left[ frac{M_{n}-1 }{n}  
ight]  geq 20, 這不僅保證了自己取的豆子數不是最多的,並且其他人不可能都取到那麼多,所以自己必然存活;

  • 如果 left[ frac{M_{n}-1 }{n}  
ight]  < 96-M_{n}-n,他在確保自己存活的情況下,使得剩下的豆子數最少,這樣可以殺更多的人;
  • 如果 left[ frac{M_{n}-1 }{n}  
ight]  geq  96-M_{n}-n,他在確保自己存活的情況下,剩下的人每個人只能取 1 顆豆子,確保殺死剩下的所有人;

推論1:如果第 1 個人想要存活,那麼他取的豆子數不能超過 20 顆,否則,後面的人只要採取引理1 的方案,將保證自己存活,且此時第 1 個人會因為取的綠豆數最多而死亡,而最後 1~3 個人(根據第 1 個人取的綠豆數)會因為自己取的豆子數最少而死亡;


引理 2:當 n=2,3時,若M_{n}leq 20n
則第 n+1 個人應該取 m_{n+1} =left[ frac{M_{n}}{n}+0.5
ight] 顆綠豆』來確保自己的存活概率最高

(其中,left[ frac{M_{n}}{n}+0.5
ight] 是均值的四捨五入)

因為當且僅當在這種情況下,只要前面的人取的綠豆數的最大最小值之差不小於 2,自己就確保能存活(否則存活範圍會變窄)

* 對於第 5 個人,這個條件可能不成立,比如見到前面四個人取了 62 顆, 可能是 14+16+16+16,也可能是 15+15+15+17,所以他無論取 15 顆還是 16 顆都有機會但不能確保自己存活。

而所有人取綠豆的最大最小值的差不大於 1,所有人都得死;

引理3: 當大家都極度自私的情況下,前 2 個人沒有存活的可能

這是因為由引理2,如果第 3~5 個人都會採取對他們而言存活概率的方案,如果第 2 個人和第 1 個人取的綠豆數差超過 1 個,那前兩個人就包攬了最大最小值,必須死,如果差不超過1,則所有人都得死;

既然第 1 個人沒有存活概率,那他的目標就很耐人尋味了:

如果自己沒有存活概率——
選擇1:殺死儘可能多的人
選擇2:儘可能拯救更多的人

按照我的假設,應該是前者。

既然第 1 個人沒有存活概率,不妨讓大家都死得乾淨些——取走 96 顆綠豆!

但如果,第 1 個人有點惻隱之心,做出了選擇 2:

那,他會取走 21~33 的豆子數,根據 引理1, 第 2~4 個人會存活;

所以,本題根據對題意的不同理解,有兩解:

  • 所有人都死亡;
  • 第 2~4 個人存活;

而對於第 1 個囚犯,他將面臨一個哲學難題:
如果自己不可能活下去,你會選擇讓別人陪葬,還是讓其他人好好活下去?

如果是你,會怎麼選擇呢?

【完】


數學上的解答,各位大牛已經詳盡了。此題還有邏輯上的簡便方法。以及,數學之外的思考。

(看我的答案前,最好先看過其他大牛的數學解答。才不至於對例子陌生。)


題干有個條件:「不能交流」。由於假定每個囚犯都無比聰明,所以交流與否,不影響最終決策。去掉「不能交流」,答案不會有任何變化。


當五個囚犯經過推理,都認定自己必死的時候,有人開始琢磨:


我的推理,都是建立在個人決策的基礎上,假如可以結盟呢?我找兩個人結盟,把剩下兩個人搞死,不就可以了嗎?


想到這裡,a不禁沾沾自喜,看到了絕處逢生的希望,他對b、c、d、e說:我雖然不能讓你們生,但保證能讓你們死。(如果我給你們每人留1個,你們都會死。)現在,上頭要求至少提供兩個死的名額,你們商量出個方案,只要保證我100%不死,我就配合。如果不能保證,誰也活不了。


b聽了,扭頭對c、d、e說:上頭要求至少提供兩個死的名額,a不能死,我也不能死,你們仨商量具體操作方案,如果誰能讓我、a、他都100%不死,同時,又讓其他二人無論如何選擇都無法左右我們三人的結盟,我和a就照辦。如果不存在,你們仨都會死(給你們都留1個)。


c對d、e說:上頭要求至少提供兩個死的名額,a、b、我,都不能死……


d、e說:開什麼玩笑,你的意思不是讓我倆死嗎?你們愛誰死誰死!


a、b、c恍然發現,結盟的可能並不存在。


不存在一種結盟可以保證某人必活。

這個結論可以推廣:


100個囚犯先後從10000顆綠豆中抓綠豆,抓得最多和最少的人將被處死——


結果一樣:所有人都會死。


10000個囚犯先後從100000000顆綠豆中抓綠豆——


仍然一樣:所有人都會死。


圍觀者曰:開玩笑吧?只是從10000人里挑最少和最多的,竟然每個人都會死,太可怕了吧?


答曰:是的。為什麼如此殘酷?在於假定前提——


「每個人都利己,即便不利己,也要損人,損人意味著局部利己。」


這樣的假定下,唯一的結果就是大家都死。假如世界上每個人都是先求利己,利己不成的情況下求損人的話,世界馬上就完蛋,誰也活不了。


既然如此,為什麼我們現在活得好好的呢?

因為真實的世界放鬆了假定。放鬆的第一處是:並不是每個人都絕頂聰明。第二處是:每個人也許都想利己,但不是必然要求損人。


現在考慮,其他條件不變,一點點放鬆第二處假定,看結果如何變化:


a想:唉,我這麼聰明的人,竟然必有一死,既然橫豎都是死,別人死不死關我鳥事,隨便抓一把,去他娘的!


抓了一把,一看:5個。


輪到b,b一摸,發現a抓了5個,心想:


喲,這傢伙居然不是心黑到頂。我最利己的抓法是幾個呢?4個。(分析略,可見樓上諸答。)


如果我抓4個,c、d、e會抓幾個?都是4個。


(5、4、4、4、4)


結果是,大家都死掉。


想到這裡,b倒吸了一口冷氣:想不到我這麼聰明的人,即便a不陷害,也逃不了一死,真是天命、天命啊!隨便抓吧。

抓了17個。


剩下c、d、e,沒得選了,出於利己優先的原則,都選平均數,抓11個。


(5、17、11、11、11)


a、b都死了,後三人活了。


這意味著,只要前面兩人不存心害人,後面人就能活得很好。但先行者的犧牲是難免的。


原始人問現代人:憑啥我們茹毛飲血你們吃香喝辣?


現代人說:憑你投胎早啊。


原始人說:老子得不到的,孫子們也別想得到。——不繁殖了。就沒有現代人了。


但要注意:b的死亡跟a還不一樣。a的死亡,在放鬆假定後很容易避免。b的死亡,則難以避免,並有最大的悲劇意義。


在a隨機抓了5個的情況下(假定a抓5個是為保證剩下的綠豆夠前人的平均數,正因為有不夠平均數的可能,b有能力拯救a,詳論見後):假如b抓的比a多,他一定是因為抓得最多而死掉。假如b抓得比a少,他一定是因為抓得最少而死掉。後來者僅僅出於利己,就會都選平均數。哪怕cde只為利己,不為害人,b都非死不可。

a的死看起來和b類似,其實有重要不同。a可以用他的死彰顯自己的高尚或卑劣:


輪到b時,b發現a抓了96個,破口大罵:王八蛋,自己死就死了,還要拉上俺們墊背!真是爛人!


輪到b時,b發現a只抓了1個,感慨萬千:好人吶,好人。脫離了低級趣味的人。


但是,a抓1個,雖然給其他人留了活命機會,但無論如何救不了b。b最利己的抓法,是抓2個,那麼接下來,c、d、e、會毫不猶豫地都抓2個,同時破口大罵:b這個王八蛋!


因為(1,2,2,2,2),所有人都要死。如果前兩人只抓3個,無論如何,後三人死的責任都在b頭上,哪怕a抓2、b抓1,c、d、e也是必死,他們的死,都是b導致的。(如果b抓50個就不會令他們都死。)


b不管怎麼抓,自己都得死。而且,沒有辦法證明自己是個好人。b出於利己抓2反而損害了自己:非但不能活,還招來一堆唾罵。


b嘆了一口氣:既然橫豎是死,與其死了挨罵,不如死了有人記得我的好。


抓了50個。


輪到c,發現筐里剩下45個,掐指一算,ab的平均數是27.5,他毫不猶豫地抓27。


輪到d,發現還剩18個,他想抓平均數27,不夠了,只好抓了17個。心裡對e說,兄弟,對不住了,不是有意要害你,哥哥自身保命要緊。

(5、50、27、17、1)


b救了a、c、d,犧牲了自己。


c並不知道,自己的命是b救的,他抓的時候還懷疑ab分別抓了(28、27)。d也不知道b救了他。e就更不知道了。


b的善意沒人知道。——除了a。


當a發現自己最終沒死的時候,被b感動得痛哭流涕:好兄弟!


換言之,如果a足夠聰明,他會想到,他的生死,可能決定在b手裡。


比如:a抓5個,b有辦法讓a必活(抓90個)。


但是,這種決定,需要一個前提,即:b有報恩心態。


我們定義一下報恩心態:


弱報恩心態:如果別人表現出對我好,在不影響自利的前提下,我選擇對他好。

強報恩心態:如果別人在可以對我壞的情況下,選擇不對我壞,在不影響自利的前提下,如果我可以對他壞或不對他壞,則選擇不對他壞。


由於報恩心態在世間是真實存在的,所以a存活的幾率很大。


a只要不殺b,放b一馬,b雖知必死,只要有強報恩心態,a就必活。


但世間存在的弱報恩心態比較普遍,強報恩心態相對較少。——如果我活著,讓我對你好當然可以,我都死了,對你好不好我才不在乎呢。


換言之,a的存活取決於b是否具備強報恩心態。而bcde是否必死,取決於a是否追求損人。


如果,a是個平庸但不卑鄙的人(只追求利己,不追求損人),則在後繼者b有強報恩心態的情況下,會享受到先行者的紅利。否則,a會成為死在沙灘上的前浪。


所以,在真實的社會模型中(利己但未必損人的假定下),a一定不會選擇抓96,讓所有人都死掉。


而b,無論如何,既無法享受先行者的紅利,也無法避開後繼者的迫擊,後人僅僅出於自利就會把他弄死,除了先行者感謝他的不殺之恩外,沒有人念他的好。


我們可以把這叫做:「老二的悲劇」。


現在假定,a是高尚的人。


先給高尚一個定義:


弱高尚:如果可以自利,就自利。如果不能自利,利人也好。(這個定義並不嚴密,因為有時候自利牽涉到損人,嚴密的定義太複雜,故從略。另外,報恩心態,也算是弱高尚的一個具體例子。)


強高尚:利人和自利無區別。


強高尚在世人身上鮮少存在,一般只存在於有血緣關係的近親或有宗教信仰的人身上。弱高尚則相對普遍。


假定a是弱高尚的人,他意識到,在世界上不存在其他高尚的人的情形下,自己難逃一死。既然橫豎都是死,不如,做個高尚的人。


a選擇只抓1個。


這就意味著,a以一己之力,讓全世界犧牲的概率最小。


但,這僅僅是概率。a的力量有限,他還需要另一個人的成全。


假如b是庸俗的人,會選抓2個。


c、d、e都是庸俗的人,都只抓2個。


(1,2,2,2,2)


全都死掉。a雖然願意拯救世界,但落空了。


但只要,b、c、d、e里,有一個人,願意抓50個,就能救所有的人,除了自己和a。


a的死,是求仁得仁。自己的死,是捨生取義。


因為有兩人選擇主動犧牲,其他人都可以得救。


假如70億人,先後從1000億綠豆中抓綠豆,最多的和最少的會死掉的話,


只要存在2個以上高尚的人,世界就會得救。


地藏菩薩云:地獄不空,誓不成佛。我們所處的世界並非不險惡,不逐利。但之所以沒有塌陷,還能支撐許多庸凡的人平靜地生活,正因為有聰明絕頂的人,在覺悟了世界的冰冷和絕望之後,自甘做出犧牲來消融世界的冰。


更新一下,把結果貼在了百度網盤上啦:take-21-95.txt_免費高速下載。take.txt是最終可能的結果。take-21-95.txt是當第一個人拿21~95個的時候會怎麼樣。可以驗證一下結果是不是對的。
===

可以寫個程序搜索一下。每個人最多100種選擇,5個人最多100^5(具體些應該是C_{99}^{4}(謝謝 @王霄池指正,應該是 sum_{i=4}^{99}C_{i}^{4})),不算很多。程序的輸出結果表明,每個人都會死。

題目說每個人都先保命,再多殺人。如果再假設當一個人無法保命時,他也要殺更多的人。那麼可以這樣理解:對於每個人來說,自己保命可得5分,另外四個人每死一人得1分。每個人都希望得到更高的分數。假設每個人在最大化自己得分的情況下,隨機做一種選擇,不考慮別人的得分。再簡化一下,在這種情況下,隨機選擇總是有利於之前的人的。另外,每個人在拿的時候,必須給剩下的人每人剩至少1個。

我的程序在我的筆記本上運行20秒左右,共有1714個結果。結果太多,就不貼出來了吧。(對於這種很長的數據,有什麼方便讓別人看的方法么?)簡單分析一下結果吧。第一個人可以選擇96或者1~20。當第一個人選擇1~20時,所有人也都會死的原因是,第二個人由於活不了,會選擇使後面的人都會死的方法來增加自己的得分,第三、四個人也是如此。

如果想看看第一個人選擇其它的數字,比如31,會怎麼樣,可以在後面的程序里改:

takeNum[0] = 31;
getResults(takeNum, 1, 100 - 31);

下面是程序代碼。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* 5個人拿完之後的結果
*/
class Result {

/**
* 每個人拿的數量
*/
private final int[] takeNum;
/**
* 每個人的得分
*/
private final int[] scores;

public Result(int[] takeNum) {
this.takeNum = Arrays.copyOf(takeNum, takeNum.length);
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i &< takeNum.length; i++) { max = Math.max(takeNum[i], max); min = Math.min(takeNum[i], min); } scores = new int[takeNum.length]; for (int i = 0; i &< takeNum.length; i++) { /** * 如果這個人死了,給其他人每人加1分。如果沒死,給自己加5分。 */ if (takeNum[i] == max || takeNum[i] == min) { for (int j = 0; j &< takeNum.length; j++) { if (i != j) { scores[j]++; } } } else { scores[i] += 5; } } } public int getScore(int n) { return scores[n]; } @Override public String toString() { return Arrays.toString(takeNum); } } public class Take { /** * 找第n個人會做出的使其得分最高的選擇 * * @param takeNum 每個人拿的數量 * @param n 第n個人 * @param remain 還剩多少可以拿 * @return 對他最好的選擇 */ static List& getResults(int[] takeNum, int n, int remain) {
ArrayList& results = new ArrayList&<&>();
if (n == takeNum.length) {
results.add(new Result(takeNum));
} else {
int maxScore = Integer.MIN_VALUE;
/**
* 最少拿1個,最多也得給剩下的人每人剩1個
*/
for (int i = 1; i &<= remain - (takeNum.length - n - 1); i++) { takeNum[n] = i; /** * 如果他拿i個,看看後面會怎麼樣 */ for (Result result : getResults(takeNum, n + 1, remain - i)) { int score = result.getScore(n); /** * 記錄使其得分最多的結果 */ if (score &> maxScore) {
maxScore = score;
results.clear();
}
if (score == maxScore) {
results.add(result);
}
}
}
}
return results;
}

public static void main(String[] args) {
int[] takeNum = new int[5];
for (Result result : getResults(takeNum, 0, 100)) {
System.out.println(result);
}
}
}


看Matrix67大牛的博客,讓我學到了一個思維方式,那就是從最簡單的情況開始考慮。

在大家開始看答案之前,我必須指出:因為題目中沒有「每個人都知道其他人也很聰明」這個條件,所以,不會出現A選96顆豆子這種情形

下面是分析:

假設有3個人ABC,10個豆子,其他條件不變。

一開始B是非常緊張的,他開始了思考。

對他來講,有上中下三種策略

  1. 上策:自己活著
  2. 中策:全部死光光
  3. 下策:自己死了,但有其他人活著。

然後他就開始預測A的行為:

  1. A如果拿8顆豆子,B拿1顆豆子,C拿1顆豆子。全死。
  2. A如果拿7顆豆子,現在輪到B做選擇了
    1. B如果拿1顆豆子,C不敢拿1顆,必然拿2顆。C獨活。
    2. B如果拿2顆豆子,C只能拿1顆,B獨活。
    3. 因為B是個理性人,B這個小婊砸一定會拿2顆。AC死了。
  3. A如果拿6顆,B就拿3顆;A如果拿5顆,B就拿4顆。都是B獨活,AC死。(我真的不是在黑A站)
  4. B已經找到了規律,那就是,讓自己拿的數量在AC之間,就可以保證活。想到此處,他不由得笑出聲來。A冷冷的看了他一眼。
  5. A如果拿4顆,現在輪到B做選擇了。
    1. 如果B拿5顆,C只能拿1顆,A獨活,BC死。
    2. 如果B拿4顆,C不論拿幾顆,都是三人同死。
    3. 如果B拿3顆,C在得知前兩人共拿7顆的情況下,選擇拿3顆,三人同歸於盡。
    4. 如果B拿2顆或1顆,C會選擇拿3顆,C獨活。AB死。
    5. B驚奇的發現,不管怎麼選,自己都會死。他是不會選擇讓C這個小婊砸活著的。
    6. 於是B選擇了拿3顆。
  6. A如果拿3顆,B略微思索了一下,也會選擇三個人同歸於盡。
  7. A如果拿2顆,B會拿3顆,但是C哈哈一笑(C已經習慣了在B的腦洞中死亡),他不拿5顆,也不拿4顆,也不會拿1顆,他拿了3顆。三人同歸於盡。
  8. A如果拿一顆,那麼(感謝 @胡昌俊 指正)
    1. B選1顆,3人同死
    2. B選2顆,CC會選擇三人同歸於盡。
    3. B選3顆或以上,C選AB的平均數。AC活,但B死,所以B不會做這個選擇。

但是A也思考了上述的全部過程,A悲催的發現。如果B很聰明,不管自己怎麼選,都是個死(對,你去上面仔細看看,我們已經列舉了所有的情況)。既然這樣,A把希望寄托在B不是很聰明上面,他微微一笑,選了4顆豆子。

ABC卒。

我們歸納出一個定理:如果3個人有n個豆子,ngg 3,且A不知道B和C是不是理性的,他可以選擇[n/3],如果ABC三人都是理性的,他們會同歸於盡。

時光荏苒,有個變態又抓到了4個人,ABCD,然後給了他們20顆豆子。
我們繼續從如果A拿20顆豆子開始分析。啊,不,還是直接寫結論吧。

  1. 當A選擇17個時,同歸於盡。
  2. 當A選擇16到6個時,B活著。A死。
  3. 當A選擇5時,B選4,C選4,D選擇4和大家同歸於盡。
  4. 當A選擇4時,B選5,C選4,D選擇4和大家同歸於盡。
  5. 。。。
  6. A發現自己必死。於是他拿了5顆豆子,他寄希望於其他人高尚一些。
  7. ABCD卒。

轉眼到了2015年,題主抓住了5個人,給了他們100顆豆子。第一個人深吸一口煙,吐出個煙圈,他拿了20個

====程序員的分割線===

後來我又寫了個程序,模擬了如下狀況:
假設所有人都假設其他人的選擇是隨機的(可能是因為每個人都假設其他人可能是聰明人,笨的人,高尚的人,自私的人,抑鬱症患者等),那麼在所有的樣本空間里(75287520種可能性),做出最有利於自己的選擇:
100 left for A
A will chose 10
90 left for B
B will chose 11
79 left for C
C will chose 11
68 left for D
D will chose 10
58 left for E
E will chose 10

源碼在此
math/a.c at master · picasso250/math · GitHub


----已修改(2017.9.14)----

感謝評論區指出各種不足。答主表達能力,邏輯等都比較有限。也歡迎繼續指正。

先說結論:全滅。

所有人先每人拿走1顆,豆子總數變為95。(處理每人至少要一個的狀況)。

證明過程如下:

1:如果A拿走的數量大於19:在此情況下,對於之後每一個人來說,其最優解拿走的個數一定是A-1個或者場上全部豆子。

證明:對於B來說,他知道A拿的數量大於19,則如果他拿A-1個,一定會有人比他少。他一定能活下來。同時,D死的唯一條件是輪到他拿的時候沒有了。否則,他可以選擇拿場上的所有豆子或者同樣拿A-1個。這兩個中一定有一個能讓他活下來。所以BC為了讓D死,要保證安全的情況下盡量多拿。C同理。所以B一定會在保證安全的情況下多拿。

所以,在此情況下,A必死,E必死。BCD不討論。

2:如果A拿走的數量小於等於19:在此情況下,沒有人會拿20個或者以上(否則化為情況1,他必死)。我們從後往前證明。對於每一個人來說,他如果能存活,前面所有人的平均數一定是存活選項之一。E在此情況下(你們的生死與我無關)一定會拿走平均數的數量。D在知道這一情況下,也會拿走平均數數量(他知道如果他能活E就一定能活,沒法殺死E)。CB同理。結果就是每一個人都會和A拿的一樣多,A同樣必死。

3:A在必死的情況下,其最優解為殺死所有人(包括自己)

4:A拿走95個,所有人,卒。

證畢。

btw做了個小程序來驗證,結果如下

代碼就不貼了【幼年程序猿,不獻醜了】


這個問題挺有意思的,分析一下有相對最優解。
推薦一個思路,分倆步答。
第一步,一號位「必死」。
從最後一個人開始考慮,他的最優選擇是:在剩餘的豆子中,選擇前四人取豆平均數,如果剩下豆子數不夠了,儘可能選擇離平均數近的數目,平均數非整數則向平均數下取整。這樣才最有機會成為五個人中取豆數的中位,才有機會活下來。以此類推,四號位會選擇儘可能靠近前三個人取豆的平均數,三號位會選擇儘可能靠近前倆人取豆平均數,二號位則會選擇和一號位一樣的豆子數目。
這樣問題就留給了第一個人,到底取幾個豆子,自己存活概率才最大呢?
首先,一號位,他明白二號位的最優策略是「取和自己相同數目的豆子」,以及後面最優策略就是選擇同樣數目的豆子了,這樣的結果會出現大家都死,自己是活不下去的。雖然一號位可以讓後面人可選豆子數目達不到平均數,但自己必然也成為最大數,自己也會死。所以在不出現「奇蹟」的情況下一號位必死。
第二步,一號位期盼「奇蹟」。
一號位想活下去,最可能的情況是,後面有人發善心,放過他。雖然這種事情概率微乎其微,但這是他唯一的希望,所以一號位會抱著這一絲希望做選擇,這是一號位想活的最後的策略(幾乎不太可能的無奈之舉)。
一號位,不會選1,因為後面人想救他都不行。一號位不會選到3或者以上,因為他明白後面人不傻,一旦自己選3,二號位就會跟著選擇3或者2(2號位不會傻到選4的,會成為最大值),無論二號選擇3或是2,自己的選擇都屬於最大數,必死。如此,一號位,最後唯一的希望就是,自己選擇2,並期待出現「奇蹟」——後面有人發善心,放過自己。
這樣難題就到二號位手裡了。二號位是知道一號位心理的,也知道這是一號位最後搏一搏的策略。不僅如此,二號位,也是想活的,因此他不能跟著選擇2,這樣後面的最優解方案,同樣會導致團滅。所以二號位也不得不,期盼奇蹟——後面有人放過自己。抱著這樣的想法,二號位最終選擇3,因為選4,自己就成為最大值,後面幾個混蛋會選擇平均數3,讓自己見鬼去了。
這樣就明朗了,前面四個人必須期盼出現「奇蹟」——後面有人放過自己。三號位會跟著選3,選4最大值必死,不選2的原因是,期盼最後倆人選1的希望相對更小。這樣四號位也跟著選3。五號位必死,因為他沒有後排人可以指望出現「奇蹟」了。所以五號位會最終選擇一個同歸於盡的2 ,或者3。
因此這場策略最優化選擇的最終結果是:一號位選2,二號位選3,三號位,四號位跟著選3,五號位報復社會,選擇團滅。
雖然最終結果是都死,但是放到每個人具體選擇還是有結果的,因為前4個都抱有出現奇蹟的心,這也是這道題有意思的地方。


第一個人拿 100 個,然後遊戲無法進行下去(要求每人至少拿一個)。
拋出 NoBeanLeftBeforeLastPrisonerException 異常中斷了遊戲,大家都活了下來。

-------------------------我是題目被改了的分割線-------------------------------------------------------
題目改了讓人情何已堪。
反正第一人有辦法讓大家團滅,除非有神奇的原因能使第一人的存活概率不為0,否則就是團滅


我的演算法是團滅。

1.第一個人會想我如果抓21以上的豆子,第二個人會抓20個,至於為什麼不是19個,待會解釋。第三個會想之前抓走41個,這樣總有一個人抓超過20個的豆子,所以我抓二十個豆子就可以不成為最多。(之所以不抓少於20個豆子,是防止成為最少,所以取豆用平均值做參考)。第四個人也是抓20個,保持默契。這樣因為他們知道第五個最多只能抓19個的。最低最高都出來了。這樣第一個由於不符合自救的條件,所以第一個人不會抓21個。同理,五個人都會想到這一點,所以沒有人會抓20個以上的。至於那是否以此類推20個,19個……都不可以抓,基於邊際遞減原理(就好像剪刀石頭布。甲說我要出剪刀,乙猜測是為了迷惑自己出石頭,所以推測甲會出布。但是又想到甲很聰明,也會想到這一點,依次一直推理……這就沒有意義了)第一個人不會取接近20的個數。

2.為什麼第二人與第一人取的豆數之間不要有間隔。因為如果第一個抓20個,第二個抓18個。第三個會想我取兩個人的平均數也就是19個,第四個第五個一樣。這樣第一個第二個都會死。聰明的他們也會想到這一點。所以第二個不會和第一個有間隔。

3.由於如果不取任何豆子,就直接是最少的。所以至少要取1個,相同推理,取1個的必死,所以不能取1個。與推測1相同。第一個人不會取接近1個的豆子。

4.由於推測1、3假設第一個人會取10個豆子。那麼由於推測2,第二個人會取9或11個豆子。(不取10個是為了防止接下來幾個人取平均數造成團滅,雖然並沒有什麼卵用哈)

5.那麼第三個人就會算出平均數是9.5或者10.5。這裡假設第二人取9個豆子,所以平均數為9.5。那麼為了不當最多和最少,第三人只能取9個或10個豆子。但不管如何,第四人算出的平均數是九點幾的數字,所以還是只有走第三人的老路。第五人面對的情況相同。導致團滅。

6.這裡遇到的主要問題是第二人知道第一人所抓的豆子數,但是由於因為推測2所以不敢和第一人產生間隔。而後面的人不敢所抓的豆子數高於或低於平均數2以上。

7.基個人自保的考慮,這個苦逼的題目最終導致的結果就是團滅。

下劃線以下是補充
————————————————————————
來來。我們討論一下第一個人算來算去都是死,於是自暴自棄亂抓的情況。分別有

1.直接抓96個豆子。其他人沒得抓。全部死翹翹。

2.第一個人抓51個豆子以上包括51個不包括100個。那麼為了多殺人,第二個人抓49個。(該情況用於可以不抓豆子)那麼總共會死四個人。

3.第一個人抓50個豆子。第二個抓49個,第三個抓1個。那麼總共會死三個人。

4.第一個人抓豆子數X大於20小於50。第二個抓X-1個。那麼在其他人不犯傻的情況下最多死三人最少死兩人。

謝謝讀者給贊,破零的我很開心 。

………………………………………………………………………
才發現題主居然改題目,至少要抓一個豆子。以上補充抓100個豆子的猜測不想改了,就這樣吧


簡單地說,就是全死。

我理解前提是:如果我能活,我就活;如果我不能活,我就優先拉後面的人死。

題目的前提一:平局一起死,所以一定有人死。
題目的前提二:任何一個人直接拿完所有的,後面的人都是0,必死。

我儘可能簡單地定性分析一下:
1、E不會比前四個中最多的拿得更多,否則E就死了;
2、因為E不會拿最多,那D拿的時候,也不會拿最多,否則D就死了;
3、依此類推,每個人都不會拿最多,所以A拿完後,A就是最多的,A必死;
4、既然A必死,A就可以選擇讓大家一起死,直接拿走100個,剩下都是0,全死。


首先拋出結論:最後博弈的結果一定是五個人全部歇菜!不存在存活幾率,且A可以選擇拿「【1,20】以及96」區間內任意數量的綠豆,結果都是一樣的。且聽我慢慢分析。

有不少知友認為「A拿96顆」或者「A拿20顆」就是最佳策略,而我和大家的分歧就在於A拿1-19顆的結果和前兩者完全相同。

下面說下我的思路,@王霄池 大牛用的是逐漸增加博弈參與者數量的思路來分析,而我則是通過減少參與者數量來分析。

首先明確幾個基本思想:

  1. 大家說此題存在隱含條件,即必須使得自己和後邊的人至少拿到一顆綠豆,私以為這個條件並不重要,我們可以先假設每人手中各拿了一顆綠豆,那麼袋子里還剩下95顆,大家又都處於同一起跑線,所以問題可以理解為95顆綠豆,如何拿最優,其實和100顆如何拿最優基本可以視為同一個問題,唯一的差異就是A是拿96顆還是拿100顆;
  2. 假設A拿m顆,B正常情況下(關於什麼是非正常情況,下面會講到)一定會拿m-1到m+1顆之間,這個是思考這道題的基礎;
  3. 假設A拿m顆,B拿n顆,C正常情況下一定會拿m+n的一半(如果是小數,則近似到最接近的整數),才能盡量保證自己不是最多和最少;
  4. 同理,由於每一個人都清楚剩下綠豆的數量,所以正常情況下,後一個人會選擇拿前面所有人拿的平均數(最多差1);
  5. 有幾個關鍵的數位元組點在我的分析中很重要:20、25、33(34)、50、96;
  6. 在別的回答里,各位大牛已經分析過A的處境和心理了,所以A最後的選擇必然是同歸於盡,而且是千方百計要和其他人同歸於盡,而且是絞盡腦汁地要儘可能和其他所有人同歸於盡((ー`′ー)憑什麼老子死了還得成全你們),這一點我不再贅述了,僅僅說一句:題目中說明了要在自保的前提下多殺人,說明默認了人性邪惡,試問自保了還想著殺人,這樣的人,在無法自保的情況下難道反而想著救別人?所以這的確是一個哲學問題。

搞清楚這些以後,我們開始分析。
一、假設A拿20顆綠豆(注意20是我的第一個數位元組點),
B必須拿19-21顆之間,才能有活的希望,
1)假設B拿20,
C必然在19-21之間選擇,否則大了小了都有可能掛,但是C知道前兩個人極有可能拿了20和20(只要C足夠聰明就一定會考慮到這種情況),如果C此時拿19和21就極有可能要掛,這時候只能拿20,並且期望後兩個人是傻X;
可是D也是個聰明蛋,他長嘆一聲,早已看穿了一切,大不了同歸於盡,欣然拿了20顆綠豆(此時D已經沒得選了,剩下40顆,不管拿幾顆,自己都得死,所以唯一的追求就是多拉幾個墊背的);
E:Σ( ° △ °|||)︴老子招誰惹誰了。
此時的情況是A20,B20,C20,D20,E隨意,大家都得死;
2)假設B拿19,
C必然拿19或者20,假設C拿19,此時剩下42顆綠豆,
D掐指一算,前面三人極有可能兩個拿了19,一個拿了20,他要是拿19,還剩23顆,E掐指一算,肯定拿19或20,
此時的情況是20,19,19,19,19(或20),大家都得死;
D要是拿20,還剩22顆,E掐指一算,要麼拿19,要麼拿20,
此時的情況是20,19,19,20,19(或20),大家都得死;
而D不可能拿21或者18犧牲小我成全大我,同理上述情況中,E也不可能拿18或者21。
C想,看來不能拿19,於是C拿了20,此時剩下41顆綠豆,
D掐指一算,前面三人極端情況就是兩個20,一個19,自己特么又得死啊,於是又拉上了E墊背。
E:(╯‵□′)╯︵┻━┻老子招誰惹誰了。
(可能大家會想D為嘛不拿20?D拿20,E拿21,D就不會死了,但是E不是傻子,不會拿21犧牲小我成全大我,如果D拿20,E算了下前面四個人的平均數,肯定會拿19或者20。)
此時的情況是20,19,20,19(或20),19(或20),大家都得死。
3)再假設B拿21,結果一:20,21,20,20(或21,事實上D足夠聰明就不會拿21),19(或18):B得死;
結果二:20,21,21(事實上C足夠聰明就不會拿21),20(或21,事實上D足夠聰明就不會拿21),18(或17):B得死。可想而知,只要B足夠聰明,都會避免在A拿20的情況下,自己拿21(這個思路很重要)。
綜上所述,當A拿20,BCDE身為聰明人,只能是在19-20之間拿,最後的結果註定是同歸於盡。


二、用「一」中的思路去推導A拿【1,19】的情況,得出的結論也是相同的,因為最後E有機會拿到和前面的幾個人同樣數量的綠豆(100÷5=20),就一定不會去選擇拿明顯最小或者明顯最大的數量(題目有說明可以不拿光)。
但這部分恰恰是我和大多數人的分歧所在,所以有理由展開說明一下。


假設A拿19顆,B會拿【18,20】,
1)假設B拿20,則C肯定拿19,D會拿19或20(事實上D足夠聰明就不會拿20),剩餘【22,23】,此時注意了,E是聰明人,並且這次和「一」中不同,剩餘綠豆數量足夠多,E有了選擇的餘地,他也會和D一樣,拿19或20(事實上不會拿20),此時綠豆有剩餘。
這種情況下,大家都得死。
2)假設B拿【18,19】,完全可以根據「一」中的推導過程得出「大家都得死」的結論。
同理,假設A拿【1,18】,也是一樣的結果。
所以目前A可以選擇的區間是【1,20】。


三、分析A拿21顆以上的情況,就要用到最開始講的,逐漸減少博弈參與者的思路,簡單來說就是先放棄E((╯‵□′)╯︵┻━┻)。
由於此題必定死人,而且拿的最少的那個必須死,所以前面的人如果多拿一些,E肯定就是拿的最少的那個。
100÷4=25,。
所以接下來考慮A拿【21,25】區間數的情況。
假設A拿25,剩餘75顆綠豆,75÷4=18餘3,B會怎麼拿?B會拿【19,24】,因為此時就是上面說的非正常情況下,
1)假設B拿19,剩餘56顆(註:下面再次出現56顆的情況),56÷3=18餘2,C會拿【19,21】,原因很簡單,拿19,DE一定有人比自己小,拿21,AB平均是22,一定有人比自己大,
假設C拿19,剩餘37顆,37÷2=18餘1,同理D會拿【19,20】,原因同C,此時E只可能拿到【1,18】,必為最小,
此時的情況是25,19,【19,21】,【19,20】,【1,18】,AE死。
2)同理,不管B拿【20,24】區間內任意數,C都有辦法左右後面的局勢,而D也都能化解自己的危險,最後的結果必然是AE死。相信大家能夠推導出來。

假設A拿24,剩餘76顆,76÷4=19,B會拿【20,23】,
1)假設B拿20顆,剩餘56顆,你會發現此時和上面的情形一模一樣,B再次左右後三人,C再次左右後兩人,結果自然也是AE死。
接下來的論證和上面一樣,不再贅述。
據此,只要A足夠聰明,他就一定不會讓這樣的情況發生,即自己死的情況下竟然特么有人活下來!(ー`′ー)憑什麼?
所以排除A拿【21,25】區間內的數。


四、接下來只要按照「三」中的思路,依次減少博弈參與者的數量。
100÷3=33餘1。
考慮A拿【26,34】之間的情況,
假設A拿34,剩餘66顆,66÷4=16餘2,B會拿【17,33】,原因同上。
1)假設B拿17,剩餘49顆,49÷3=16餘1,C會拿【17,25】,原因同上。
假設C拿17,剩餘32顆,32÷2=16,D會拿【17,22】,原因同上,此時E只可能拿到【1,15】,必為最小,
此時的情況不言而喻,AE死。
2)同理,不管B拿【18,33】區間內任意數,結果都是AE死。
假設A拿33,剩餘67顆,67÷4=16餘3,同樣適用上面的原理,B、C等完全可以左右局勢,而A怎樣都得死,並且有人活下來。
到此為止,其實就是不斷地重複「三」中的過程,排除區間【26,34】。

五、100÷2=50,考慮A拿【35,50】之間的情況,
假設A拿50,剩餘50顆,50÷4=12餘2,B會拿【13,47】,這裡考慮隱含條件,B至少會留下3顆綠豆(不考慮的話,B【13,,50】)。
假設B47,剩餘3顆,ACDE死。
假設B46,剩餘4顆,ADE死。
假設B45,剩餘5顆,C【2,3】,C2,則AE死,C3則ADE死。
。。。。。。
假設B13,剩餘37顆,37÷3=12餘1,C繼續左右局勢,結果不言而喻。
所以A同樣不會選擇【35,50】的區間。

六、繼續減少博弈參與者(其實這個說法並不準確,但是思路我已經在上面陳述清楚了),100÷1=100,考慮到隱含條件,A至少會留下4顆綠豆,所以考慮A拿區間【51,96】之間的情況,
假設A拿96顆,剩餘4顆,4÷4=1,B會拿幾顆?B只能拿1顆,因為隱含條件,同理CDE都拿了1顆,大家同歸於盡!
所以96可取!


假設A拿95顆,剩餘5顆,5÷4=1餘1,B此時必定拿2顆,ACDE死。
假設A拿94顆,剩餘6顆,B【2,3】,假設B2,還剩4顆,C必定拿2顆,此時94,2,2,1,1,全死;假設B3,ACDE死。
繼續分析,B依舊可以左右局勢。
所以A同樣不會選擇【51,95】的區間。

至此六步可以得出,A只要選擇在區間【1,20】之間拿,或者拿96顆,都可以達到ABCDE五兄弟「不求同年同月同日生,但求同年同月同日死」的美好願望,而且成功率(幾率)都是百分之百,故非只有一種最優決策,
另外當A取【21,34】的時候,存活的人將最多。

最後表達一下對A兄的同情:一個如此聰明之人,在一場博弈中,最優策略竟然都是「死」,還有比這更悲催的人生嗎?上輩子必定是折翼的天使!(* ̄(エ) ̄)

----------------------------------------------------------------分割線------------------------------------------------------------------
無意中看到@haoshu zhao 大牛的答案,已經羅列出了所有博弈結果的可能性,算是和我的答案互為佐證。
遺憾自己沒有學好編程,只能通過繁瑣的推導得出結論。

最後,私以為原題這樣的博弈意義不大,一:最優策略是同歸於盡,記得高曉松在《奇葩說》節目里經常掛在嘴邊的一句話就是「一個成年人,做一件事情,最高期望值是0,這叫什麼事」,大概就是這味道;二:首先博弈各方有決策的先後順序,並且一旦做了決策就無法改變了,其次後者在信息上具有優勢,但對於前者的影響和反饋卻很小,這樣就使得後者在決策上被動選擇迫害前者,而反過來也會使得前者做出最極端的決策去改變優劣勢情況,這無疑將博弈結果推向了極端惡化。所以我認為肯定是牢獄長故意整五個囚犯的;-)

沒想到會在這個問題上交出處女答,感謝大家看完,如果我的思路有不妥的地方,或者整篇回答有漏洞,歡迎知友們能夠給予意見和幫助,謝謝!


先放結論:所有人都得死。

根據題目條件,先保命,然後多殺人。換言之,要是保不了命,那麼多殺人便是唯一追求。

為了方便起見,叫他們abcde。
a是沒有可能活下來的。他不管拿多少個,b拿的數量不會和a相差超過1(|b-a|≤1),否則c就拿ab的平均值((a+b)/2個),然後ab就是兩個極值,直接gg。
當然,後面的人為了保命,拿的數量肯定要逼近ab平均數的。要是平均數不是整數,向上或者向下取整,對a來說是一樣,他都得死。

因此,得出一個結論,a是必死的

那他唯一的目標便是:你們這些小表砸陪老子一起死。

a深吸一口煙,吐出個煙圈,拿出了96個。

bcde面面相覷,絕望的味道瀰漫著這個房間。

音響里傳出聲音,敵軍還有三十秒到達戰場,碾碎他們。


--------------------------------------------------------------------------------------------------------------------------------------------
1.根據題目意思,是每個人都得可以拿豆子,因此不存在第二個人拿4個的情況。即使真的可以允許,相應的,第一個人直接100個拿完就行了

2.拜託各位別說個方案說一半就不說了,我是處女座

3.所有說這個方法不是最好的,可以評論區,你扮演ace,我演bd,看看結果如何。

4.可以和 @曾加大神一起上今日熱榜還是非常excited!感謝他的答案,其實這個算是他答案的一個簡化版,詳細證明大家去看他的就好啦

5.再次謝謝大家捧場和支持~


100顆豆子五人抓取,平均數為20顆,也就是誰有最大的幾率拿到20顆,誰的存活幾率最大。

4號存活的可能性最大。

如果四號抓取時,豆子數多於40粒,那麼四號會抓取20粒,保證不死。如果豆子數少於40粒,那麼他只要抓取多於一半少於20粒的豆子就可以保證不死。在這兩種情況下,5號很容易死。

如果四號抓取時,豆子數正好40粒,那麼四號的最優策略是抓取20粒。如果1、2、3號都拿了20粒,那沒辦,4號怎麼拿都是死;如果1、2、3號有一人拿的不是20粒,四號拿20粒可保證存活。

如果四號抓取時,沒有豆子可拿了,那就沒轍了。但是這種情況是1、2、3號有一人最少拿了 34粒,顯然這是作死行為,因為他們都很聰明,所以沒人這樣做。


如果依次取,那貌似只要取之前平均和之後平均之間的某數就行。所以一個均衡解是都取20粒。

注意到題目有額外條件藏在提示里:提示4解釋了極值可重,而另一個提示解釋了100不必取完

第一個人如果多於20,那麼2-4會活,1,5會死,因為2-4隻要取20就可以保證自己活。
所以任何人最多取20。
後人的最優策略永遠是取前人的平均。這會導致大家取相等的豆。因為如果不取前人平均就會變成極值


「2、他們的原則是先求保命,再去多殺人」這一條原則可以理解為每個人都不會主動選擇最大或最小的數,以及在明知道必死的情況下不會主動做出犧牲吧?那僅這一條就註定了是團滅啊……

A選什麼都是死,但由於上述原則,他不會選擇大於總數平均數也就是20以上的數量。
那接下來B的數量也只會等於A的數量或者+1/-1,因為在這個條件下他選什麼也都是死,但只要差數大於1,C、D、E就可以活,但這違背了第2點原則。
接下來C、D、E同理。

團滅,妥妥的~


這個問題,我曾經跟舍友討論過半個晚上,得出的結論是五個人會同歸於盡,一定要評出規則最有利於誰,那麼我會選最後一個人。

每個人的最優解應該的拿取前面人拿去的豆子的平均數,這樣自己有可能不是最多或者最少的(只能有這樣美好的期望)

所以最後一個人只要拿了平均數,那麼要麼自己活著有人死了,要麼大家同歸於盡。當然這只是他的一廂情願,5個絕頂聰明的人一定會選出5個20,要死一起死,我死了憑啥讓你活著。


我也採用編程遍歷的辦法。

我不是專業干編程的,編程的風格很糟糕,大家將就一下:


//100個豆,5個人依次取,最少和最多豆的人死掉。後面的人可以知道剩下幾個豆

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
typedef struct{
int dou[5];
int left[5];
bool live[5];
}QUDOU;
const char LIVE=1;
const char DEAD=2;
const char UNSURE=3;
const char EMPTY=0;

char winnermap[5][101][101];//剩了幾個豆,摸了幾個豆

//QUDOU plan[100000];//不夠大,囧

void init();
int creat();//創建所有取豆方案
void whowin(QUDOU data);//判斷誰活了
void findanswer();

int _tmain(int argc, _TCHAR* argv[])
{
int findend;
init();
findend=creat();
findanswer();
system("PAUSE");
return 0;
}
QUDOU emptyqd()
{ QUDOU qudou0;
int ki;
for(ki=0;ki&<5;ki++) { qudou0.dou[ki]=0; qudou0.left[ki]=100; qudou0.live[ki]=true; } return qudou0; } void init() { int ki,pi,qi; for(ki=0;ki&<5;ki++) { for(pi=0;pi&<101;pi++) { for(qi=0;qi&<101;qi++) { winnermap[ki][pi][qi]=EMPTY; } } } } int creat()//創建所有取豆方案 { int total=0; int a,b,c,d,e; QUDOU qd; qd=emptyqd(); qd.left[0]=100; for(a=0;a&<=qd.left[0];a++) { qd.dou[0]=a; qd.left[1]=qd.left[0]-a; for(b=0;b&<=qd.left[1];b++) { qd.dou[1]=b; qd.left[2]=qd.left[1]-b; for(c=0;c&<=qd.left[2];c++) { qd.dou[2]=c; qd.left[3]=qd.left[2]-c; for(d=0;d&<=qd.left[3];d++) { qd.dou[3]=d; qd.left[4]=qd.left[3]-d; for(e=0;e&<=qd.left[4];e++) { qd.dou[4]=e; whowin(qd); total++; } } } printf("%d ",total); } } return total; } void show(QUDOU data) { QUDOU sd; sd=data; int ki; for(ki=0;ki&<5;ki++) { printf("%-4d",sd.dou[ki]); } for(ki=0;ki&<5;ki++) { if(sd.live[ki]) { printf("T "); } else { printf("F "); } } printf(" "); } void fillmap(QUDOU data) { QUDOU fd; fd=data; char* pm; char temp; int ki; for(ki=0;ki&<5;ki++) { if(fd.live[ki]) { temp=LIVE; } else { temp=DEAD; } pm=(winnermap[ki][fd.left[ki]][fd.dou[ki]]); if(*pm==EMPTY) { *pm=temp; } else { if(*pm==temp) { } else { *pm=UNSURE; } } } //printf("%d ",*pm); } void whowin(QUDOU data)//判斷誰活了 { QUDOU wd; wd=data; int wdmax=0; int wdmin=100; int ki; for(ki=0;ki&<5;ki++) { if(wd.dou[ki]&>wdmax)
{
wdmax=wd.dou[ki];
}
if(wd.dou[ki]&

我沒來得及考慮,如何能多殺人。我著重考慮,如何能讓自己活下來。

結果如下。第一列是第幾個人(1~5),第二列是這個人取的時候剩下幾個豆,第三列是這個人取幾個豆。

  • 2 1 1
    2 2 1
    2 2 2
    2 3 1
    2 3 2
    2 3 3
    2 4 2
    2 4 3
    2 4 4
    2 5 2
    2 5 3
    2 5 4
    2 5 5
    2 6 2
    2 6 3
    2 6 4
    2 6 5
    2 6 6
    2 7 2
    2 7 3
    2 7 4
    2 7 5
    2 7 6
    2 7 7
    2 8 3
    2 8 4
    2 8 5
    2 8 6
    2 8 7
    2 8 8
    2 9 3
    2 9 4
    2 9 5
    2 9 6
    2 9 7
    2 9 8
    2 9 9
    2 10 3
    2 10 4
    2 10 5
    2 10 6
    2 10 7
    2 10 8
    2 10 9
    2 10 10
    2 11 3
    2 11 4
    2 11 5
    2 11 6
    2 11 7
    2 11 8
    2 11 9
    2 11 10
    2 11 11
    2 12 4
    2 12 5
    2 12 6
    2 12 7
    2 12 8
    2 12 9
    2 12 10
    2 12 11
    2 12 12
    2 13 4
    2 13 5
    2 13 6
    2 13 7
    2 13 8
    2 13 9
    2 13 10
    2 13 11
    2 13 12
    2 13 13
    2 14 4
    2 14 5
    2 14 6
    2 14 7
    2 14 8
    2 14 9
    2 14 10
    2 14 11
    2 14 12
    2 14 13
    2 14 14
    2 15 4
    2 15 5
    2 15 6
    2 15 7
    2 15 8
    2 15 9
    2 15 10
    2 15 11
    2 15 12
    2 15 13
    2 15 14
    2 15 15
    2 16 5
    2 16 6
    2 16 7
    2 16 8
    2 16 9
    2 16 10
    2 16 11
    2 16 12
    2 16 13
    2 16 14
    2 16 15
    2 16 16
    2 17 5
    2 17 6
    2 17 7
    2 17 8
    2 17 9
    2 17 10
    2 17 11
    2 17 12
    2 17 13
    2 17 14
    2 17 15
    2 17 16
    2 17 17
    2 18 5
    2 18 6
    2 18 7
    2 18 8
    2 18 9
    2 18 10
    2 18 11
    2 18 12
    2 18 13
    2 18 14
    2 18 15
    2 18 16
    2 18 17
    2 18 18
    2 19 5
    2 19 6
    2 19 7
    2 19 8
    2 19 9
    2 19 10
    2 19 11
    2 19 12
    2 19 13
    2 19 14
    2 19 15
    2 19 16
    2 19 17
    2 19 18
    2 19 19
    2 20 6
    2 20 7
    2 20 8
    2 20 9
    2 20 10
    2 20 11
    2 20 12
    2 20 13
    2 20 14
    2 20 15
    2 20 16
    2 20 17
    2 20 18
    2 20 19
    2 20 20
    2 21 6
    2 21 7
    2 21 8
    2 21 9
    2 21 10
    2 21 11
    2 21 12
    2 21 13
    2 21 14
    2 21 15
    2 21 16
    2 21 17
    2 21 18
    2 21 19
    2 21 20
    2 21 21
    2 22 6
    2 22 7
    2 22 8
    2 22 9
    2 22 10
    2 22 11
    2 22 12
    2 22 13
    2 22 14
    2 22 15
    2 22 16
    2 22 17
    2 22 18
    2 22 19
    2 22 20
    2 22 21
    2 22 22
    2 23 6
    2 23 7
    2 23 8
    2 23 9
    2 23 10
    2 23 11
    2 23 12
    2 23 13
    2 23 14
    2 23 15
    2 23 16
    2 23 17
    2 23 18
    2 23 19
    2 23 20
    2 23 21
    2 23 22
    2 23 23
    2 24 7
    2 24 8
    2 24 9
    2 24 10
    2 24 11
    2 24 12
    2 24 13
    2 24 14
    2 24 15
    2 24 16
    2 24 17
    2 24 18
    2 24 19
    2 24 20
    2 24 21
    2 24 22
    2 24 23
    2 24 24
    2 25 7
    2 25 8
    2 25 9
    2 25 10
    2 25 11
    2 25 12
    2 25 13
    2 25 14
    2 25 15
    2 25 16
    2 25 17
    2 25 18
    2 25 19
    2 25 20
    2 25 21
    2 25 22
    2 25 23
    2 25 24
    2 25 25
    2 26 7
    2 26 8
    2 26 9
    2 26 10
    2 26 11
    2 26 12
    2 26 13
    2 26 14
    2 26 15
    2 26 16
    2 26 17
    2 26 18
    2 26 19
    2 26 20
    2 26 21
    2 26 22
    2 26 23
    2 26 24
    2 26 25
    2 26 26
    2 27 7
    2 27 8
    2 27 9
    2 27 10
    2 27 11
    2 27 12
    2 27 13
    2 27 14
    2 27 15
    2 27 16
    2 27 17
    2 27 18
    2 27 19
    2 27 20
    2 27 21
    2 27 22
    2 27 23
    2 27 24
    2 27 25
    2 27 26
    2 27 27
    2 28 8
    2 28 9
    2 28 10
    2 28 11
    2 28 12
    2 28 13
    2 28 14
    2 28 15
    2 28 16
    2 28 17
    2 28 18
    2 28 19
    2 28 20
    2 28 21
    2 28 22
    2 28 23
    2 28 24
    2 28 25
    2 28 26
    2 28 27
    2 28 28
    2 29 8
    2 29 9
    2 29 10
    2 29 11
    2 29 12
    2 29 13
    2 29 14
    2 29 15
    2 29 16
    2 29 17
    2 29 18
    2 29 19
    2 29 20
    2 29 21
    2 29 22
    2 29 23
    2 29 24
    2 29 25
    2 29 26
    2 29 27
    2 29 28
    2 29 29
    2 30 8
    2 30 9
    2 30 10
    2 30 11
    2 30 12
    2 30 13
    2 30 14
    2 30 15
    2 30 16
    2 30 17
    2 30 18
    2 30 19
    2 30 20
    2 30 21
    2 30 22
    2 30 23
    2 30 24
    2 30 25
    2 30 26
    2 30 27
    2 30 28
    2 30 29
    2 30 30
    2 31 8
    2 31 9
    2 31 10
    2 31 11
    2 31 12
    2 31 13
    2 31 14
    2 31 15
    2 31 16
    2 31 17
    2 31 18
    2 31 19
    2 31 20
    2 31 21
    2 31 22
    2 31 23
    2 31 24
    2 31 25
    2 31 26
    2 31 27
    2 31 28
    2 31 29
    2 31 30
    2 31 31
    2 32 9
    2 32 10
    2 32 11
    2 32 12
    2 32 13
    2 32 14
    2 32 15
    2 32 16
    2 32 17
    2 32 18
    2 32 19
    2 32 20
    2 32 21
    2 32 22
    2 32 23
    2 32 24
    2 32 25
    2 32 26
    2 32 27
    2 32 28
    2 32 29
    2 32 30
    2 32 31
    2 32 32
    2 33 9
    2 33 10
    2 33 11
    2 33 12
    2 33 13
    2 33 14
    2 33 15
    2 33 16
    2 33 17
    2 33 18
    2 33 19
    2 33 20
    2 33 21
    2 33 22
    2 33 23
    2 33 24
    2 33 25
    2 33 26
    2 33 27
    2 33 28
    2 33 29
    2 33 30
    2 33 31
    2 33 32
    2 33 33
    2 34 9
    2 34 10
    2 34 11
    2 34 12
    2 34 13
    2 34 14
    2 34 15
    2 34 16
    2 34 17
    2 34 18
    2 34 19
    2 34 20
    2 34 21
    2 34 22
    2 34 23
    2 34 24
    2 34 25
    2 34 26
    2 34 27
    2 34 28
    2 34 29
    2 34 30
    2 34 31
    2 34 32
    2 34 33
    2 34 34
    2 35 9
    2 35 10
    2 35 11
    2 35 12
    2 35 13
    2 35 14
    2 35 15
    2 35 16
    2 35 17
    2 35 18
    2 35 19
    2 35 20
    2 35 21
    2 35 22
    2 35 23
    2 35 24
    2 35 25
    2 35 26
    2 35 27
    2 35 28
    2 35 29
    2 35 30
    2 35 31
    2 35 32
    2 35 33
    2 35 34
    2 35 35
    2 36 10
    2 36 11
    2 36 12
    2 36 13
    2 36 14
    2 36 15
    2 36 16
    2 36 17
    2 36 18
    2 36 19
    2 36 20
    2 36 21
    2 36 22
    2 36 23
    2 36 24
    2 36 25
    2 36 26
    2 36 27
    2 36 28
    2 36 29
    2 36 30
    2 36 31
    2 36 32
    2 36 33
    2 36 34
    2 36 35
    2 36 36
    2 37 10
    2 37 11
    2 37 12
    2 37 13
    2 37 14
    2 37 15
    2 37 16
    2 37 17
    2 37 18
    2 37 19
    2 37 20
    2 37 21
    2 37 22
    2 37 23
    2 37 24
    2 37 25
    2 37 26
    2 37 27
    2 37 28
    2 37 29
    2 37 30
    2 37 31
    2 37 32
    2 37 33
    2 37 34
    2 37 35
    2 37 36
    2 37 37
    2 38 10
    2 38 11
    2 38 12
    2 38 13
    2 38 14
    2 38 15
    2 38 16
    2 38 17
    2 38 18
    2 38 19
    2 38 20
    2 38 21
    2 38 22
    2 38 23
    2 38 24
    2 38 25
    2 38 26
    2 38 27
    2 38 28
    2 38 29
    2 38 30
    2 38 31
    2 38 32
    2 38 33
    2 38 34
    2 38 35
    2 38 36
    2 38 37
    2 38 38
    2 39 10
    2 39 11
    2 39 12
    2 39 13
    2 39 14
    2 39 15
    2 39 16
    2 39 17
    2 39 18
    2 39 19
    2 39 20
    2 39 21
    2 39 22
    2 39 23
    2 39 24
    2 39 25
    2 39 26
    2 39 27
    2 39 28
    2 39 29
    2 39 30
    2 39 31
    2 39 32
    2 39 33
    2 39 34
    2 39 35
    2 39 36
    2 39 37
    2 39 38
    2 39 39
    2 40 11
    2 40 12
    2 40 13
    2 40 14
    2 40 15
    2 40 16
    2 40 17
    2 40 18
    2 40 19
    2 40 20
    2 40 21
    2 40 22
    2 40 23
    2 40 24
    2 40 25
    2 40 26
    2 40 27
    2 40 28
    2 40 29
    2 40 30
    2 40 31
    2 40 32
    2 40 33
    2 40 34
    2 40 35
    2 40 36
    2 40 37
    2 40 38
    2 40 39
    2 40 40
    2 41 11
    2 41 12
    2 41 13
    2 41 14
    2 41 15
    2 41 16
    2 41 17
    2 41 18
    2 41 19
    2 41 20
    2 41 21
    2 41 22
    2 41 23
    2 41 24
    2 41 25
    2 41 26
    2 41 27
    2 41 28
    2 41 29
    2 41 30
    2 41 31
    2 41 32
    2 41 33
    2 41 34
    2 41 35
    2 41 36
    2 41 37
    2 41 38
    2 41 39
    2 41 40
    2 41 41
    2 42 11
    2 42 12
    2 42 13
    2 42 14
    2 42 15
    2 42 16
    2 42 17
    2 42 18
    2 42 19
    2 42 20
    2 42 21
    2 42 22
    2 42 23
    2 42 24
    2 42 25
    2 42 26
    2 42 27
    2 42 28
    2 42 29
    2 42 30
    2 42 31
    2 42 32
    2 42 33
    2 42 34
    2 42 35
    2 42 36
    2 42 37
    2 42 38
    2 42 39
    2 42 40
    2 42 41
    2 42 42
    2 43 11
    2 43 12
    2 43 13
    2 43 14
    2 43 15
    2 43 16
    2 43 17
    2 43 18
    2 43 19
    2 43 20
    2 43 21
    2 43 22
    2 43 23
    2 43 24
    2 43 25
    2 43 26
    2 43 27
    2 43 28
    2 43 29
    2 43 30
    2 43 31
    2 43 32
    2 43 33
    2 43 34
    2 43 35
    2 43 36
    2 43 37
    2 43 38
    2 43 39
    2 43 40
    2 43 41
    2 43 42
    2 43 43
    2 44 12
    2 44 13
    2 44 14
    2 44 15
    2 44 16
    2 44 17
    2 44 18
    2 44 19
    2 44 20
    2 44 21
    2 44 22
    2 44 23
    2 44 24
    2 44 25
    2 44 26
    2 44 27
    2 44 28
    2 44 29
    2 44 30
    2 44 31
    2 44 32
    2 44 33
    2 44 34
    2 44 35
    2 44 36
    2 44 37
    2 44 38
    2 44 39
    2 44 40
    2 44 41
    2 44 42
    2 44 43
    2 44 44
    2 45 12
    2 45 13
    2 45 14
    2 45 15
    2 45 16
    2 45 17
    2 45 18
    2 45 19
    2 45 20
    2 45 21
    2 45 22
    2 45 23
    2 45 24
    2 45 25
    2 45 26
    2 45 27
    2 45 28
    2 45 29
    2 45 30
    2 45 31
    2 45 32
    2 45 33
    2 45 34
    2 45 35
    2 45 36
    2 45 37
    2 45 38
    2 45 39
    2 45 40
    2 45 41
    2 45 42
    2 45 43
    2 45 44
    2 45 45
    2 46 12
    2 46 13
    2 46 14
    2 46 15
    2 46 16
    2 46 17
    2 46 18
    2 46 19
    2 46 20
    2 46 21
    2 46 22
    2 46 23
    2 46 24
    2 46 25
    2 46 26
    2 46 27
    2 46 28
    2 46 29
    2 46 30
    2 46 31
    2 46 32
    2 46 33
    2 46 34
    2 46 35
    2 46 36
    2 46 37
    2 46 38
    2 46 39
    2 46 40
    2 46 41
    2 46 42
    2 46 43
    2 46 44
    2 46 45
    2 46 46
    2 47 12
    2 47 13
    2 47 14
    2 47 15
    2 47 16
    2 47 17
    2 47 18
    2 47 19
    2 47 20
    2 47 21
    2 47 22
    2 47 23
    2 47 24
    2 47 25
    2 47 26
    2 47 27
    2 47 28
    2 47 29
    2 47 30
    2 47 31
    2 47 32
    2 47 33
    2 47 34
    2 47 35
    2 47 36
    2 47 37
    2 47 38
    2 47 39
    2 47 40
    2 47 41
    2 47 42
    2 47 43
    2 47 44
    2 47 45
    2 47 46
    2 47 47
    2 48 13
    2 48 14
    2 48 15
    2 48 16
    2 48 17
    2 48 18
    2 48 19
    2 48 20
    2 48 21
    2 48 22
    2 48 23
    2 48 24
    2 48 25
    2 48 26
    2 48 27
    2 48 28
    2 48 29
    2 48 30
    2 48 31
    2 48 32
    2 48 33
    2 48 34
    2 48 35
    2 48 36
    2 48 37
    2 48 38
    2 48 39
    2 48 40
    2 48 41
    2 48 42
    2 48 43
    2 48 44
    2 48 45
    2 48 46
    2 48 47
    2 48 48
    2 49 13
    2 49 14
    2 49 15
    2 49 16
    2 49 17
    2 49 18
    2 49 19
    2 49 20
    2 49 21
    2 49 22
    2 49 23
    2 49 24
    2 49 25
    2 49 26
    2 49 27
    2 49 28
    2 49 29
    2 49 30
    2 49 31
    2 49 32
    2 49 33
    2 49 34
    2 49 35
    2 49 36
    2 49 37
    2 49 38
    2 49 39
    2 49 40
    2 49 41
    2 49 42
    2 49 43
    2 49 44
    2 49 45
    2 49 46
    2 49 47
    2 49 48
    2 49 49
    2 50 13
    2 50 14
    2 50 15
    2 50 16
    2 50 17
    2 50 18
    2 50 19
    2 50 20
    2 50 21
    2 50 22
    2 50 23
    2 50 24
    2 50 25
    2 50 26
    2 50 27
    2 50 28
    2 50 29
    2 50 30
    2 50 31
    2 50 32
    2 50 33
    2 50 34
    2 50 35
    2 50 36
    2 50 37
    2 50 38
    2 50 39
    2 50 40
    2 50 41
    2 50 42
    2 50 43
    2 50 44
    2 50 45
    2 50 46
    2 50 47
    2 50 48
    2 50 49
    2 51 13
    2 51 14
    2 51 15
    2 51 16
    2 51 17
    2 51 18
    2 51 19
    2 51 20
    2 51 21
    2 51 22
    2 51 23
    2 51 24
    2 51 25
    2 51 26
    2 51 27
    2 51 28
    2 51 29
    2 51 30
    2 51 31
    2 51 32
    2 51 33
    2 51 34
    2 51 35
    2 51 36
    2 51 37
    2 51 38
    2 51 39
    2 51 40
    2 51 41
    2 51 42
    2 51 43
    2 51 44
    2 51 45
    2 51 46
    2 51 47
    2 51 48
    2 52 14
    2 52 15
    2 52 16
    2 52 17
    2 52 18
    2 52 19
    2 52 20
    2 52 21
    2 52 22
    2 52 23
    2 52 24
    2 52 25
    2 52 26
    2 52 27
    2 52 28
    2 52 29
    2 52 30
    2 52 31
    2 52 32
    2 52 33
    2 52 34
    2 52 35
    2 52 36
    2 52 37
    2 52 38
    2 52 39
    2 52 40
    2 52 41
    2 52 42
    2 52 43
    2 52 44
    2 52 45
    2 52 46
    2 52 47
    2 53 14
    2 53 15
    2 53 16
    2 53 17
    2 53 18
    2 53 19
    2 53 20
    2 53 21
    2 53 22
    2 53 23
    2 53 24
    2 53 25
    2 53 26
    2 53 27
    2 53 28
    2 53 29
    2 53 30
    2 53 31
    2 53 32
    2 53 33
    2 53 34
    2 53 35
    2 53 36
    2 53 37
    2 53 38
    2 53 39
    2 53 40
    2 53 41
    2 53 42
    2 53 43
    2 53 44
    2 53 45
    2 53 46
    2 54 14
    2 54 15
    2 54 16
    2 54 17
    2 54 18
    2 54 19
    2 54 20
    2 54 21
    2 54 22
    2 54 23
    2 54 24
    2 54 25
    2 54 26
    2 54 27
    2 54 28
    2 54 29
    2 54 30
    2 54 31
    2 54 32
    2 54 33
    2 54 34
    2 54 35
    2 54 36
    2 54 37
    2 54 38
    2 54 39
    2 54 40
    2 54 41
    2 54 42
    2 54 43
    2 54 44
    2 54 45
    2 55 14
    2 55 15
    2 55 16
    2 55 17
    2 55 18
    2 55 19
    2 55 20
    2 55 21
    2 55 22
    2 55 23
    2 55 24
    2 55 25
    2 55 26
    2 55 27
    2 55 28
    2 55 29
    2 55 30
    2 55 31
    2 55 32
    2 55 33
    2 55 34
    2 55 35
    2 55 36
    2 55 37
    2 55 38
    2 55 39
    2 55 40
    2 55 41
    2 55 42
    2 55 43
    2 55 44
    2 56 15
    2 56 16
    2 56 17
    2 56 18
    2 56 19
    2 56 20
    2 56 21
    2 56 22
    2 56 23
    2 56 24
    2 56 25
    2 56 26
    2 56 27
    2 56 28
    2 56 29
    2 56 30
    2 56 31
    2 56 32
    2 56 33
    2 56 34
    2 56 35
    2 56 36
    2 56 37
    2 56 38
    2 56 39
    2 56 40
    2 56 41
    2 56 42
    2 56 43
    2 57 15
    2 57 16
    2 57 17
    2 57 18
    2 57 19
    2 57 20
    2 57 21
    2 57 22
    2 57 23
    2 57 24
    2 57 25
    2 57 26
    2 57 27
    2 57 28
    2 57 29
    2 57 30
    2 57 31
    2 57 32
    2 57 33
    2 57 34
    2 57 35
    2 57 36
    2 57 37
    2 57 38
    2 57 39
    2 57 40
    2 57 41
    2 57 42
    2 58 15
    2 58 16
    2 58 17
    2 58 18
    2 58 19
    2 58 20
    2 58 21
    2 58 22
    2 58 23
    2 58 24
    2 58 25
    2 58 26
    2 58 27
    2 58 28
    2 58 29
    2 58 30
    2 58 31
    2 58 32
    2 58 33
    2 58 34
    2 58 35
    2 58 36
    2 58 37
    2 58 38
    2 58 39
    2 58 40
    2 58 41
    2 59 15
    2 59 16
    2 59 17
    2 59 18
    2 59 19
    2 59 20
    2 59 21
    2 59 22
    2 59 23
    2 59 24
    2 59 25
    2 59 26
    2 59 27
    2 59 28
    2 59 29
    2 59 30
    2 59 31
    2 59 32
    2 59 33
    2 59 34
    2 59 35
    2 59 36
    2 59 37
    2 59 38
    2 59 39
    2 59 40
    2 60 16
    2 60 17
    2 60 18
    2 60 19
    2 60 20
    2 60 21
    2 60 22
    2 60 23
    2 60 24
    2 60 25
    2 60 26
    2 60 27
    2 60 28
    2 60 29
    2 60 30
    2 60 31
    2 60 32
    2 60 33
    2 60 34
    2 60 35
    2 60 36
    2 60 37
    2 60 38
    2 60 39
    2 61 16
    2 61 17
    2 61 18
    2 61 19
    2 61 20
    2 61 21
    2 61 22
    2 61 23
    2 61 24
    2 61 25
    2 61 26
    2 61 27
    2 61 28
    2 61 29
    2 61 30
    2 61 31
    2 61 32
    2 61 33
    2 61 34
    2 61 35
    2 61 36
    2 61 37
    2 61 38
    2 62 16
    2 62 17
    2 62 18
    2 62 19
    2 62 20
    2 62 21
    2 62 22
    2 62 23
    2 62 24
    2 62 25
    2 62 26
    2 62 27
    2 62 28
    2 62 29
    2 62 30
    2 62 31
    2 62 32
    2 62 33
    2 62 34
    2 62 35
    2 62 36
    2 62 37
    2 63 16
    2 63 17
    2 63 18
    2 63 19
    2 63 20
    2 63 21
    2 63 22
    2 63 23
    2 63 24
    2 63 25
    2 63 26
    2 63 27
    2 63 28
    2 63 29
    2 63 30
    2 63 31
    2 63 32
    2 63 33
    2 63 34
    2 63 35
    2 63 36
    2 64 17
    2 64 18
    2 64 19
    2 64 20
    2 64 21
    2 64 22
    2 64 23
    2 64 24
    2 64 25
    2 64 26
    2 64 27
    2 64 28
    2 64 29
    2 64 30
    2 64 31
    2 64 32
    2 64 33
    2 64 34
    2 64 35
    2 65 17
    2 65 18
    2 65 19
    2 65 20
    2 65 21
    2 65 22
    2 65 23
    2 65 24
    2 65 25
    2 65 26
    2 65 27
    2 65 28
    2 65 29
    2 65 30
    2 65 31
    2 65 32
    2 65 33
    2 65 34
    2 66 17
    2 66 18
    2 66 19
    2 66 20
    2 66 21
    2 66 22
    2 66 23
    2 66 24
    2 66 25
    2 66 26
    2 66 27
    2 66 28
    2 66 29
    2 66 30
    2 66 31
    2 66 32
    2 66 33
    2 67 17
    2 67 18
    2 67 19
    2 67 20
    2 67 21
    2 67 22
    2 67 23
    2 67 24
    2 67 25
    2 67 26
    2 67 27
    2 67 28
    2 67 29
    2 67 30
    2 67 31
    2 67 32
    2 68 18
    2 68 19
    2 68 20
    2 68 21
    2 68 22
    2 68 23
    2 68 24
    2 68 25
    2 68 26
    2 68 27
    2 68 28
    2 68 29
    2 68 30
    2 68 31
    2 69 18
    2 69 19
    2 69 20
    2 69 21
    2 69 22
    2 69 23
    2 69 24
    2 69 25
    2 69 26
    2 69 27
    2 69 28
    2 69 29
    2 69 30
    2 70 18
    2 70 19
    2 70 20
    2 70 21
    2 70 22
    2 70 23
    2 70 24
    2 70 25
    2 70 26
    2 70 27
    2 70 28
    2 70 29
    2 71 18
    2 71 19
    2 71 20
    2 71 21
    2 71 22
    2 71 23
    2 71 24
    2 71 25
    2 71 26
    2 71 27
    2 71 28
    2 72 19
    2 72 20
    2 72 21
    2 72 22
    2 72 23
    2 72 24
    2 72 25
    2 72 26
    2 72 27
    2 73 19
    2 73 20
    2 73 21
    2 73 22
    2 73 23
    2 73 24
    2 73 25
    2 73 26
    2 74 19
    2 74 20
    2 74 21
    2 74 22
    2 74 23
    2 74 24
    2 74 25
    2 75 19
    2 75 20
    2 75 21
    2 75 22
    2 75 23
    2 75 24
    2 76 20
    2 76 21
    2 76 22
    2 76 23
    2 77 20
    2 77 21
    2 77 22
    2 78 20
    2 78 21
    2 79 20
    3 1 1
    3 2 1
    3 2 2
    3 3 2
    3 3 3
    3 4 2
    3 4 3
    3 4 4
    3 5 2
    3 5 3
    3 5 4
    3 5 5
    3 6 3
    3 6 4
    3 6 5
    3 6 6
    3 7 3
    3 7 4
    3 7 5
    3 7 6
    3 7 7
    3 8 3
    3 8 4
    3 8 5
    3 8 6
    3 8 7
    3 8 8
    3 9 4
    3 9 5
    3 9 6
    3 9 7
    3 9 8
    3 9 9
    3 10 4
    3 10 5
    3 10 6
    3 10 7
    3 10 8
    3 10 9
    3 10 10
    3 11 4
    3 11 5
    3 11 6
    3 11 7
    3 11 8
    3 11 9
    3 11 10
    3 11 11
    3 12 5
    3 12 6
    3 12 7
    3 12 8
    3 12 9
    3 12 10
    3 12 11
    3 12 12
    3 13 5
    3 13 6
    3 13 7
    3 13 8
    3 13 9
    3 13 10
    3 13 11
    3 13 12
    3 13 13
    3 14 5
    3 14 6
    3 14 7
    3 14 8
    3 14 9
    3 14 10
    3 14 11
    3 14 12
    3 14 13
    3 14 14
    3 15 6
    3 15 7
    3 15 8
    3 15 9
    3 15 10
    3 15 11
    3 15 12
    3 15 13
    3 15 14
    3 15 15
    3 16 6
    3 16 7
    3 16 8
    3 16 9
    3 16 10
    3 16 11
    3 16 12
    3 16 13
    3 16 14
    3 16 15
    3 16 16
    3 17 6
    3 17 7
    3 17 8
    3 17 9
    3 17 10
    3 17 11
    3 17 12
    3 17 13
    3 17 14
    3 17 15
    3 17 16
    3 17 17
    3 18 7
    3 18 8
    3 18 9
    3 18 10
    3 18 11
    3 18 12
    3 18 13
    3 18 14
    3 18 15
    3 18 16
    3 18 17
    3 18 18
    3 19 7
    3 19 8
    3 19 9
    3 19 10
    3 19 11
    3 19 12
    3 19 13
    3 19 14
    3 19 15
    3 19 16
    3 19 17
    3 19 18
    3 19 19
    3 20 7
    3 20 8
    3 20 9
    3 20 10
    3 20 11
    3 20 12
    3 20 13
    3 20 14
    3 20 15
    3 20 16
    3 20 17
    3 20 18
    3 20 19
    3 20 20
    3 21 8
    3 21 9
    3 21 10
    3 21 11
    3 21 12
    3 21 13
    3 21 14
    3 21 15
    3 21 16
    3 21 17
    3 21 18
    3 21 19
    3 21 20
    3 21 21
    3 22 8
    3 22 9
    3 22 10
    3 22 11
    3 22 12
    3 22 13
    3 22 14
    3 22 15
    3 22 16
    3 22 17
    3 22 18
    3 22 19
    3 22 20
    3 22 21
    3 22 22
    3 23 8
    3 23 9
    3 23 10
    3 23 11
    3 23 12
    3 23 13
    3 23 14
    3 23 15
    3 23 16
    3 23 17
    3 23 18
    3 23 19
    3 23 20
    3 23 21
    3 23 22
    3 23 23
    3 24 9
    3 24 10
    3 24 11
    3 24 12
    3 24 13
    3 24 14
    3 24 15
    3 24 16
    3 24 17
    3 24 18
    3 24 19
    3 24 20
    3 24 21
    3 24 22
    3 24 23
    3 24 24
    3 25 9
    3 25 10
    3 25 11
    3 25 12
    3 25 13
    3 25 14
    3 25 15
    3 25 16
    3 25 17
    3 25 18
    3 25 19
    3 25 20
    3 25 21
    3 25 22
    3 25 23
    3 25 24
    3 25 25
    3 26 9
    3 26 10
    3 26 11
    3 26 12
    3 26 13
    3 26 14
    3 26 15
    3 26 16
    3 26 17
    3 26 18
    3 26 19
    3 26 20
    3 26 21
    3 26 22
    3 26 23
    3 26 24
    3 26 25
    3 26 26
    3 27 10
    3 27 11
    3 27 12
    3 27 13
    3 27 14
    3 27 15
    3 27 16
    3 27 17
    3 27 18
    3 27 19
    3 27 20
    3 27 21
    3 27 22
    3 27 23
    3 27 24
    3 27 25
    3 27 26
    3 27 27
    3 28 10
    3 28 11
    3 28 12
    3 28 13
    3 28 14
    3 28 15
    3 28 16
    3 28 17
    3 28 18
    3 28 19
    3 28 20
    3 28 21
    3 28 22
    3 28 23
    3 28 24
    3 28 25
    3 28 26
    3 28 27
    3 28 28
    3 29 10
    3 29 11
    3 29 12
    3 29 13
    3 29 14
    3 29 15
    3 29 16
    3 29 17
    3 29 18
    3 29 19
    3 29 20
    3 29 21
    3 29 22
    3 29 23
    3 29 24
    3 29 25
    3 29 26
    3 29 27
    3 29 28
    3 29 29
    3 30 11
    3 30 12
    3 30 13
    3 30 14
    3 30 15
    3 30 16
    3 30 17
    3 30 18
    3 30 19
    3 30 20
    3 30 21
    3 30 22
    3 30 23
    3 30 24
    3 30 25
    3 30 26
    3 30 27
    3 30 28
    3 30 29
    3 30 30
    3 31 11
    3 31 12
    3 31 13
    3 31 14
    3 31 15
    3 31 16
    3 31 17
    3 31 18
    3 31 19
    3 31 20
    3 31 21
    3 31 22
    3 31 23
    3 31 24
    3 31 25
    3 31 26
    3 31 27
    3 31 28
    3 31 29
    3 31 30
    3 31 31
    3 32 11
    3 32 12
    3 32 13
    3 32 14
    3 32 15
    3 32 16
    3 32 17
    3 32 18
    3 32 19
    3 32 20
    3 32 21
    3 32 22
    3 32 23
    3 32 24
    3 32 25
    3 32 26
    3 32 27
    3 32 28
    3 32 29
    3 32 30
    3 32 31
    3 32 32
    3 33 12
    3 33 13
    3 33 14
    3 33 15
    3 33 16
    3 33 17
    3 33 18
    3 33 19
    3 33 20
    3 33 21
    3 33 22
    3 33 23
    3 33 24
    3 33 25
    3 33 26
    3 33 27
    3 33 28
    3 33 29
    3 33 30
    3 33 31
    3 33 32
    3 33 33
    3 34 12
    3 34 13
    3 34 14
    3 34 15
    3 34 16
    3 34 17
    3 34 18
    3 34 19
    3 34 20
    3 34 21
    3 34 22
    3 34 23
    3 34 24
    3 34 25
    3 34 26
    3 34 27
    3 34 28
    3 34 29
    3 34 30
    3 34 31
    3 34 32
    3 35 12
    3 35 13
    3 35 14
    3 35 15
    3 35 16
    3 35 17
    3 35 18
    3 35 19
    3 35 20
    3 35 21
    3 35 22
    3 35 23
    3 35 24
    3 35 25
    3 35 26
    3 35 27
    3 35 28
    3 35 29
    3 35 30
    3 35 31
    3 35 32
    3 36 13
    3 36 14
    3 36 15
    3 36 16
    3 36 17
    3 36 18
    3 36 19
    3 36 20
    3 36 21
    3 36 22
    3 36 23
    3 36 24
    3 36 25
    3 36 26
    3 36 27
    3 36 28
    3 36 29
    3 36 30
    3 36 31
    3 37 13
    3 37 14
    3 37 15
    3 37 16
    3 37 17
    3 37 18
    3 37 19
    3 37 20
    3 37 21
    3 37 22
    3 37 23
    3 37 24
    3 37 25
    3 37 26
    3 37 27
    3 37 28
    3 37 29
    3 37 30
    3 37 31
    3 38 13
    3 38 14
    3 38 15
    3 38 16
    3 38 17
    3 38 18
    3 38 19
    3 38 20
    3 38 21
    3 38 22
    3 38 23
    3 38 24
    3 38 25
    3 38 26
    3 38 27
    3 38 28
    3 38 29
    3 38 30
    3 39 14
    3 39 15
    3 39 16
    3 39 17
    3 39 18
    3 39 19
    3 39 20
    3 39 21
    3 39 22
    3 39 23
    3 39 24
    3 39 25
    3 39 26
    3 39 27
    3 39 28
    3 39 29
    3 39 30
    3 40 14
    3 40 15
    3 40 16
    3 40 17
    3 40 18
    3 40 19
    3 40 20
    3 40 21
    3 40 22
    3 40 23
    3 40 24
    3 40 25
    3 40 26
    3 40 27
    3 40 28
    3 40 29
    3 41 14
    3 41 15
    3 41 16
    3 41 17
    3 41 18
    3 41 19
    3 41 20
    3 41 21
    3 41 22
    3 41 23
    3 41 24
    3 41 25
    3 41 26
    3 41 27
    3 41 28
    3 41 29
    3 42 15
    3 42 16
    3 42 17
    3 42 18
    3 42 19
    3 42 20
    3 42 21
    3 42 22
    3 42 23
    3 42 24
    3 42 25
    3 42 26
    3 42 27
    3 42 28
    3 43 15
    3 43 16
    3 43 17
    3 43 18
    3 43 19
    3 43 20
    3 43 21
    3 43 22
    3 43 23
    3 43 24
    3 43 25
    3 43 26
    3 43 27
    3 43 28
    3 44 15
    3 44 16
    3 44 17
    3 44 18
    3 44 19
    3 44 20
    3 44 21
    3 44 22
    3 44 23
    3 44 24
    3 44 25
    3 44 26
    3 44 27
    3 45 16
    3 45 17
    3 45 18
    3 45 19
    3 45 20
    3 45 21
    3 45 22
    3 45 23
    3 45 24
    3 45 25
    3 45 26
    3 45 27
    3 46 16
    3 46 17
    3 46 18
    3 46 19
    3 46 20
    3 46 21
    3 46 22
    3 46 23
    3 46 24
    3 46 25
    3 46 26
    3 47 16
    3 47 17
    3 47 18
    3 47 19
    3 47 20
    3 47 21
    3 47 22
    3 47 23
    3 47 24
    3 47 25
    3 47 26
    3 48 17
    3 48 18
    3 48 19
    3 48 20
    3 48 21
    3 48 22
    3 48 23
    3 48 24
    3 48 25
    3 49 17
    3 49 18
    3 49 19
    3 49 20
    3 49 21
    3 49 22
    3 49 23
    3 49 24
    3 49 25
    3 50 17
    3 50 18
    3 50 19
    3 50 20
    3 50 21
    3 50 22
    3 50 23
    3 50 24
    3 51 18
    3 51 19
    3 51 20
    3 51 21
    3 51 22
    3 51 23
    3 51 24
    3 52 18
    3 52 19
    3 52 20
    3 52 21
    3 52 22
    3 52 23
    3 53 18
    3 53 19
    3 53 20
    3 53 21
    3 53 22
    3 53 23
    3 54 19
    3 54 20
    3 54 21
    3 54 22
    3 55 19
    3 55 20
    3 55 21
    3 55 22
    3 56 19
    3 56 20
    3 56 21
    3 57 20
    3 57 21
    3 58 20
    3 59 20
    4 1 1
    4 2 2
    4 3 2
    4 3 3
    4 4 3
    4 4 4
    4 5 3
    4 5 4
    4 5 5
    4 6 4
    4 6 5
    4 6 6
    4 7 4
    4 7 5
    4 7 6
    4 7 7
    4 8 5
    4 8 6
    4 8 7
    4 8 8
    4 9 5
    4 9 6
    4 9 7
    4 9 8
    4 9 9
    4 10 6
    4 10 7
    4 10 8
    4 10 9
    4 10 10
    4 11 6
    4 11 7
    4 11 8
    4 11 9
    4 11 10
    4 11 11
    4 12 7
    4 12 8
    4 12 9
    4 12 10
    4 12 11
    4 12 12
    4 13 7
    4 13 8
    4 13 9
    4 13 10
    4 13 11
    4 13 12
    4 13 13
    4 14 8
    4 14 9
    4 14 10
    4 14 11
    4 14 12
    4 14 13
    4 14 14
    4 15 8
    4 15 9
    4 15 10
    4 15 11
    4 15 12
    4 15 13
    4 15 14
    4 15 15
    4 16 9
    4 16 10
    4 16 11
    4 16 12
    4 16 13
    4 16 14
    4 16 15
    4 16 16
    4 17 9
    4 17 10
    4 17 11
    4 17 12
    4 17 13
    4 17 14
    4 17 15
    4 17 16
    4 17 17
    4 18 10
    4 18 11
    4 18 12
    4 18 13
    4 18 14
    4 18 15
    4 18 16
    4 18 17
    4 18 18
    4 19 10
    4 19 11
    4 19 12
    4 19 13
    4 19 14
    4 19 15
    4 19 16
    4 19 17
    4 19 18
    4 19 19
    4 20 11
    4 20 12
    4 20 13
    4 20 14
    4 20 15
    4 20 16
    4 20 17
    4 20 18
    4 20 19
    4 20 20
    4 21 11
    4 21 12
    4 21 13
    4 21 14
    4 21 15
    4 21 16
    4 21 17
    4 21 18
    4 21 19
    4 21 20
    4 21 21
    4 22 12
    4 22 13
    4 22 14
    4 22 15
    4 22 16
    4 22 17
    4 22 18
    4 22 19
    4 22 20
    4 22 21
    4 22 22
    4 23 12
    4 23 13
    4 23 14
    4 23 15
    4 23 16
    4 23 17
    4 23 18
    4 23 19
    4 23 20
    4 23 21
    4 23 22
    4 23 23
    4 24 13
    4 24 14
    4 24 15
    4 24 16
    4 24 17
    4 24 18
    4 24 19
    4 24 20
    4 24 21
    4 24 22
    4 24 23
    4 24 24
    4 25 13
    4 25 14
    4 25 15
    4 25 16
    4 25 17
    4 25 18
    4 25 19
    4 25 20
    4 25 21
    4 25 22
    4 25 23
    4 25 24
    4 26 14
    4 26 15
    4 26 16
    4 26 17
    4 26 18
    4 26 19
    4 26 20
    4 26 21
    4 26 22
    4 26 23
    4 26 24
    4 27 14
    4 27 15
    4 27 16
    4 27 17
    4 27 18
    4 27 19
    4 27 20
    4 27 21
    4 27 22
    4 27 23
    4 27 24
    4 28 15
    4 28 16
    4 28 17
    4 28 18
    4 28 19
    4 28 20
    4 28 21
    4 28 22
    4 28 23
    4 29 15
    4 29 16
    4 29 17
    4 29 18
    4 29 19
    4 29 20
    4 29 21
    4 29 22
    4 29 23
    4 30 16
    4 30 17
    4 30 18
    4 30 19
    4 30 20
    4 30 21
    4 30 22
    4 30 23
    4 31 16
    4 31 17
    4 31 18
    4 31 19
    4 31 20
    4 31 21
    4 31 22
    4 32 17
    4 32 18
    4 32 19
    4 32 20
    4 32 21
    4 32 22
    4 33 17
    4 33 18
    4 33 19
    4 33 20
    4 33 21
    4 33 22
    4 34 18
    4 34 19
    4 34 20
    4 34 21
    4 35 18
    4 35 19
    4 35 20
    4 35 21
    4 36 19
    4 36 20
    4 36 21
    4 37 19
    4 37 20
    4 38 20
    4 39 20

如果囚犯取的時候正好剩下第二列數目的豆子,那麼囚犯有策略可以保證活下來。

這裡沒有考慮囚犯的陰謀算計問題。如果互相算計的話,很容易大家都死掉。如果互相幫助的話,也就是活3人死2人,有很多種方法,也沒什麼意思。


問題:是否允許第一個人拿走全部100顆?還是最多只能拿走96顆?
暫時還沒推算完,但感覺上是他們全都會死的樣子……
其他人的答案似乎都漏了一點:只有第二人確切知道第一人拿了多少,後面的都只能靠算前人的剩餘來推算。

除非第一個人能找到強迫後續四人給自己一條活路的方法,否則必然強迫所有人跟自己一起死。
關鍵在於第一人。
第一人僅靠自己存活的方案我暫時還沒想出來,他大概也許很可能需要讓第二人配合自己。若如此,則他需要收買第二人,結果是一二活,三四五至少死兩個。
繼續推論,若有解,則最多推到第三人,若第三人能活,則四五必死。
再參考海盜分金,也許有方案讓第一人跳過第二人直接收買第三人配合,但這個很難——第二人若發現自己必死,會儘可能讓所有人一起死。

又算了算,貌似第一人能誘使後續者配合自保的方案,都會導致自己必死……

再算了算,若第一人拿3顆,第二人要如何取,就很玄妙啊……

關鍵還是在於題目是否允許強制0,即輪到某人時已經沒有豆子了。


這裡面如果沒人自願犧牲所有人就會一起死,上面的大拿忘了一個問題,從人性的角度,其實第一名取5~~20沒有任何區別比如說取10,那麼第二名只能在9~~11里取,不然後面的人只要在第一名和第二名之間就可以存活並把第一名和第二名幹掉。

這個問題好像傳炸彈,一定要一個人把炸彈拿去丟掉,丟炸彈的人一定會死,不過不丟炸彈所有人都會死。而第一個人擁有定製時間的權利,卻沒有丟炸彈的權利,所以他面臨等死和一起死的選擇。

而第二名到第五名都是準備丟炸彈的人,但是前提是要有一個人和第一名不一樣才能丟炸彈。(同歸於盡的不考慮)所以第二名也沒有權利丟炸彈,不過可以做橋樑,讓後來的人丟炸彈。

情況很明顯了,就是第二名願不願意做橋樑,願意的話就第一名和第二名中死一個,第三名到第五名之間死一個,如果不願意的話問題拋給第三名。以此類推如果炸彈推到第五名還沒有橋樑,全體玩完,所以第四應該果斷做橋樑,要是這樣,第五名就絕對死定了,不過確定三人存活。

好吧,說到這裡有人說我不對題目了,明明是儘可能多殺人,為什麼我一直在保人?真正的答案在下面,可能出人意料的簡單。

其實這個問題是威勢理論和零和博弈的變種,威勢就是同歸於盡,零和博弈就是有人贏就有人輸。做個比喻,5個國家因為沒有資源要大戰,至少需要消滅兩個國家才能生存,而且每個國家都擁有毀滅全世界的核武器,當一個國家的存活率等於0%的時候,這個國家就會發動毀滅世界的核武器。

結果怎麼樣?五個國家要麼餓死,要麼被核平,生存率都是0%,因為缺少犧牲精神的2個國家,第一個犧牲的國家可能是身不由己,但是第二個國家絕對知道得清清楚楚,在犧牲就自己和基友死,不犧牲就全部死里做選擇,然而在生存幾率等於0%時,威勢理論開啟同歸於盡策略。

所以,在設定所有人都極度自私的情況下,答案只有一個,那就是,全部玩完! 這個問題帶來了一個思考,如果5個人都是白痴,那麼至少他們還有3/5的存活率,不過嘛╮(╯_╰)╭


這裡是最後的最後了,假設五個人都是自私且聰明的,那麼他們就能預見前面的問題,那麼他們會怎麼做呢?
他們通過協商,制定一個計劃,計劃第一點:所有人生還幾率相等。計劃第二點:在處決之前沒有人能知道自己是否生還(防止同歸於盡)。計劃第三點:假設所有人智商一樣高,沒有人可能想出不被識破的作弊行為。最後,人們的生存幾率從0%提升到20%~~60%,大概就醬。

不過這裡的幾率可以再用窮舉法再細算,可以再提升個人的生存幾率,不過要這樣想的話,還要再考慮人性的角度,我不是這個專業的,所以在此懇請看到的大拿幫我補充,謝謝謝謝呀!


作為一個曾經的老軟體工程師,一眼就看出這題目在邏輯上的不嚴謹。

1,是只能抓一次,還是可以抓多次?
2,是一起抓,還是先後抓,後抓的人是否能看到前面的人抓了多少?


團滅呀。不取平均數,就必死。取平均數就團滅。最終還是團滅。


推薦閱讀:

TAG:文化 | 演算法 | 數學 | 邏輯 | 博弈論 |