1、剛才她出石頭，如果她還出石頭、我怨0I. 2. 3!哈哈*羸了 I件炮如果預(yù)料到我這樣想她、善府她就要出布. 就會(huì)出剪子.出 石頭？ ”1以肯我沒(méi)有3 乂和 也ZE q她就會(huì)心所以我還應(yīng)該，”又她如果1八考慮過(guò)，而C、樣出石頭./出布/第十講游戲策略卡莉妍向墨莫 W學(xué)看了。石頭勇f子布 吆蟻對(duì)策論又稱博弈論，研究的現(xiàn)象與政治、經(jīng)濟(jì)、軍事乃至人們的日常生活學(xué)習(xí)都有密切的聯(lián)系.一般地，在具有競(jìng)爭(zhēng)或?qū)剐再|(zhì)的行為中，參加競(jìng)爭(zhēng)對(duì)抗的 各方具有不同的目標(biāo).為了達(dá)到各自的目標(biāo)，各方既要制定出對(duì)自己最有利的方案，又要考慮到對(duì)手所有可能采取的方案.對(duì)策論就是研究競(jìng)爭(zhēng)對(duì)抗中各方是否 存在最佳行 動(dòng)方案，以及如何

2、找到這個(gè)最佳方案.我們將要學(xué)習(xí)的對(duì)策問(wèn)題，主要是研究在兩人的游戲過(guò)程中如何使自己取勝的策略問(wèn)題.如果說(shuō)“統(tǒng)籌規(guī)劃”所研究的是“死的”對(duì)象的話，那么“對(duì)策問(wèn) 題”所 研究的就是一個(gè)“活的”對(duì)手，因而在考慮問(wèn)題時(shí)需要設(shè)想對(duì)手可能采取 的各種方案，并使己方的策略能在對(duì)手所有可能采取的方案中都處于有利位置，我們將這種狀態(tài)稱作“必勝狀態(tài)”（否則稱為“必?cái)顟B(tài)”） ？那么在給定的游戲 規(guī)則下，是 否存在必勝狀態(tài)，以及為了達(dá)到必勝狀態(tài)所采取的策略就成了問(wèn)題的 關(guān)鍵.需要強(qiáng)調(diào)的是，我們的目標(biāo)不是“可能勝”，而是“必勝”！我們不能存在僥 TOC o 1-5 h z 幸心理，不能寄希望于對(duì)方的失誤，而是要在假定雙

3、方都足夠聰明的前提下尋找必勝策略.例題1有12枚棋子，甲、乙兩人輪流取，規(guī)定甲先取，每人每次至少取1枚，最多取3枚.如果誰(shuí)取走最后一枚棋子誰(shuí)贏，那么誰(shuí)有必勝策略？ 如果誰(shuí)取走最后一枚棋子誰(shuí)輸，那么誰(shuí)有必勝策略？必勝策略是什么？分析直接考慮12枚棋子并不容易，大家不妨試試棋子較少時(shí)誰(shuí)有必勝策略，看看能否找到規(guī)律.練習(xí)1有15枚棋子，甲、乙兩人輪流取，規(guī)定甲先取，每人每次至少取1枚，最多取2枚.如果誰(shuí)取走最后一枚棋子誰(shuí)贏.那么誰(shuí)有必勝策略？如果誰(shuí)取走最后 一枚 棋子誰(shuí)輸，那么誰(shuí)有必勝策略？必勝策略是什么？情況很復(fù)雜時(shí)，我們往往需要先從比較簡(jiǎn)單的情況開(kāi)始嘗試，在逐漸變復(fù)雜 的 過(guò)程中，尋找規(guī)律進(jìn)而解

4、決題目.這其實(shí)是一種非常重要的數(shù)學(xué)思想， 高年級(jí) 乃至 往后的數(shù)學(xué)學(xué)習(xí)中應(yīng)用的遞推、數(shù)學(xué)歸納法等都是以此為基礎(chǔ)的 .利用互補(bǔ)的想法，我們有更一般的結(jié)論.“有m枚棋子，兩人輪流取棋子， 規(guī)定 每人每次可以取走1至n枚，直到把棋子取完為止，誰(shuí)取得最后的一枚棋子誰(shuí)勝?”其取勝策略是：每次取走棋子數(shù)除以n 1的余數(shù)枚棋子，讓對(duì)方面對(duì)n1的倍數(shù)枚棋子一一必?cái)顟B(tài)，則可保證取到最后的一枚棋子而獲勝.例題2現(xiàn)有2014根火柴.甲、乙兩個(gè)人輪流從中取出火柴，規(guī)定甲先取，每人每次至少?gòu)闹腥〕?根，最多取出4根.如果誰(shuí)無(wú)法取出火柴誰(shuí)就贏，請(qǐng)問(wèn)誰(shuí)一定能贏？策略是什么？分析本題中每人每次最少要取出2根火柴，如果恰好剩

