問題描述
有一個(gè)m*n方格的巧克力，最左上角一個(gè)方格有毒，兩個(gè)人輪流在這個(gè)巧克力上選一個(gè)方格吃，當(dāng)一個(gè)方格被選了以后，它的右邊和下邊的所有方格全被吃掉。每個(gè)人每輪必須吃，吃到有毒的一方為輸。怎么選擇你的策略？
背景知識
策梅洛定理（Zermelo's theorem）:二人參與的游戲中，如果滿足以下條件，那么先行一方有必勝策略或者后行一方有必勝策略。
- 游戲步驟有限；
- 信息完備（參與者知曉游戲規(guī)則）
- 不會(huì)產(chǎn)生平局
- 確定性（不存在運(yùn)氣成分或者放水行為）
簡單情景
-
棋盤只有一行，但多于一格
先手只需吃掉左上角以外位置的巧克力即可。對于只有一列的棋盤，采取同樣的方法。
-
棋盤是正方形，但多于一格
先手只需吃掉位置(2, 2)的巧克力，隨后模仿后手的吃法，在另一行或列對稱地進(jìn)行相同的操作。
-
棋盤只有兩行
先拿走右下角的一塊，隨后不管后手選擇拿走哪塊，都保證上行比下行多一塊
Three rowed
用有向圖的方法標(biāo)識可行方案。用點(diǎn)Pi表示棋盤所有的可達(dá)狀態(tài)，并用P和N分別標(biāo)識所有先者勝或后者勝的狀態(tài)；用有向邊，如(P1, P2)，表示存在從狀態(tài)P1到狀態(tài)P2的一步可行走法（吃法）。那么，標(biāo)記有向圖中出度為0的點(diǎn)為P，標(biāo)記至少存在一條邊到P點(diǎn)的所有點(diǎn)為N，然后，標(biāo)記那些所有邊到達(dá)的都是N狀態(tài)的點(diǎn)為P，重復(fù)操作。
論文[1]陳述了兩個(gè)結(jié)論，并予以證明：
對任意a≥1，棋盤位置
是一個(gè)P position；當(dāng)a, b滿足a≥b≥0, 且a-b≠1，棋盤位置
是一個(gè)N position. 并且，當(dāng)a=b時(shí)，下一步應(yīng)走(a, a-1)；當(dāng)a≥b-2時(shí)，下一步應(yīng)走(b+1, b).
證明（聯(lián)合歸納）：結(jié)論1顯然是正確的。由結(jié)論2，從狀態(tài)(a, a-1)經(jīng)一步能到達(dá)的狀態(tài)都是N position，如(a-1, a-1), (a-1, a-2), (a-1, a-3), ..., (a, 0)，因此P2(b)隱含P1(a)。并且，a=b或a-b=2，P2(b)隱含在P1(b-1)或P1(b)中。所以有，P1(b-1)和P1(b)隱含P2(b), P2(b-1), ..., p2(1)，能推出P1(b)。又P1(1)是一個(gè)P position，得證。
對不確定的棋盤大小M*N，不存在一個(gè)多項(xiàng)式時(shí)間算法。特別地，當(dāng)M=2時(shí)，對于(a, a-1)這樣的棋盤，能確定P和N狀態(tài)，并且能找到先者勝的方案。下面討論M=3的情況，設(shè)P(a, b, c)。
分析：根據(jù)最開始的依據(jù)，出度為0的點(diǎn)是P點(diǎn)、能一步達(dá)P點(diǎn)的是N點(diǎn)和只能從N點(diǎn)一步到達(dá)的狀態(tài)是P點(diǎn)，可以從兩行的棋盤總結(jié)出如下規(guī)律。
| N position | P position |
|---|---|
| (b+1, b, 1) | (b+1, b, 0) |
| (1, 1, 1) | (1, 0, 0) |
| (a, 0, 0) | (1, 0, 0) |
| a-b≥2時(shí)，(a, a, 0) (a, b, 0) |
特別地，當(dāng)格子數(shù)一共有4格或5格時(shí)，情況如下：
| N position | P position |
|---|---|
| (5, 0, 0) (4, 1, 0) | (2, 2, 1) (3, 1, 1) |
| (4, 0, 0) (3, 1, 0) (2, 2, 0) (2, 1, 1) |
由前面的結(jié)論，我們知道，
-
c=1時(shí)的P狀態(tài)只有(2, 2, 1)和(3, 1, 1)
滿足c=1，且格子數(shù)至少為6的N狀態(tài)是以下情況之一：(3, 2, 1), (3, 3, 1), (4+p, 1, 1), (2+p, 2+q, 1)，p≥q≥0.
因?yàn)樯鲜鏊姆N狀態(tài)能一步達(dá)到P狀態(tài)，如下：
(3, 2, 1) —> (3, 1, 1); (3, 3, 1) —> (3, 1, 1); (4+p, 1, 1) —> (3, 1, 1);
(2+p, 2+q, 1) —> (2, 2, 1)
c=2時(shí)，(a, b, 2)為P狀態(tài)，當(dāng)且僅當(dāng)a-b=2
參考資料
【1】Doron Zeilberger, Three-Rowed CHOMP, Department of Mathematics, Temple University, Philadelphia, Pennsylvania 19122, Advances in Applied Mathematics 26, 168–179 (2001)
