Problem 54

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Count to 5

Due: March 1
Points: 6

Let me teach you a new game. It's called "count to 5". Here are the rules.

  1. The count start starts at 0
  2. Two players take turns adding to the count
  3. On each turn, a player must add 1, 2, or 3 to the count.
  4. The first player to add something that makes the count go to 5 or above, loses the game.

So here's an example: Player 1 starts by adding 3, so the count is now 3. Then player 2 adds 1, so the count is now 4. Player 1 adds 1, to make the count 5, and loses the game.

Another example: player 1 starts by adding 2, so the count is now 2. Player 2 adds 1, so the count is now 3. Then player 1 adds 1, to make the count 4. Finally, plater 2 adds 2, to make the count 6, and plater 2 loses.

  1. Draw out the complete game tree for this game.
  2. Is it possible for player 1 to guarantee a win? Or is it possible for player 2 to guarantee a win? Or neither? Whatever the case is, tell me how the game tree shows you that's the case.
  3. What would the best strategy be for whoever can win the game? Or if neither can guarantee a win, what is the strategy that guarantees player 1 can tie?