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.

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.

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky