第十二講：游戲必勝的策略

1、第十二講游戲必勝的策略我國古代有一個 “田忌賽馬” 的故事； 齊王經(jīng)常要求將軍田忌和他賽馬。 規(guī)定各從自己的馬 中選上等馬、中等馬、下等馬各一匹，進行三場比賽，每場各出一匹馬。每勝一場可得一千 金。 田忌的這三個等級的馬都不如齊王的好。但田忌的上等馬要優(yōu)于齊王的中等馬，田忌 的中等馬要優(yōu)于齊王的下等馬。 田忌的朋友孫臏給他出了一個主意， 叫田忌用下等馬對齊王 的上等馬， 上等馬對齊王的中等馬， 中等馬對齊王的下等馬。 結(jié)果， 田忌先負(fù)一場然后連勝 兩場，反而贏了一千金。這個故事是對策的一個典型例子。他告訴我們：在競爭時，要認(rèn)真 分析研究、 尋求并制定盡可能好的方案。 利用它取得盡可能大的勝利，

2、 或在勝利無望的時候， 也不至于輸?shù)锰珣K。這種思想在 20 世紀(jì)形成了對策論這門新興學(xué)科。下面我們就根據(jù)這個理論來想一想對策：例1、 兩個人輪流數(shù)數(shù)，每個人每次可以數(shù)1 個、 2 個、3 個，但不能不數(shù)。例如第一個數(shù)1、2，第二個接著往下數(shù) 3，也可以數(shù) 3、 4，還可以數(shù) 3、4、 5,。如此繼續(xù)下去， 誰先數(shù)到 100 ，誰就算勝。請試一試，怎樣才能獲勝？分析：要搶到 100，必須搶到 96.這時另一個人只能數(shù) 97 或 97、98 或數(shù) 97、98、99，無法數(shù)到 100。如何才能搶到 96 呢？有必須搶到 只要搶到這些數(shù)中的任何一個，然后當(dāng)對方報 這樣就能搶到這個數(shù)列中的上一個數(shù)，直到

3、搶到 但無論第一個人報什么數(shù)，第二個人都可以搶到92.以此類推，得到一列數(shù)92、88、84、, 、 4.a個數(shù)時（1 w aw 3）時，就報（4-a）個數(shù)， 100.4n（n=1 、2, ）因此第二個人就有必勝的策略。只有在第二個人產(chǎn)生錯誤時，第一個人才能獲勝。思考： 如果將 100 改為 101 或 99 ，其他條件都不變， 先數(shù)的人能否獲勝呢？ （是否還是搶 4 呢？）例 2、有兩堆火柴，一堆 16 跟，一堆 11 跟。甲乙兩人輪流從中拿走 1 根或幾根甚至一堆， 但每次只能在某一堆中拿火柴，誰拿走最后一根誰取勝，問甲如何才能取勝？分析： 這是另一類對策游戲。 我們先考慮特殊情況。 當(dāng)兩堆

4、中的火柴根數(shù)相同時， 后取者只 要根據(jù)先取者的取法， 在另一堆中取相同的根數(shù)， 就能保證取到最后一根。 對一般情況可以 化為特殊情況。解：甲從 16 根的那堆中先取出 16-11=5 根，是兩堆火柴根數(shù)相同。然后每次根據(jù)對手取得 根數(shù)在另一堆中取相同的根數(shù)，是兩堆火柴根數(shù)保持相等，直至取到最后一根火柴而獲勝。 說明：當(dāng)乙先取時，如果他不知道獲勝的策略，那么甲可以利用已的錯誤取勝。例3、 一張3X 10的長方形網(wǎng)格紙有 30個小方格。甲乙兩人輪流用剪刀沿方格紙直線剪一 刀。（只能沿直線剪，否則為輸）甲將一份分為兩份，選送一份給乙；乙按要求剪一 刀后，選一份再送給甲 , 如此重復(fù)進行，誰送給對方一

