1、論（1）Zhou Yuan組合by Zhou YuanOutlineCh.1 簡單組合Ch.2 Nimby Zhou YuanCh.1 簡單組合的組合（two-game） 兩人雙方知道所有信息（perfect information）沒有隨機事件（no chance moves） 確定的結果（a win-or-losee）by Zhou Yuan示例如下 有兩個者：I和II桌上有21個石子每個人可以從桌子上拿走1, 2, 3個石子 I開始，兩人輪流取石子 拿走最后一個石子的者獲勝若參加后手必勝者都足夠聰明，判斷先手還是by Zhou Yuan組合稱為組合：抽象定義(Combinatorial

2、Game)如下 有兩個參與者 有一個很多可能的狀態(tài)的集合（一般是有限集） 若兩個人移動規(guī)則都一樣，則稱為公平的（Impartial），這是的主要情況 兩個者交替移動 某個玩家不能移動時結束一般的：最后一個移動的玩家是勝者相反的（最后一個移動的玩家失?。┮彩且环N規(guī)則在有限回合內(nèi)一定結束by Zhou Yuan取石子的狀態(tài)：桌子上：遞推解法的石子數(shù) 0個，1個，2個，21個判斷每一個狀態(tài)先手必勝(N)/先手必敗(P)先手必勝iff.某個后繼狀態(tài)先手必敗先手必敗iff.任何后繼狀態(tài)先手必勝沒有后繼的狀態(tài)先手必?。?先手必敗012345678910resultPNNNPNNNPNNby Zhou Yu

3、an構造必勝策略對于任何一個先手必勝(N)狀態(tài)后繼狀態(tài)中，必有一個先手必敗(P)狀態(tài)選擇這個狀態(tài)，先手就可以保證必勝by Zhou Yuan觀察：的平衡構造必勝策略時，始終將敗局面留給一方看來：石子數(shù)n是4的倍數(shù)就是平衡點 預定的勝利者總是要平衡 預定到失敗者面對平衡點，只能打破平衡，直平衡的主導權在勝利者，終止局面一定是平衡點問題在于：尋找的平衡點by Zhou Yuan)練在取石子的石子中，雙方只能取走如下數(shù)目 1, 3, 5, 7 1, 3, 6 1, 2, 4, 8, 16, 2的整次冪那么哪些狀態(tài)是先手必勝的？by Zhou Yuan練習(2)有兩堆非空石子，一堆m個，一堆n個用(m

4、, n)表示這樣的一個狀態(tài)雙方移動規(guī)則選擇扔掉一堆石子把另一堆石子分成兩堆（每堆非空）唯一的結束狀態(tài)(1, 1)，最后移動這勝利求所有的先手必勝狀態(tài)by Zhou Yuan練習(3)在一個棋盤上的雙方移動規(guī)則：棋盤就是狀態(tài)選擇一個方格（不能是左下角的）移走這個方格和其右上方的所有方格不能移動者失敗一個先手必勝的狀態(tài)矩形棋盤：先手必勝by Zhou Yuan練習(4)一列n方格，初始都是空的雙方輪流選擇一個空方格寫上S或者O第一個完成一個SOS的玩家勝利可能有平局證明n=4, 第一個人在第一個方格寫下一個S, 則后者可以獲勝n=7時先手必勝，n=2000時先手必敗n=14時結果如何？by Zho

5、u YuanCh.2 Nim規(guī)則（兩人） 桌上有很多堆石子，第i堆石子有xi個者輪流選擇一堆石子，從中拿走至少一粒（最多將這一堆取完） 所有石子取完時，最后一個移動的玩家勝利by Zhou Yuan簡要分析只有一堆非空石子：先手必勝（直接取完）有兩堆非空石子 平衡點：兩堆石子相同:(1,1), (2,2), (3,3) 先手從某一堆中拿走一定量石子打破平衡后手可以從另一堆中取走同樣多石子終止狀態(tài)(0,0)也屬于平衡點：先手必敗因此在上述平衡點先手必敗其他非平衡狀態(tài)都可以到達某個平衡狀態(tài)先手必勝平衡by Zhou YuanNim和定義兩個非負整數(shù)的Nim和定義為它們二進制形式的異或和例交換律結合

6、律by Zhou YuanNim和(contd)=求證：證明： 于是元by Zhou Yuan定理1：Boutons TheoremNim中一個局面是先手必敗當且僅當每一堆石子的Nim和是0如4堆石子時，條件為證明思路為每一個勝局面找到一個必敗的后繼局面證明必敗局面的后繼都是勝局面（或無后繼）by Zhou Yuan證明為勝局面找一個必敗后繼局面：構造勝局面：Nim和大于0在Nim和的豎式中找到最高的非0位選擇一堆石子：其二進制在該位上是1可以讓這堆石子變少使得Nim和為0：敗局面11110111000110101010100011101111by Zhou Yuan證明(contd)Nim和是0的敗局面 唯一的終止局面，每一堆石子都是0其他局面的每一個后繼局面反若在第一堆石子中取走一些，Nim和仍為0，于是后繼局面的Nim和不為0：勝局面by Zhou Yuan練習(5)一個一維棋盤，從左到右0,1,2,3,棋盤上有一些硬幣:一個方格上可以有多個雙方輪流移動 選擇一枚硬幣，將它移至左邊的任意一個方格所有硬幣都到0號位最后移動者勝利結束by Zhou Yuan練習(6)著名的Turning Turtles一列n個Turtles，頭朝上(H)/尾朝上(T)雙方輪流移動，最后移動者勝利選擇一個H改為T同時還能選擇左邊的任何一個Turtle