尼姆博弈最簡單的解法？

1.

每個N狀態都可以一步到達P狀態。 證明是構造性的。檢查Nim和X的二進制表示中最左邊一個1,則隨便挑一個該位為1的物品堆Y,根據Nim和進行調整(0變1,1變0)即可。 例如Nim和為100101011,而其中有一堆為101110001。為了讓Nim和變為0,只需要讓操作的物品數取操作前的物品數和Nim的異或即可,可驗證一下 顯然操作后物品數變小,因此是合法的。設操作前其他堆的Nim和為Z,則有Y xor Z = X。操作后的Nim和為X xor Y xor Z = X xor X = 0,是一個P狀態

2.

每個P狀態(必敗態)都不可以一步再次到達P狀態 由于只能改變一堆的物品,不管修改它的哪一位,Nim的對應位一定不為0,不可能是P狀態。 這樣就證明了Bouton定理。