5、下1根火柴，就已經(jīng) 無(wú)法再次取出了 ？能否像例題1那樣，從火柴較少的情況入手，找出規(guī)律呢？練習(xí)現(xiàn)有2009個(gè)糖豆，甲、乙兩個(gè)人輪流取從中出糖豆，每次至少?gòu)闹腥〕?個(gè)，最多取出5個(gè)，誰(shuí)無(wú)法取出糖豆誰(shuí)就贏？如果甲先取，請(qǐng)問(wèn)誰(shuí)一定能贏？策略是什么？在一定能分出勝負(fù)的對(duì)策問(wèn)題中，一方要么處于必勝狀態(tài)，要么處于必?cái)?態(tài). 處于必勝狀態(tài)的一方，總能進(jìn)行一次適當(dāng)?shù)牟僮骱?，把必?cái)顟B(tài)留給對(duì)手 .反之，處 于必?cái)顟B(tài)的一方，無(wú)論采取什么策略，都只能把必勝狀態(tài)留給對(duì)手 .在很多對(duì)策問(wèn)題中，具有對(duì)稱性的狀態(tài)往往是解決問(wèn)題的關(guān)鍵 .例題3甲、乙兩人玩一個(gè)游戲：有兩堆小球，甲、乙兩人輪流從中取球，每 次 只能從同一堆

6、中取，個(gè)數(shù)不為零即可.規(guī)定取到最后一個(gè)球的人贏，甲先取球.如果開(kāi)始時(shí)兩堆分別有五個(gè)球和八個(gè)球，那么誰(shuí)有必勝策略？請(qǐng)說(shuō)明理由.分析直接考慮5個(gè)和8個(gè)并不容易，你能像之前一樣，從最簡(jiǎn)單的情況開(kāi)始分析，找到規(guī)律嗎？練習(xí)3甲、乙兩個(gè)海盜分金幣：有兩堆金幣，一堆有 2009枚，一堆有2014枚.甲、乙輪流從中拿金幣，每次只能從同一堆中拿，個(gè)數(shù)不為零即可.規(guī)定拿到最后一 枚金 幣的人獲勝，勝者可以獲得所有金幣.如果甲先拿，那么誰(shuí)有必勝策略？請(qǐng) 說(shuō)明理由.例題4如下圖，方格A中放有一枚棋子，甲先乙后輪流移 動(dòng)這枚棋子，只能向上、向右或向右上方沿 45 走1步，最終將棋子走到方格 B的人獲勝.請(qǐng)問(wèn)： 一定能獲

7、勝？必勝策略是什么？誰(shuí).一方想要獲勝，必分析在棋盤(pán)中，有一些是必勝格，有一些是必?cái)「耥毭看味及哑遄幼叩奖貏俑褡又校沟脤?duì)手下一步無(wú)論采取什么操作，都不得不進(jìn)入必?cái)「褡?本題中方格B就是必勝格.那么其他的格子中哪些是必勝格？ 哪些是必?cái)「?？BA例題5如下圖，方格A中放有一枚棋子，甲先乙后 輪流移動(dòng)這枚棋子，只能向上、向右或向右 上方沿45角走1步，最終將棋子走到方格 B 的人獲勝.請(qǐng)問(wèn)：誰(shuí)一定能獲勝？必勝策略是什么？如果每次允許往同一方向（上、右或 右上）走任意多步，結(jié)果又如何呢？分析第（1）問(wèn)中，每次只能走1步，那么B為必勝格，貝尼相鄰的左、下、左下三個(gè)格子全是必?cái)「?；第?）問(wèn)中，每次可以走

