倒推法的步驟是: 要想贏,我必須先走這一步,為此必須迫使對方走那一步; 此前我又必須… . 這裏有兩道可用倒推法求解的遊戲題, 不妨一試: 1. 兩個人輪流依次報數: 所報的第一個數必須是1至9中的某個數. 以後報的數必須比對方剛才所報的數大1至此10. (1) 如果報出15的人為獲勝者, 請解釋為什麽首先報4的人一定獲勝. (2) 如果報出100的人為獲勝者, 請問誰一定獲勝? 他的策略是什麽? (3) 您能推廣到一般情況嗎? 2. 兩個人玩報日期遊戲. 第一個人報 “1月1日” 開始;此後輪流報日期: 下一個人必須往前改變月份或日期. 比如, 第二個人可說 “1月5日” 或 “3月1日”. 報出 “12月31日”者為勝. 請問, 第二個人必須報哪個日期才能獲取? 3.(1)四個同心圓被四條直線分成8個部分.在最外層的圓環中的某一個扇區,已經放置了一枚棋子.兩個人輪流移動棋子一步:可以順時針走一格,或者朝中心走一格;但是,已經進入過的扇區不能再進入.走最後一步的人是贏家.請問,是先走的人必勝,還是後走的人必勝?(2)如果是5個同心圓被5條直線分成9個部分,情況又如何? 4 (COMC 2007-B3) Alphonse and Beryl are back! They are playing a two person game with the following rules: --Initially, there is a pile of N stones, with N ≥ 2. --The players alternate turns, with Alphonse going first. On his first turn, Alphonse must remove at least 1 and at most N – 1 stones from the pile. --If a player removes k stones on their turn, then the other player must remove at least 1 and at most 2k – 1 stones on their next turn. --The player who removes the last stone wins the game. (a) Determine who should win the game when N = 7, and explain the winning strategy. (b) Determine who should win the game when N = 8, and explain the winning strategy. (c) Determine all values of N for which Beryl has a winning strategy. Explain this strategy. |