倒推法解游戏题

倒推法的步骤是: 要想赢,我必须先走这一步,为此必须迫使对方走那一步; 此前我又必须… . 这里有两道可用倒推法求解的游戏题, 不妨一试:

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.