5、個方格，誰就獲勝。甲要 想獲勝，有何策略 ？分析：送給對方一個正方形的方格紙，這時后剪的都可以使圖形再變成（更小的）正方形， 知道取勝為止。解：甲先剪下7X 3的一塊，把3X 3的那塊送給乙。乙只能剪成1 X 3和2 X 3的兩塊。若送 給甲1X3的那塊，正好使甲剪下 1X2而獲勝。若送給甲2X3的那塊，那么甲再一刀剪成 1X2和2X 2的兩塊 ，把2X 2的送給乙。乙只可能切成 1X 2的兩塊。其中一塊送給甲， 甲還是獲勝。同學(xué)們，這種方法你考慮到了嗎？你會不會再遇到問題時，先動腦筋想辦法。例4、下圖是一張由4X 10個方格組成的棋盤， 一人持白子置于 A位，另一人持黑子置于 B 位。隨后兩

6、個人輪流走子， 每一次可以沿一條橫線或一條縱線至少走一格， 并要遵守下列游 戲規(guī)則：(1) 不允許和對方的棋子在同一條直線上。(2 )不能越過對方棋子所在的直線。輪到誰無路可走，就算輸。flCA分析：為了找到規(guī)律，我們先從最簡單的情況入手，以便找到獲勝的策略。(1) A(1)圖中的形勢解：如果棋盤只有一個方格，兩子置于正方形的對角，誰先走誰輸。在22的棋盤上，先走者按規(guī)則只能走動一格，這時后者仍能走一格，變成因此，持白子的人第一步應(yīng)沿長邊移動6格到C點處，C與B是4 X 4的正方形對角(兩個相對的頂點)然后不論黑子如何移動，白子均可移動，使他和黑子仍然處于一個較小的正方 形的對角，直至變成 1

7、 X1正方形，黑子認(rèn)輸?？偨Y(jié)：以上幾例，實質(zhì)上都是利用一種對稱原理來解決的。只要搶先給對方制造一個對稱圖形，輸?shù)娜艘欢ㄊ菍Ψ健＠?、甲乙兩人輪流在黑板上寫不超過10的自然數(shù)。游戲規(guī)則：不允許寫黑板上已寫過的數(shù)的約數(shù)。輪到誰無法寫數(shù)時，就是輸者?，F(xiàn)甲先寫，乙后寫，問誰能獲勝？需要 什么對策？分析：仍然利用對稱原理。搶先給對方制造一個對稱。只要甲先寫6.解：甲先寫6。乙還有4、5、7、8 9、10六個數(shù)可以選擇。把他們分成三組(4,5)、(8,10 )、(7,9)。乙寫某組數(shù)中的一個時，甲就寫同組數(shù)中的另一個，從而一定獲勝。 練習(xí)1、 甲乙兩人輪流報數(shù)，每次報的數(shù)必須是1至8之內(nèi)的自然數(shù)。把兩人報

8、的數(shù)逐次相加， 誰正好使和達到 88，誰就獲勝，甲欲取勝，有何策略？2、 桌面上有1999根火柴，甲甲乙兩人輪流的取1根或2根，誰取到最后一根火柴誰獲勝。 問獲勝的策略是什么？3、有兩個箱子分別裝有 63、108個球。甲乙兩個輪流在任意箱中取球，規(guī)定取得最后一個 球的為勝。甲先取，他應(yīng)如何取才能取勝？4、現(xiàn)有三堆火柴，分別為 3、5 8根。兩人輪流取，每次可以取走其中的一堆，也可以取走一堆中的若干根(一次不能從兩堆中取，最少要取一根)。誰取到最后一根或一堆，誰獲勝。先取的人要保證獲勝的策略是什么？5、把 16 枚棋子排成一行。甲乙二人輪流取走棋子，每人每次可以取走緊挨著的兩枚（如 果兩枚棋子當(dāng)中已經(jīng)有其他棋子被取走，就不算緊挨，就不能同一次取走）如果在甲取 走棋子后，乙再也找不到緊挨著的兩枚棋子可以取，甲獲勝。甲有獲勝辦法嗎？6、圖中是一張2X9棋盤。甲置白