Quiz 8 MAT 118, Spring 2003

- Consider the following variation of the game of Nim:
The game begins with the four digits 1,2,3,4 in a line:

1 2 3 4Players take turns crossing out either one or two

**adjacent**digits. (For example, on your first move, you could cross out 3&4 but not 1&4.) The winner is the player who crosses out the last digit.

Draw a partial game tree that shows that the player who goes first always has a winning strategy, no matter what the other player does.

**Solution:**The winning strategy is to cross out the 2 and the 3 on the first move. Then your opponent must either cross out the 1 or the 4, but not both. This leaves the other one for you to win with.Any other initial move can be countered by your opponent, and so is not a good strategy.

The partial game tree for the winning strategy is below. The numbers indicate what is crossed out by that player during that move.

- Circle which date you prefer for the second midterm.

April 14 April 21 No preference**Solution:**By an overwhelming majority, the preference was to have the exam on April 21.35 people voted for April 21, while 14 voted for April 14. Four had no preference, and the remaining 26 slackers didn't take the quiz, so they have no say in the matter.

Scott Sutherland 2003-04-05