8、任意多步，那么 B為必勝格，則由B可以直接找出多少個(gè)必?cái)「衲?例題6桌上有一塊巧克力，它被直線劃分成 3行7列的21個(gè)小方塊，如圖 所 示.現(xiàn)在讓你和對(duì)手進(jìn)行一種兩人輪流切巧克力的游戲，規(guī)則如下：每人每次只許沿一條直線把巧克力切成兩塊；拿走其中一塊，把另一塊留給對(duì)手再切；不斷重復(fù)前兩步，最后誰(shuí)能恰好留給對(duì)手一個(gè)小方塊，誰(shuí)獲勝 .如果你首先切巧克力，那么你第一次應(yīng)該切走多少個(gè)小方塊，才能保證自己最后獲勝？卜分析直接分析并不容易，還是先來(lái)看看簡(jiǎn)單情況吧! 如果只有一行或一列的小方塊，誰(shuí)會(huì)次勝？?jī)尚谢騼?列呢？你能發(fā)現(xiàn)什么規(guī)徒呢？在對(duì)策問(wèn)題中，要想取得勝利，必須使自己能始終保持在必勝狀態(tài)中，而使對(duì)手

9、總是處于必?cái)顟B(tài).明確了這一點(diǎn)，我們就知道了解決對(duì)策問(wèn)題的關(guān)鍵在于弄清楚什么是必勝狀態(tài)，什么是必?cái)顟B(tài).“知己知彼，百戰(zhàn)不殆.”哪一方的策 略更勝 一籌，哪一方就會(huì)取得最終的勝利.課堂內(nèi)外田忌賽馬田忌很喜歡賽馬？有一回他和齊威王約定，進(jìn)行一次比賽將馬分成上、中、下三等，比賽的時(shí)候，上等馬對(duì)上等馬，中等馬對(duì)中等馬,下等馬對(duì)下等馬由于齊威王每個(gè)等級(jí)都比田忌的強(qiáng)，三場(chǎng)比下來(lái)，田忌都失敗了？田忌覺(jué)得很掃興，垂頭喪氣地準(zhǔn)備離開(kāi)賽馬場(chǎng).這時(shí)，田忌發(fā)現(xiàn)，他的好朋友孫臏也在人群里 ？孫臏招呼田忌過(guò)來(lái)，拍著他 的肩膀，說(shuō)：“從 剛才的情形看，齊威王的馬比你的馬快不了多少呀”孫臏還沒(méi)說(shuō)完，田忌瞪了他一眼，說(shuō)：“想

10、不到你也來(lái)挖苦我！”孫臏說(shuō)：“我不是挖苦你，你再同他賽一次，我有辦法讓你取勝.”田忌疑惑地看著孫臏：“你是說(shuō)另?yè)Q幾匹馬？ ”孫臏搖搖頭，說(shuō)：“一匹也不用換.” 田忌沒(méi)有信心地說(shuō)：“那還不是照樣輸 ！孫臏胸有成竹地說(shuō)：“你就照我的主意辦吧齊威王正在得意洋洋地夸耀自己的馬,看見(jiàn)田忌和孫臏過(guò)來(lái)了,便譏諷田忌:“怎么，難道你還不服氣？ ”田忌說(shuō)：“當(dāng)然不服氣，咱們?cè)儋愐淮?！”齊威王輕蔑地說(shuō)：“那就來(lái)吧！”一聲鑼響，賽馬又開(kāi)始了 .孫臏讓田忌先用下等馬對(duì)齊威王的上等馬，第一場(chǎng)輸了.接著進(jìn)行第二場(chǎng)比賽？孫臏讓田忌拿上等馬對(duì)齊威王的中等馬，勝了第二場(chǎng)?齊威王有點(diǎn)兒心慌了.第三場(chǎng)，田忌拿中等馬對(duì)齊威王的下等馬

11、，又勝了一場(chǎng) ？這下，齊威王目瞪口呆了 .比賽結(jié)果，田忌勝兩場(chǎng)輸一場(chǎng)，贏了齊威王 .還是原來(lái)的馬，只調(diào)換了一下出場(chǎng)順序，就可以轉(zhuǎn)敗為勝作業(yè)10枚正面朝下的硬幣排成一排放在桌子上，兩個(gè)小朋友玩翻硬幣游戲.規(guī)定：每人每次只能翻動(dòng)一枚或兩枚硬幣使之正面朝上，翻過(guò)的硬幣不能再翻.兩人輪流翻硬幣，翻動(dòng)最后一枚硬幣的人獲勝？請(qǐng)問(wèn)：誰(shuí)有必勝策略？必勝策略是什么？現(xiàn)有200個(gè)石子.甲、乙兩個(gè)人輪流從中取出石子，每次最少?gòu)闹腥〕?個(gè)，最多取出4個(gè)，誰(shuí)無(wú)法取出石子誰(shuí)就贏？如果甲先取，那么誰(shuí)有必勝的策略？必勝策略是什么？甲、乙兩人玩一個(gè)游戲：有兩堆小球，甲、乙兩人輪流從中取球，每次只能從同一堆中取任意多個(gè)，但不能不

