數學家殺人事件

推理劇《古畑任三郎》之「數學家殺人事件」中有這麼一個小插曲。

這是古畑和數學家之間的一個小遊戲：

兩個人輪流數數，從1開始數到16，每人每次可以數1到3個數，規定最後數到16的人就輸了。

我們可愛的古畑大叔並不知道其中訣竅，所以連著輸了兩局。

但是過了兩天，古畑從另一個數學家那裡掌握到了訣竅，大致來看是這樣的：要讓對方數到16的話，自己就必須數到15才行，要數到15你會發現只要數到11即可,因為如果對方數一個數數到到12，你可以連著數3個數直到15；如果對方數2個數數到13，那麼你也數兩個數數到15；如果對方數三個數數到14，那麼你就數一個數數到15。於是只要數到11就能確保自己數到15，那麼同樣的道理，要數到11就只要數到7，要數到7就要數到3，所以呢，誰先數到3，然後一步步數到7,11,15，最後把16丟給對方那就贏了。

好了，諸如此類的博弈其實更接近一個純數學問題，這類問題基本上有如下一些共性：

有兩名玩家。

遊戲有一個確定的局面，該局面是雙方可見的（完全信息）；

規則對遊戲雙方是相同的（公平的），它規定了哪些操作（策略）是可行的；

玩家的操作將使遊戲從一個局面確定地走向另一個局面，無隨機行動；

遊戲將會在有限步內結束，此時有唯一的一方成為贏家。

滿足上述條件的遊戲，稱為無偏博弈。

比如說五子棋就不能算是無偏博弈，因為黑棋有禁手的緣故？就算是無禁手的五子棋也不屬於無偏博弈。記住第條，規則對雙方是相同的，這意味著兩名玩家面對同一局面時，能採取的策略是一樣的。換句話說，或者讓兩個人都可以使用白色和黑色的棋子，或者讓棋子只有黑色或只有白色，而且遊戲結束條件也必須「無偏差」，你可以規定先使五子連成一條直線的人為贏家，但不能規定黑棋代表一個人，白棋代表另一個人。而這當然不能算是一般意義的五子棋了。同樣的道理，凡是有固定顏色的棋子代表某方玩家的，諸如圍棋，象棋，陸戰旗等都不屬於無偏博弈。

無偏博弈在數學上有一定的章法可循。現在來考慮一個和上面古畑先生玩的相同性質的一個「取石子遊戲」：桌子上有15個石子，每人每次可以拿去1到3個石子，拿走最後一個石子的人贏。

這個遊戲其實不管從推理還是從結論上說都和文章開頭的遊戲一樣，不過這次我們嘗試找出更普遍的規律。因為石子的數量總是遞減的，所以這個遊戲必將在有限步（15步）內結束。我們可以用餘下石子的數目來表示局面，於是一共有16個局面。因為規定了拿走最後一個石子的人贏，換句話說當石子個數為0時，就是一個「輪到誰誰就輸」的局面，我們通常叫這種局面為必敗態。既然0是必敗態，那麼當局面為1,2,3時，先手就可以採取規則所允許的策略（拿走1個，2個，或是3個）來把局面變成0，於是稱1,2,3為勝態；而當局面為4時，不論採取何種策略，局面都將走向勝態，從而4是一個必敗態。

現在不用再分析下去我們就知道，一個無偏博弈的局面可以分成兩種：必敗態和勝態。

勝態一定可以通過某種策略走向必敗態；而必敗態採取任何策略都將走向勝態。

假如遊戲開始時的局面是勝態，那麼先手總可以採取適當的策略使勝態走向必敗態，然後交給後手。而後手面對必敗態，無論他怎麼行動，都將走向勝態。假如先手足夠聰明的話，先手就讓後手永遠面臨必敗態，而自己永遠面臨勝態，直至遊戲結束。這就是一個先手（採取適當策略）能必勝的遊戲。反之，如果遊戲開始的局面是必敗態，那麼這就是一個後手必勝的遊戲。

在文章的最後，大家來練練手吧，還是剛才的取石子遊戲，桌子上有15個石子，每人每次可以拿去1個或3個石子，拿走最後一個石子的人贏，能否列出所有的必敗態，找出先手的必勝策略呢？

via：冰羊（果殼）

超模君全球嚴選數學思維好物推薦：

【手動推薦】《黎曼猜想漫談》 盧昌海 著

【好物】科學的故事，最受美國學生歡迎的科學史讀本

【好物】數學和數學家的故事，國內數學科普最具影響力

【數學趣事】無言的宇宙：隱藏在24個數學公式背後的故事

【數學趣事】《數學之旅》數學發展史上的100個重大發現

本文系由超級數學建模整理編輯

分享、轉發請隨意

轉載請在公眾號中，回復「轉載」

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！