Question

Two players, 1 and 2, take turns choosing numbers; 1 goes first. On his turn, a player may choose any number between 1 and 10, inclusive, and this number is added to a running total. When the running total of both players’ choices reaches 100, the game ends. The player whose choice of number takes the total to exactly 100 is the winner.

(i) Who wins the game when we solve it using backwards induction?

(ii) Provide a (not necessarily formal), description of the winner’s moves that conform with backward induction.

Answer 1

Player 1's choice          Player 2's choice       Running Total
         10                                               10 
                                     5                    15
          8                                               23
                                     8                    31
          2                                               33
                                     9                    42
          9                                               51
                                     9                    60
          8                                               68
                                     9                    77
          9                                               86
                                    10                    96
          4                                              100

Player 1 wins.

If the total T left by player A is between 90 and 99 inclusive, 
player B can take the rest (100 - T) and win. It should be the goal 
of each player not to let that happen. That means that a target 
number for each player is 89. If the running sum is 89, for whatever 
number N player A chooses, player B chooses 11 - N. Then the total 
will be 100, so B wins. Notice that:

     1 <= N <= 10

implies that

     1 <= 11 - N <= 10

so B's choice is allowed by the rules.

Now if the total T left by player A is between 79 and 88, B can choose 
a number 89 - T, which is between 1 and 10, and make the total 89. 
Then B can win. That means that another target number for each player 
is 78.

Similarly, other target numbers are 67, 56, 45, 34, 23, 12, and 1. 
(See a pattern here?) Either player who makes any of these totals can 
win.

Since 1 is a target number, and the first player can choose 1, he 
should do so. Then he can win by this strategy: when the second 
player chooses N, he responds by choosing 11 - N.

11 appears here because the sum of the smallest and largest numbers 
each player can choose is 1 + 10 = 11.