12、取.規(guī)定取到最后一個(gè)球的人輸，甲先取球 .(1)如果開(kāi)始時(shí)兩堆各有兩個(gè)球，那么誰(shuí)有必勝策略？請(qǐng)說(shuō)明理由；(2)如果開(kāi)始時(shí)兩堆分別有兩個(gè)球和三個(gè)球，那么誰(shuí)有必勝策略？請(qǐng)說(shuō)明理由 .規(guī)定新畫(huà)甲、乙二人輪流在一個(gè)正十二邊形中畫(huà)對(duì)角線（即兩個(gè)不相鄰頂點(diǎn)的連線）的對(duì)角線不能與已經(jīng)畫(huà)出的對(duì)角線相交，誰(shuí)不能繼續(xù)畫(huà)誰(shuí)輸.甲先畫(huà)，請(qǐng)問(wèn)誰(shuí)有必勝策如卜圖所示，方格 A中放右，枚棋子，甲先乙后輪流移動(dòng)這枚棋子，只能向上、向右.或向右上方沿45角走1步，最終將棋子走到方格 B的人獲勝.請(qǐng)問(wèn)：誰(shuí)一定能獲勝？ 必勝策略是什么？BA第十講游戲策略例題1答案：（1）乙有必勝策略；（2）甲有必勝策略詳解：（1）如果剩不到4枚棋子

13、，先取的人把所有棋子取走后獲勝；如果剩4枚棋子，無(wú)論先 取的人如何取，所剩的棋子數(shù)都不到4枚，所以后取的人獲勝；如果有 12枚棋子，甲取1枚時(shí)乙取3枚，甲取2枚時(shí)乙取2枚，甲取3枚時(shí)乙取1枚，在每次甲取完后，乙可以取適當(dāng)數(shù)量的棋子以保證兩人一個(gè)回合共取 4枚棋子，這樣乙可以拿到最后 1枚，乙勝.（2）如果剩1枚，那么先取的人必?cái)。蝗绻?2至4枚，先取的人可以剩 1枚不取，所以后取 的人敗.12枚 的情況與4枚的情況類似，甲先取 3枚，剩下9枚?之后乙取 1枚時(shí)甲取3枚，乙取2枚時(shí)甲取2枚，乙取3 枚時(shí)甲取1枚，甲保證兩人一個(gè)回合共取 4枚棋子？最后1枚必 然被乙拿到，甲勝.例題2答案：甲有必

14、勝策略詳解：根據(jù)上題經(jīng)驗(yàn)，第二個(gè)人總可以保證和第一個(gè)人共取6根火柴，2014 6 335LL4，所以2014根火柴的情況與4枚火柴的情況相同.4枚火柴時(shí)甲先取2根火柴即可獲勝，因此 2014根火柴時(shí)甲也先取2根火柴，之后乙無(wú)論怎么取，甲再取時(shí)都可以保證兩人一個(gè)回合共取6根火柴.20142 6 335L L 2 ,最后剩下的2根火柴留給了乙，甲無(wú)法取出火柴，甲獲勝 .例題3答案：甲必勝詳解：甲先從 8個(gè)球的那堆中取出三個(gè)球，使得兩堆球一樣多 ？之后每次乙取幾個(gè)球，甲就在另一堆中取相同數(shù)量的球，甲獲勝.例題4答案：甲必勝詳解：我們給必勝格子（如方格 B）標(biāo)記 7,給必?cái)「褡訕?biāo)記“X”？從方格 B逆

