遊戲簡介
chomp是一個雙人遊戲，有m x n塊曲奇餅排成一個矩形格狀，稱作棋盤。
----兩個玩家輪流自選一塊還剩下的曲奇餅，而且還要把它右邊和下邊所有的曲奇餅都取走（如果存在）
----先吃到左上角(1,1)那塊曲奇餅的玩家為失敗
如圖所示
------紅方選擇(3,3)--->
------藍方選擇(1,4)---->
----紅方選擇(1,2)--->
-----藍方選擇(2,1)-->
------------>紅方玩家隻能選左上角那一塊，失敗
分析
首先介紹一個重要定理——策梅洛定理(zermelo)
下面證明：除去 1 x 1大小的棋盤外，其他大小的棋盤，先手存在必勝政策。
證明：（反證法）
假設棋盤規模為m x n。
首先，遊戲不可能産生平局。
其次，由于每一步移動至少吃掉1塊曲奇餅幹，是以不超過 mn 步後遊戲必定結束。
由策梅洛定理，這個确定性二人有限遊戲資訊完備，且不存在平局，則或者先行一方有必勝政策，或者後行一方有必勝政策。
如果後手有必勝政策，使得無論先手第一次取哪個石子，後手都能獲得最後的勝利。
那麼現在假設先手取最右下角的石子(m,n) ，接下來後手可以取某塊曲奇(a,b) 使得自己進入必勝的局面。
事實上，先手在第一次取的時候就可以取曲奇 (a,b) ，之後完全模仿後手的必勝步驟，迫使後手失敗。
于是産生沖突。是以不存在後手必勝政策，先手存在必勝政策。
注意：這個證明是非構造性存在性證明，也即隻是證明了先手必勝政策的存在性，但沒有構造出具體必勝政策。而且目前還沒有人給出chomp一般性的必勝政策。
其中一些簡單的情況，可以找到必勝政策：
1、棋盤隻有一行，但多于一格
-------先手拿去除左上角的全部即可
2、棋盤是正方形，但多于一格
-------先手選取(2,2),之後無論後手做什麼，先手隻要模仿即可（即關于對角線對稱選取）
3、棋盤隻有兩行
------先手取第二行最後一個，之後無論後手選什麼，先手總能采取合适的選擇，使得第一行比第二行多一個
類似問題
1、三維chomp遊戲
将曲奇排成 p x q x r 的立方體，兩個玩家輪流自選吃掉一塊剩下的曲奇餅，若取走的曲奇餅為 (i,j,k) ，則也要取走所有滿足 i ≤ a ≤ p，j ≤ b ≤ q ， k ≤ c ≤ r 的曲奇餅(a,b,c)（如果存在）。
可以類似地将chomp遊戲擴充到任意維，并可以類似地證明，先手都存在必勝政策。
2、有限偏序集上的chomp遊戲
chomp遊戲可以推廣到在任意一個存在最小元 a 的有限偏序集(s,≤)上：兩名遊戲者輪流選擇s中的元素 x ，移走 x 以及所有 s 中比 x 大的元素。失敗者是被迫選擇最小元 a 的玩家。
如果 (s,≤) 有最大元素 b ，那麼在偏序集上的chomp遊戲存在一個獲勝政策.
3、約數遊戲
給定一個大于1的自然數 n ，兩個遊戲參與者輪流選擇n的大于1的正約數，但不可選擇之前被選擇過的因子的倍數（例如 n = 72，有一方之前選擇了4，則之後任一方都不可以再選擇36）
4、删數遊戲
給定整數集合 {1,2,...n} ，兩個人輪流從中選擇一個數字，并将它和它的約數從集合中删除，删除最後一個數的人獲勝。
以上幾個遊戲，類似chomp遊戲，得到結論就是無論 n 是幾，都是先手必勝。
參考連結：中國大學mooc 離散數學 劉铎
個性簽名：時間會解決一切