倒推法解遊戲題

倒推法的步驟是: 要想贏,我必須先走這一步,為此必須迫使對方走那一步; 此前我又必須… . 這裏有兩道可用倒推法求解的遊戲題, 不妨一試:

1. 兩個人輪流依次報數: 所報的第一個數必須是1至9中的某個數. 以後報的數必須比對方剛才所報的數大1至此10. (1) 如果報出15的人為獲勝者, 請解釋為什麽首先報4的人一定獲勝. (2) 如果報出100的人為獲勝者, 請問誰一定獲勝? 他的策略是什麽? (3) 您能推廣到一般情況嗎?

 

2. 兩個人玩報日期遊戲. 第一個人報 “1月1日” 開始;此後輪流報日期: 下一個人必須往前改變月份或日期. 比如, 第二個人可說 “1月5日” 或 “3月1日”. 報出 “12月31日”者為勝. 請問, 第二個人必須報哪個日期才能獲取?

 

3.（１）四個同心圓被四條直線分成８個部分．在最外層的圓環中的某一個扇區，已經放置了一枚棋子．兩個人輪流移動棋子一步：可以順時針走一格，或者朝中心走一格；但是，已經進入過的扇區不能再進入．走最後一步的人是贏家．請問，是先走的人必勝，還是後走的人必勝？（２）如果是５個同心圓被５條直線分成９個部分，情況又如何？

 

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.