算法合集之由感性認識到理性認識——透析一類搏弈游戲的解答過程(已修改)
2025-01-21 09:23 本頁面
【正文】 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 1 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 一、 游戲 ................................................................................................. 2 二、 從簡單入手 .................................................................................... 2 三、 類比與聯(lián)想 .................................................................................... 6 四、 證明 ................................................................................................. 8 五、 推廣 ............................................................................................... 11 六、 精華 ............................................................................................... 12 七、 結(jié)論 ............................................................................................... 16 八、 總結(jié) ............................................................................................... 17 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 2 一、 游戲 ? 游戲 A： ? 甲乙兩人面對若干堆石子，其中每一堆石子的數(shù)目可以任意確定。例如圖 1所示的初始局面：共 n=3 堆，其中第一堆的石子數(shù) a1=3，第二堆石子數(shù) a2=3，第三堆石子數(shù) a3=1。兩人輪流按下列規(guī)則取走一些石子，游戲的規(guī)則如下： ? 每一步應取走至少一枚石子； ? 每一步只能從某一堆中 取走部分或全部石子； ? 如果誰無法按規(guī)則取子，誰就是輸家。 圖 1 游戲的一個初始局面 ? 游戲 B： ? 甲乙雙方事先約定一個數(shù) m，并且每次取石子的數(shù)目不能超過 m 個； ? 其余規(guī)則同游戲 A。 我們關心的是，對于一個初始局面，究竟是先行者（甲）有必勝策略，還是后行者（乙）有必勝策略。 下面，我們從簡單入手，先來研究研究這個游戲的一些性質(zhì)。 二、 從簡單入手 ? 用一個 n 元組 (a1, a2, … , an)，來描述游戲過程中的一個局面。 ? 可以用 3 元組 (3, 3, 1)來描述圖 1 所示的局面。 第一堆： a1=3 第二堆： a2=3 第三堆： a3=1 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 3 ? 改變這個 n 元組中數(shù)的順序，仍然代表同一個局面。 ? (3, 3, 1)和 (1, 3, 3)，可以看作是同一個局面。 ? 如果初始局面只有一堆石子，則甲有必勝策略。 ? 甲可以一次把這一堆石子全部取完，這樣乙就無石子可取了。 ? 如果初始局面有兩堆石子，而且這兩堆石子的數(shù)目相等，則乙有必勝策略。 ? 因為有兩堆石子，所以甲無法一次取完； ? 如果甲在一堆中取若干石子，乙便在另一堆中取同樣數(shù)目的石子； ? 根據(jù)對稱性，在甲取了石子之后，乙總有石子可?。? ? 石子總數(shù)一直在減少，最后必定 是甲無石子可取。 ? 對于初始局面 (1)，甲有必勝策略，而初始局面 (3, 3)，乙有必勝策略。 ? 局面的加法： (a1, a2, …, a n) + (b1, b2, …, b m) = (a1, a2, …, a n, b1, b2, …, b m)。 ? (3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。 ? 對于局面 A, B, S，若 S=A+B，則稱局面 S 可以分解為“子局面” A 和 B。 ? 局面 (3, 3, 1)可以分解為 (3, 3)和 (1)。 ? 如果初始局面可以分成兩個相同的“子局面”，則乙 有必勝策略。 ? 設初始局面 S=A+A，想象有兩個桌子，每個桌子上放一個 A 局面； ? 若甲在一個桌子中取石子，則乙在另一個桌子中對稱的取石子； ? 根據(jù)對稱性，在甲取了石子之后，乙總有石子可取； ? 石子總數(shù)一直在減少，最后必定是甲無石子可取。 ? 初始局面 (2, 2, 5, 5, 5, 5, 7, 7)，可以分成兩個 (2, 5, 5, 7)，故乙有必勝策略。 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 4 ? 對于局面 S，若先行者有必勝策略，則稱“ S 勝”。 ? 對于局面 S，若后行者有必勝策略，則稱“ S 負”。 ? 若 A=(1)， B=(3, 3)， C=(2, 2, 5, 5, 5, 5, 7, 7)，則 A 勝， B 負， C 負。 ? 我們所關心的，就是如何判斷局面的勝負。 ? 如果局面 S 勝，則必存在取子的方法 S→T ，且 T 負。 ? 如果局面 S 負，則對于任意取子方法 S→T ，有 T 勝。 ? 設初始局面 S 可以分解成兩個子局面 A 和 B（分解理論） 。 ? 若 A 和 B 一勝一負，則 S 勝。 ? 不妨設 A 勝 B 負； ? 想象有兩個桌子 A 和 B，桌子上分別放著 A 局面和 B 局面； ? 因為 A 勝，所以甲可以保證取桌子 A 上的最后一個石子； ? 與此同時，甲還可以保證在桌子 B 中走第一步的是乙；
試題試卷相關推薦
鄂ICP備17016276號-1