Indian Computing Olympiad

Training Material


Games and strategies

A Multiplication Game (ACM contest)

This is a two player game. The players start with the number X = 1 and play alternately. A move consists of picking a number j in the range {2,3,...,9} and updating X to X⋅j.

For instance, here is a possible evolution of the game:

                  X
               -----
Start with    :   1
P1 plays 2    :   2
P2 plays 7    :  14
P1 plays 2    :  28
P2 plays 3    :  84
...
      

The game is specified with a target number N. The first player who makes X ≥ N wins.

Given N, and assuming that both players play optimally, compute which player will win.

Solution

Whoever plays in the interval N/9 ≤ X < N wins, because he can make X cross N in one move. Whoever plays in the interval N/18 ≤ X < N/9 loses, because he cannot reach N in one move but he also cannot avoid pushing X into the winning range N/9 ≤ X < N. In the same way, the interval N/(9*18) ≤ X < N/18 is winning, because the player who plays in this interval can force the next move to be in the losing interval N/18 ≤ X < N/9.

In this way, we can label the intervals back from N

           Win         Lose        Win
... N/162 <----> N/18 <----> N/9 <----> N
      

Now, look at whether 1 falls in a Win or Lose interval — this can be done in log N steps. Depending on this, P1 (the player who moves first) wins or loses.