三道趣題紀(jì)念數(shù)學(xué)游戲大師

1、三道趣題紀(jì)念數(shù)學(xué)游戲大師karsus 2012-03-31 17:25:03第十屆馬丁·加德納聚會(huì)即將結(jié)束。現(xiàn)在不知道點(diǎn)馬丁·加德納的東西還敢叫做數(shù)學(xué)愛好者嗎？怎樣在數(shù)學(xué)系博士面前假裝見多識(shí)廣？和他聊聊馬丁加德納的經(jīng)典著作。第十屆馬丁加德納聚會(huì)3月26日-4月1日正在亞特蘭大舉行。馬丁加德納是美國(guó)數(shù)學(xué)游戲界泰斗，在科學(xué)美國(guó)人雜志上曾開設(shè)了20余年的數(shù)學(xué)游戲?qū)?。他沒有數(shù)學(xué)博士學(xué)位，但是他的謎題讓無數(shù)讀者不止一次燃起對(duì)數(shù)學(xué)的熱情。加德納于 2010 年 5 月 22 日去世，但以他命名的馬丁·加德納聚會(huì)仍在繼續(xù)舉辦，這個(gè)聚會(huì)每?jī)赡暝诿绹?guó)舉行一次，與會(huì)者與加德納的興趣

2、和愛好相同，多是數(shù)學(xué)家、魔術(shù)師和益智游戲愛好者。趁著這個(gè)時(shí)候，死理性派選擇 3 個(gè)馬丁·加德納的趣味數(shù)學(xué)題，讓我們一起來看看數(shù)學(xué)游戲大師的風(fēng)采吧。第十屆馬丁加德納聚會(huì)logo：Gathering for Gardner 10三角決斗的故事漢密爾頓，普希金，伽羅華三個(gè)槍手A、B、C進(jìn)行決斗，規(guī)則不同尋常：三人抽簽決定開槍的順序后，站成一個(gè)等邊三角形，每人每次只開一槍，以抽簽決定的順序循環(huán)往復(fù)，直至只剩一人存活下來。每輪開槍的人可以瞄準(zhǔn)任何人。雖然都是槍手，他們的命中率卻各不相同。漢密爾頓百發(fā)百中，普希金命中率是 80%，伽羅華的命中率只有的50%。我們不考慮意外情況比方子彈沒打出去，如

3、果他們?nèi)硕疾扇∽钫_的策略，那最后誰存活的概率最大？或者說三人幸存的概率分別是多少呢？解答：說來你可能不信，最后結(jié)果是槍法最差的伽羅華存活的概率最大，漢密爾頓的存活概率比普希金要高。這是因?yàn)?，如果輪到漢密爾頓或者普希金開槍的時(shí)候，他們一定會(huì)向?qū)Ψ介_槍，而伽羅華的最正確策略是對(duì)天開槍，直到漢密爾頓和普希金中的一個(gè)倒下否則如果他射殺了某一個(gè)人，另一個(gè)人就要朝他開槍，兩人都是高命中率，存活幾率很小，接下來他可以先對(duì)剩下的那個(gè)人開槍，因此他最容易存活下來。不妨讓我們來具體計(jì)算一下每個(gè)槍手的存活概率：漢密爾頓的最容易計(jì)算，他和普希金的對(duì)決中，先開槍的概率抽簽決定為 1/2，這時(shí)普希金會(huì)被殺死；普希金先

4、開槍的概率也是 1/2，而普希金的命中率是 4/5，所以漢密爾頓對(duì)普希金幸存的概率是 1/2 + 1/2×(1 - 4/5) = 3/5，這時(shí)會(huì)輪到伽羅華開槍，如果伽羅華打不中，漢密爾頓會(huì)把伽羅華打死，因此，漢密爾頓從伽羅華槍下存活的概率是 1/2，所以漢密爾頓生還的概率是 3/5×1/2 = 3/10。普希金存活概率的計(jì)算要復(fù)雜一些，它其實(shí)是個(gè)無窮級(jí)數(shù)。從前面的分析我們知道，普希金面對(duì)漢密爾頓的幸存概率為 2/5，而幸存后他會(huì)對(duì)上伽羅華，伽羅華打不中他的概率是 1/2，而普希金打中伽羅華的概率是 4/5，因此這時(shí)普希金存活的概率為 1/2×4/5 = 4/10，