15、推，能一 步走到B的格子都要標(biāo)記“X”.特別地，最上邊一行和最右邊一列為“V和“X相間的標(biāo) 記，如左圖.對(duì)于左圖中的格子1和格子3,對(duì)方有辦法把它移到必勝格子中，所以格子1和格子3都是必?cái)「褡?？如果把棋子移到格?中，對(duì)手無(wú)論怎么移，都只能移到必?cái)「褡又校虼烁褡?是必勝格子？用類似的方法分析，得到右圖？因此甲有必勝策略，每次把棋子移到標(biāo)有“V的格子中即可.例題5答案：（1 ）甲必勝；（2）甲必勝詳解：（1 ）我們給必勝格子（如方格 B）標(biāo)記 7,給必?cái)「褡訕?biāo)記“X”?從方格 B逆推,能一步走到B的格子都要標(biāo)記“x”.特別地，最上邊一行和最右邊一列為和“乂相間 的標(biāo)記，如左圖.對(duì)于左圖中的格子

16、1和格子3,對(duì)方有辦法把它移到必勝格子中，所以格子1和格子3都是必?cái)「褡?如果把棋子移到格子 2中，對(duì)手無(wú)論怎么移，都只能移到必?cái)「褡又?，因此格?是標(biāo)有“/的格子中即可必勝格子？用類似的方法分析，得到右圖？因此甲有必勝策略，每次把棋子移到VXVXVXB1XX23VXVAXVXVXVXBXXXXXXXVXVXVXVXXXXXXXVXVXVXVAXXXXXX（2）與第（1）問(wèn)方法類似，得到下圖?甲有必勝策略，每次把棋子移到標(biāo)有“V的格子中即可.6.7.8.9.XXXXXXBXXXXVXXXXXXXVXXVXXXXXXXXXXXXAXXVXXX例題6答案：切走12個(gè)小方塊詳解：當(dāng)只剩1行（或1歹U

17、）時(shí)，但不是一個(gè)小方塊，先切的人只要切剩下一個(gè)小方塊就贏了當(dāng)剩2行（或2歹U）時(shí)，如果剩22的方塊，那么先切的人切完后成為1 2的方塊，所以后切 的人必勝；如果剩2 3、2 4、等情況，先切的人只要切剩下一個(gè)2 2的方塊就可以取勝.當(dāng)剩3行（或3歹U）時(shí)，如果剩3 3的方塊，先切的人切一刀后只能剩下13或2 3的方塊，此時(shí)后切的人獲勝.當(dāng)有37塊時(shí)，先切的人切走34 12塊，給對(duì)手留下一個(gè)33的正方形，接著每次都給對(duì)手 留下一個(gè)11或2 2的正方形即可獲勝.練習(xí)1答案：（1 ）乙必勝；（2）甲必勝詳解：（1）甲取1枚時(shí)乙取2枚，甲取2枚時(shí)乙取1枚，乙只要保證兩人一個(gè)回合共取 3枚棋 子，即可拿

18、到最 后1枚獲勝.（2）甲先取2枚，剩下13枚?之后乙取 1枚時(shí)甲取2枚，乙取2枚時(shí)甲取1枚，甲保證兩人一個(gè) 回合共取3枚棋子，最后1枚必然被乙拿到，甲勝.練習(xí)2答案：甲必勝詳解：20092 5287,甲先取5個(gè)糖豆，之后乙無(wú)論怎么取，甲再取時(shí)都可以保證兩人一個(gè)回合共取7個(gè)糖豆，最后剩下的2個(gè)糖豆留給了乙，甲無(wú)法再次取出糖豆，甲獲勝 .練習(xí)3答案：甲必勝簡(jiǎn)答：甲先從2014個(gè)金幣中取出5個(gè)金幣，使兩堆金幣一樣多？之后每次乙拿幾個(gè)金幣，甲就在另一堆中拿相同數(shù)量的金幣，最后肯定甲拿走最后一個(gè)金幣，甲獲勝 .練習(xí)4答案：甲必勝簡(jiǎn)答：策略是每次把棋子走到下圖中標(biāo)有“V的格子內(nèi).VXVXBXXXXXVXVXVAXXXX作業(yè)1答案：先翻動(dòng)的人必勝簡(jiǎn)答：先翻硬幣的小朋友翻 1枚硬幣，以后對(duì)手翻1枚時(shí)自己翻2枚，對(duì)手翻2枚時(shí)自己翻1枚，保證兩人一個(gè) 回合共翻3枚，即可保證自己翻到最后1枚.作業(yè)2答案：乙必勝簡(jiǎn)答：甲取2個(gè)乙就取4個(gè)，甲取3個(gè)乙也