A matches games
Suppose there are 30 matches on a table.
I begin by picking up 1, 2 or 3 matches. Then my opponent
must pick up 1, 2 or 3 matches. We continue in this fashion
until the last match is picked up. The player who picks up the last
match is the loser. How can I (the first player) be sure of winning
the game ?
The value of game is equal to 1 if the player wins the game.
The value of game is equal to 0 if the player loses the game.
Define Sk to be the maximum value of game to the player whose move
it is when
k matches remain, where 0 £ k £ 30.
The recurrence relation:
|
Sk = |
max
j=1,2,3
|
{ 1 - Sk-j }, k=4,...,30. |
|
The initial conditions:
|
