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.

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

- The count start starts at 0
- Two players take turns adding to the count
- On each turn, a player must add 1, 2, or 3 to the count.
- 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.

- Draw out the complete game tree for this game.
- 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.
- 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?