5、但是如果普希金沒打中，這樣伽羅華會(huì)獲得第二次時(shí)機(jī)，普希金第二輪對(duì)上伽羅華的時(shí)候幸存概率為 1/2×1/5×1/2×4/5 = 4/100，以此類推，第三輪如果有的話普希金的存活概率為 4/1000，第四輪的時(shí)候?yàn)?4/10000最終這個(gè)無窮級(jí)數(shù)的和為 4/10 + 4/100 + 4/1000 + 4/10000 + = 4/9。所以普希金對(duì)伽羅華的幸存概率為 4/9，乘以之前他從漢密爾頓槍下生還的概率 2/5，普希金的生還概率為 2/5×4/9 = 8/45。伽羅華的分析過程與普希金類似，或者用 1 減去漢密爾頓和普希金生還的概率，我們可以算出，他生還

6、的概率為 47/90。 47/90 > 3/10 > 8/45,所以這場(chǎng)決斗槍法最差的伽羅華最可能獲勝，其次是漢密爾頓，最后是普希金。不過更有意思的是，如果伽羅華沒有那么明智，每輪都朝他認(rèn)為的最危險(xiǎn)的對(duì)手，百發(fā)百中的漢密爾頓射擊，最終幸存的概率依然是三人中最高的，為 44.772%。但如此以來，另外兩人的存活率就調(diào)了過來，普希金的幸存概率提升到了31.111%，百發(fā)百中的漢密爾頓幸存概率只有24.167%。或許現(xiàn)實(shí)中也是如此，高手總是死在笨蛋手里。額頭上的數(shù)字圖片來源：parallelozero 教授有兩個(gè)學(xué)生 A 和 B，他們都很老實(shí)且有很強(qiáng)的推理能力。教授挑選了一對(duì)連續(xù)的正整數(shù)

7、分別貼在他們的頭上，兩位學(xué)生可以看見彼此額頭上的數(shù)字，但并不知道自己額頭上的數(shù)字。教授開始不斷問學(xué)生：現(xiàn)在你們知道自己額頭上的數(shù)是多少了么？這樣輪流不斷的問，直至有人說“知道”為止。只過了一會(huì)兒，一個(gè)學(xué)生就答復(fù)“我知道了”。你明白他是怎樣推斷出來的么？解答：如果這一對(duì)連續(xù)的正整數(shù)中較大的數(shù)是 n，那么有一個(gè)學(xué)生會(huì)在教授的第 n 次或者第n-1次提問中答復(fù)“知道”取決于教授先問哪個(gè)學(xué)生。我們利用數(shù)學(xué)歸納法來簡(jiǎn)單分析一下，首先從最簡(jiǎn)單的 1 和 2 開始，頭上數(shù)字是 2 的人將在第 1 次或第 2 次提問的時(shí)候答復(fù)“知道”如果他先被提問則是在第一次提問時(shí)答復(fù)，如果后被提問則是在第二次提問時(shí)答復(fù)，因

8、為看到對(duì)方貼著1后，他會(huì)知道自己頭上的一定是 2?，F(xiàn)在考慮 2 和 3 的情況。當(dāng)?shù)谝淮蜗蛸N著 3 的人提問時(shí)，他會(huì)說不知道，因?yàn)樗吹綄?duì)方是2時(shí)，自己頭上的數(shù)字可能是1也可能是3。如果他是 1，這時(shí)他答復(fù)不知道后，貼著2的人就會(huì)知道自己是 2。但是他是3，所以輪到問貼著 2 的人答復(fù)不知道后不清楚自己是 2 還是 4，第一個(gè)人就知道了自己貼的是 3，因此第二次向貼著 3 的人提問時(shí)，他將答復(fù)知道。于是我們可以像這樣繼續(xù)推理，逐步推廣到任何一對(duì)連續(xù)數(shù)字的情況。對(duì)于這個(gè)問題，普林斯頓的數(shù)學(xué)教授 John Conway 有一個(gè)更加迷惑人的擴(kuò)展。他將 n 個(gè)人頭上貼上 n 個(gè)數(shù)字，這 n 個(gè)數(shù)字可以

