Quiz 8         MAT 118, Spring 2003

PRINT your Name: Solution

1. 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     4

   Players 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.

   
   

   

   
   

   
   

2. 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.