發刊日期 |
2023年9月
|
---|---|
標題 | 有關單堆奇偶的拈 |
作者 | |
關鍵字 | |
檔案下載 | |
全文 |
一、前言有關『拈 (nim)』的遊戲, 大略可分為單堆、 二堆、 及三堆以上三大類。 有一種單堆的拈, 若每次可取 1 到 $k$ 個, 不管約定取走最後一個的獲勝或敗, 則安全狀態以 $1 \!+\! k$ 為模的同餘呈現。 有一種兩堆的拈叫做威氏遊戲, 可以從一堆中取走任意個, 或是從兩堆中取走相同的任意個, 取完最後石子的獲勝; 這是荷蘭數學家威佐夫 (Willem Abraham Wythoff) 於 1907 年發表的論文, 是以最接近黃金分割比為斜率的整數點的座標, 作為安全狀態的兩堆, 其特點是每一個正整數都會在安全狀態的座標上出現一次, 且連續的兩個費氏數列: $(1 ,2),(3 ,5),(8 ,13),\ldots$ 等都是安全狀態的兩堆 (充分但非必要)。 三堆以上的拈, 最常見的一種是: 只能選擇任一堆, 並從中取走任意個; 則是以各堆數的二進位表示的不進位加法的和是否全為偶數, 來判斷是否為安全狀態。 這三種拈的重要精神就是『安全狀態』的攻防。 在拈遊戲中的「安全狀態」, 是指出手後留下此狀態的人安全, 接著要下的人, 無論如何下都不會贏得遊戲; 而「不安全狀態」指的是留下此狀態的人不安全, 接著要下的人有一種下法會贏得遊戲。 例如每次可取1到2個的遊戲, 留下3個的人就是取得安全狀態, 對手取 1 你取 2, 對手取 2 你取 1, 遊戲就結束了; 若留下 4 或 5 個的人就是不安全狀態, 接下來的人一定能留下 3 個, 就是取得安全狀態。 在對手留下的不安全狀態下, 你一定有辦法在下一次操作中變成安全狀態留給對手; 而且這個安全狀態, 對手『絕對無法』在下一次操作中變成安全狀態留給你。 同樣的, 如果對手將安全狀態留給你, 你也『絕對無法』在下一次操作中變成安全狀態留給對手; 這裡說的『絕對無法』是可以用數學方式證明的, 所以不會有任何妙招造成逆轉勝的情形, 這些用到的數學證明正是拈遊戲的價值。 儘管這些證明處理起來難易有別, 但各自都具有重要的數學概念。 通常對遊戲的條件稍作改變, 安全狀態也跟著改變, 但致勝的要領仍然離不開原本的數學概念。 如果加入的新條件還能加入一些數學元素, 使遊戲更有變化, 就值得研究一下了。 先看一個例子: 取 17 個小石子合成一堆, 由兩人輪流取出。 每人每次至少取 1 顆, 至多取3顆, 直到全部被取完, 檢視各人手中的石子, 得奇數顆者為勝。 這是單堆的『拈』遊戲, 因為總和為奇數, 所以最後兩人一定是一奇一偶, 絕不會有和局, 合乎拈的要求。 但因為雙方手中的石子隨時有奇數偶數的變化, 所以安全狀態的掌握要比一般單堆的的拈複雜一些, 但讀者可以從 3 顆、 5 顆、 7 顆等較小的奇數開始嘗試, 也許可以親自驗證出下列獲勝的要訣: 1. 每次取完後若自己手上有奇數個 (不管對手已取的個數), 若能留下 $8n$ 或 $8n\!+\!1$ (視對手已取的奇偶)中之一種, 就是在拈的遊戲中取得安全狀態。 2. 每次取完後若自己手上有偶數個 (不管對手已取的個數), 若能留下 $8n\!+\!4$ 或 $8n\!+\!5$ (視對手已取的奇偶) 中之一種, 也是安全狀態。 3. 若無法達成上述 1. 或 2. 的任何一種狀況, 表示對手已先取得安全狀態, 你已無法在這一次操作中取得安全狀態。 最佳策略是儘量少取, 以拖待變, 等待對手犯錯沒有回到安全狀態, 才能在下一手再設法達成上述 1. 或 2. 之一種狀態。 4. 因為起始狀態是 $(0 , 0)$ 且總數是奇數, 所以只有 $8n\!+\!5$ 時對先手不利 (即無法達成 1. 2. 之任何一種), 其餘情況先手都能取得安全狀態。 這遊戲的安全狀態以模8的同餘呈現, 而不是原來的模 4 (即 $1\!+\!3$), 這個 8 應該是來自 $2\times (1\!+\!3)$。 至於每次取 1 到 $k$ 個的條件, 這個 $k$ 對安全狀態的模的影響有何規律, 將在本文中另行探討。 這樣有關奇偶的遊戲, 安全狀態比一般單堆的拈稍微複雜一點了。 對所有拈的遊戲來說, 如果雙方都知道安全狀態的公式, 不是搶著當先手, 就是不願當先手, 如此一來拈的遊戲就玩不下去了。 只好再改變遊戲條件, 讓安全狀態更複雜, 更不容易算出, 才能讓拈的遊戲回到數學的探討: 觀察、 分析、 歸納、 證明的本質。 像前述的安全狀態對雙方而言是相同的, 如果把遊戲規則再做以下的修改, 雙方就各自有不同的安全狀態, 便是一個值得研究的新遊戲了。 二、介紹有關單堆奇偶的拈首先讓遊戲者知道, 將偶數分成兩個整數, 一定是同奇或同偶, 不會是一奇一偶。 因此兩人先要選定為奇方 (設為甲) 或偶方 (設為乙), 並決定誰是先手。 再由公正的第三者取稍大的偶數顆石子為一堆, 兩人輪流取石子, 每次為 1 到 3 顆, 整堆取完後, 兩人手上石子的奇偶必相同, 都是奇則甲勝, 都是偶則乙勝。 如果沒有公正的第三者, 可由兩人先決定一個目標偶數, 再像網球選手在比賽前拋銅板, 由勝者在 (奇、 偶)、 (攻、 守) 四個選項間先選一項; 再由負者在另一性質的兩項中, 作最後完成選邊及先攻後守的決定。 如此一來可以避免雙方事先計算石子總數是否為己方的安全或不安全狀態, 而搶著先下或拒絕先下, 俾能使遊戲順利進行。 三、遊戲分析顯然這遊戲仍是單堆的拈, 但其難度在於彼此無法改變對手已取石子數的奇偶。 為記錄及分析遊戲變化, 設定 $(a,b,r)$ 分別為: $a =$ 奇方手上石子數, $b =$ 偶方手上石子數, $r =$ 堆中剩餘石子數, 在這裡同時定義: 若且唯若 $(a_1,b_1,r_1 ) \!\equiv\! (a_2,b_2,r_2)$, 則 $a_1\!\equiv\! a_2$ (模 2), 且 $b_1\!\equiv\! b_2$ (模 2), 且 $r_1\!\equiv\! r_2$ (模 8)。 將有助於遊戲過程的簡化和證明。 當 $r$ 變成 0 時, 遊戲就結束了。 以下是幾個最簡單的分析: 1. $(0,0,2)$ 太簡單了, 很容易看出來接下來要取的人一定會贏: 2. $(1,1,2)$ 仍然是接下來要取的人一定會贏: 3. $(0,0,4)$ 4. $(1,1,4)$ 5. $(0,1,5)$ 6. $(1,0,5)$ 把 $(0,0,2)$ 對照 $(1,1,2)$ 及 $(0,0,4)$ 對照 $(1,1,4)$ 的分析過程我們可以得到一個結論: 如果 $(0,0,n)$ 不是某一方的安全狀態, 則 $(1,1,n)$ 也不是另一方的安全狀態; 如果 $(0,0,n)$ 是某一方的絕對安全狀態, 則 $(1,1,n)$ 也是另一方的絕對安全狀態。 說明: 對於 $(1,1,n)$ 下一個人可以採用對方在 $(0,0,n)$ 的策略就會獲勝。 以 (0,0,6)和(1,1,6)來看: (0,0,6)奇先下可以取 2 成 $(2,0,4) \equiv (0,0,4)$ 為奇方的絕對安全狀態; (1,1,6) 偶先下可以取 2 成 $(1,3,4) \equiv (1,1,4)$ 為偶方的絕對安全狀態。 (0,0,6) 偶先下可以取 1 成 $(0,1,5)$ 為偶方的安全狀態; (1,1,6) 奇先下可以取 1 成 $(2,1,5)\equiv (0,1,5)$ 為奇方的安全狀態。 所以 $(0,0,6)$、 $(1,1,6)$ 都不是任一方的安全狀態, 即下一手必可取得安全狀態。 以 (0,0,8) 和 (1,1,8) 來看: (0,0,8) 奇取 1 變成 (1,0,7), 偶可以取3變成 $(1,3,4)\equiv (1,1,4)$; 奇取 2 變成 $(2,0,6) \equiv (0,0,6)$; 取 3 變成 $(3,0,5)\equiv (1,0,5)$ 都不是奇方的安全狀態。 (0,0,8) 偶取3變成 $(0,3,5) \!\equiv\!(0,1,5)$ 是偶的安全狀態。 所以(0,0,8)是偶方的絕對安全狀態。 (1,1,8) 偶取 1 變成 $(1,2,7) \equiv (1,0,7)$, 奇可取 3 變成 $(4,0,4)\equiv (0,0,4) $; 偶取 2 變成 $(1,3,6) \equiv (1,1,6)$; 取 3 變成 $(1,4,5) \equiv (1,0,5)$ 都不是偶的安全狀態。 (1,1,8) 奇取3變成 $(4,1,5) \!\equiv \! (0,1,5)$ 是奇的安全狀態。 所以(1,1,8)是奇方的絕對安全狀態。 7. (1,0,9) 奇先無法取成 (1,1,8) 的安全狀態, 且偶方都可以在下一手立即取得安全狀態。 所以 (1,0,9) 是偶方的安全狀態。 8. (0,1,9)奇先取 1 變成 (1,1,8), 為奇方的絕對安全狀態, 所以 (0,1,9)不是偶方的安全狀態; 把 (0,1,5) 對照 (1,0,5) 及 (0,1,9) 對照 (1,0,9) 的分析過程, 我們可以得到另一個結論: 如果 $(0,1,n)$ 或 $(1,0,n)$ 不是某一方的安全狀態, 則同時也不是另一方的安全狀態; 如果 $(0,1,n)$ 或 $(1,0,n)$ 是某一方的安全狀態, 則同時也是另一方的安全狀態。 說明: 對於不是安全狀態的 $(0,1,n)$ 或 $(1,0,n)$, 雙方可以採用的取法是一樣的。 以 (1,0,5) 來看, 雙方先取 1 就變成 (0,0,4) 或 (1,1,4) 的己方安全狀態; 以 (0,1,7) 來看, 雙方先取 2 就變成 (0,1,5) 的己方安全狀態。 四、安全狀態公式的歸納與證明由上面分析整理雙方的安全狀態: 奇方有: (0,0,4), (0,1,5), (1,1,8), (1,0,9); 偶方有: (1,1,4), (0,1,5), (0,0,8), (1,0,9)。 其他不在上述 8 種安全狀態的 (0,0,2), (1,1,2), (0,1,3), (1,0,3), (0,0,6), (1,1,6), (0,1,7), (1,0,7), 對雙方而言都不是安全狀態, 無論先手是奇或偶, 都可在下一手取得己方的安全狀態, 所以都是先手勝。 從 $r$ 的變化來觀察, 正好是前述奇數的拈的四個安全狀態 $8n$、 $8n\!+\!1$、 $8n\!+\!4$、 $8n\!+\!5$。 我們可以大膽地假設: 奇方的安全狀態為: $(0,0,8n\!+\!4), (0,1,8n\!+\!5), (1,1,8n), (1,0,8n\!+\!1)$; 偶方的安全狀態為: $(1,1,8n\!+\!4), (0,1,8n\!+\!5), (0,0,8n), (1,0,8n\!+\!1) $。 以下先證明奇方的四種安全狀態, 偶方均無法只用一步就進入偶方的安全狀態, 且奇方都可以在下一步取回安全狀態。 一. $(0,0,8n\!+\!4)$: 偶方取 1 變成 $(0,1,8n\!+\!3)$, 而奇方可取3變成 $(1,1,8n)$; 二. $(0,1,8n\!+\!5)$: 偶方取 1 變成 $(0,2,8n\!+\!4) \equiv (0,0,8n\!+\!4)$, 而奇方可取 3 變成 $(3,0,8n\!+\!1) \equiv (1,0,8n\!+\!1)$; 三. $(1,1,8n)$: 偶方取 1 變成 $(1,2,8n\!-\!1) \equiv (1,0,8n\!+\!7)$, 而奇方可取 3 變成 $(4,0,8n\!+\!4) \equiv (0,0,8n\!+\!4)$; 四. $(1,0,8n\!+\!1)$: 偶方取 1 變成 $(1,1,8n)$, 而奇方可取 3 變成 $(4,1,8n\!-\!3) \equiv (0,1,8n\!+\!5) $; 同法可以證明偶方的四種安全狀態, 奇方都無法在下一步取成奇方的安全狀態, 而偶方都可以在奇方取完之後, 重新取回安全狀態, 所以完整地形成拈的基本架構。 五、和一般的拈不同的地方一般的拈, 通常安全狀態是共有的, 所以雙方搶進的目標一致, 也無法從自己的安全狀態只取一次又回到自己的安全狀態; 但這個奇偶的拈有兩種特殊的現象: 一. 奇方的安全狀態 $(0,0,8n\!+\!4)$, 可由奇方取成 $(3,0,8n\!+\!1)\equiv (1,0,8n\!+\!1)$, 仍為奇方的安全狀態; 二. 當初始狀態為 $(1,0,8n\!+\!1)$ 或 $(0,1,8n\!+\!5)$, 是雙方共同的安全狀態, 先手都無法回到自己的安全狀態, 所以先手不利。 三. 此外的各種狀態都是先手有利, 可以在正確的下一步取得安全狀態。 所以這個有關奇偶的拈, 有各自不同的單方安全狀態, 也有共同的安全狀態, 遊戲中除了爭取搶進自己的安全狀態, 也要避免對手搶進單方的安全狀態, 如此才合乎知己知彼百戰百勝的戰略準則。 六、安全狀態的一般化 (模與 $k$ 的關係)現在回到每次取 $a$ 到 $b$ 個對安全狀態的變化, 如果 $a$ 大於 1, 當最後留下比 $a$ 小的數量時, 雙方都無法將石子取完, 遊戲必將中斷, 必須另定勝負標準徒增困擾。 所以規定每次 1 到 $k$ 個, 是比較完美的拈。 以下是用前述的分析方法整理出 $k$ 從 2 到 6 的結果。 A. 每次取 1 到 2 個。 B. 每次取 1 到 3 個。 C. 每次取 1 到 4 個。 D. 每次取 1 到 5 個。 E. 每次取 1 到 6 個。 不難從 $k$ 的變化歸納出安全狀態中 $r$ 的模為: 當 $k$ 為偶數時, 安全狀態的 $r$ 是以 $M = k\!+\!2$ 為模, 且所有安全狀態的 $r$ 只有三種: $M, M\!+\!1, M + (k\!+\!1)$。 即 奇方的安全狀態為: $(0,1,Mn\!+\!k\!+\!1), (1,0,Mn\!+\!1), (1,1,Mn)$; 偶方的安全狀態為: $(0,1,Mn\!+\!k\!+\!1), (1,0,Mn\!+\!1), (0,0,Mn)$。 當 $k$ 為奇數時, 安全狀態的 $r$ 是以 $M = 2\times (k\!+\!1)$ 為模, 且所有安全狀態的 $r$ 有四種: $M, M\!+\!1, M + (k\!+\!1), M + (k\!+\!2)$。 即 奇方的安全狀態為: $(0,0,Mn\!+\!k\!+\!1), (0,1, Mn\!+\!k\!+\!2), (1,0,Mn\!+\!1), (1,1,Mn)$; 偶方的安全狀態為: $(1,1,Mn\!+\!k\!+\!1), (0,1,Mn\!+\!k\!+\!2), (1,0,Mn\!+\!1), (0,0,Mn)$。 如果把 $k$ 為偶數時的 $M = k\!+\!2$ 寫成 $M = 2\times (k/2+1)$, 會和 $k$ 為奇數時的 $M = 2\times (k\!+\!1)$ 得到一致的形式。 尾聲在所有單堆的拈中, 每一手可選取的變化就是 $k$ 中選一, 所以 $k$ 愈大變化愈多。 但每一安全狀態在對手選取後, 都只有唯一的一種取法才能正確地回到安全狀態。 所以採用愈大的 $k$, 遊戲的難度愈大, 連用樹族圖分析都不容易, 瞎貓碰上死耗子而獲勝的機率就愈小, 愈能促進心算的能力。 最後討論一下 $k = 1$ 時的特殊情形, 一般以為兩人輪流一次限取一個的遊戲, 勝負早在遊戲開始的數量, 及決定先後手時就一併決定了。 因為 $k = 1$ 時, 每手回應只有一種取法, 中途是否能改變安全狀態已無從選擇, 因此每次只限定取 1 個的遊戲不是拈的遊戲。 但將 $k=1$套入上述結論, 可以得到 $M = 2\times (1+1)=4$, 即
奇方的安全狀態為: $(0,0,4n\!+\!2), (0,1,4n\!+\!3), (1,0,4n\!+\!1), (1,1,4n)$; 偶方的安全狀態為: $(1,1,4n\!+\!2), (0,1,4n\!+\!3), (1,0,4n\!+\!1), (0,0,4n)$。 就是以 $(0,0,4n\!+\!2)$ 開始的, 奇方必勝; 以 $(0,0,4n)$ 開始的, 偶方必勝。 雙方最後一定是各取一半, $2n\!+\!1$ 或 $2n$ 與先後手無關, 因為這兩種初始狀態是各方的絕對安全狀態, 過程中對手也無法搶回自己的安全狀態, 本文安全狀態的一般性公式仍然適用, 堪稱完美的公式, 不知這樣的說法能不能被大家接受? 參考資料本文作者為高雄市中正高中退休教師 |