9、是任何一組非負(fù)整數(shù)，Conway又在一塊黑板上寫了一組數(shù)，這組數(shù)的個(gè)數(shù)小于或等于 n，且它們彼此不同，其中的一個(gè)數(shù)和之前貼在額頭上的 n 個(gè)數(shù)字之和相等。假設(shè)參加者都是死理性派且很老實(shí)，每人除了看不到自己額頭上的數(shù)字，都能看到其他 n-1 個(gè)人額頭上的數(shù)和黑板上全部的數(shù)。Conway向第一個(gè)人提問，問他能不能推斷出自己額頭上的數(shù)，如果他說不能，則接著問第二個(gè)人，如此循環(huán)往復(fù)，知道有人說知道為止。這個(gè)問題最終也會(huì)有人答復(fù)知道，實(shí)際上這個(gè)問題也可以用數(shù)學(xué)歸納法分析出來，有興趣的讀者可以自己試一試。愛恨分明圖片來源：danlew 有人的地方就有江湖，有人的地方就有愛恨。有這樣 6 個(gè)物理學(xué)家，他們組

10、成了一個(gè)特殊的小團(tuán)體。在這個(gè)團(tuán)體中，任何兩人不是好友就是仇敵，并且團(tuán)體中也沒有彼此都為好友的 3 個(gè)成員。那么你能推斷出他們中一定有 3 個(gè)成員彼此互為仇敵嗎？解答：學(xué)過圖論的同學(xué)對(duì)這題一定不陌生，這算得上一個(gè)經(jīng)典的圖論問題了。我們用六個(gè)小黑點(diǎn) ABCDEF 來分別代表 6 個(gè)物理學(xué)家，再在各個(gè)黑點(diǎn)之間兩兩連上虛線。如果兩個(gè)人互為好友，那么我們將代表他們的點(diǎn)之間的連接虛線涂成紅色，如果互為仇敵，則把虛線涂成藍(lán)色。則按照題意，沒有3個(gè)人互為好友，則我們的圖中不能出現(xiàn) 3 條邊全為紅色的三角形。而我們最終要證明，有3人互為仇敵，則圖中一定有 3 條邊全為藍(lán)色的三角形。不妨從 A 點(diǎn)開始說起， A

11、點(diǎn)與其他 5 個(gè)點(diǎn)有 5 條連接虛線，按照敵友原則對(duì)虛線涂上顏色后，至少有3條虛線的顏色是一樣的，是什么顏色并不重要，是哪 3 條虛線也不重要。我們首先考慮是紅色的情況：假定AB，AC，AD這3條虛線都是紅色的，那么對(duì)于 BCD，如果 BC、CD、DB 這三條邊中有一條為紅色，不妨設(shè)為 BC，那么 ABC 的三條邊均為紅色，這與題意是矛盾的。同理，CD、DB也不能為紅色。故而 BCD 的三條邊都只能涂成藍(lán)色，這樣 B、C、D 三個(gè)點(diǎn)代表的物理學(xué)家則為仇敵。接下來考慮AB、AC、AD這 3 條虛線都是藍(lán)色的情況，對(duì)于 BCD，因?yàn)椴淮嬖?3 條邊均為紅色的三角形，因此 BC、CD、DB 中一定有一條邊是藍(lán)色，不妨設(shè)為 BC，這樣 ABC 的三條邊均為藍(lán)色。所以無論最初選的三條邊是紅色還是藍(lán)色，我們一定可以在圖中找到一個(gè)藍(lán)色的三角形，它表示三個(gè)物理學(xué)家互為仇敵。這個(gè)題目還有一個(gè)更加強(qiáng)的結(jié)論，如果圖中沒有 3 條邊全是紅色的三角形，那么一定會(huì)存在兩個(gè) 3 條邊全是藍(lán)色的三角形。也就是說，這個(gè) 6 人小團(tuán)體中，如果沒有 3 個(gè)物理學(xué)家互為好友，則一定有 2 組 3 個(gè)物理學(xué)家互為仇敵的情況。這個(gè)結(jié)論的證明比上述的要略微復(fù)雜一點(diǎn)，腦力充分的同學(xué)可以自己試試。數(shù)學(xué)游戲就講到這里，馬丁加德納本人并不是一個(gè)數(shù)學(xué)家，他自