Kvant Math Problem 731

The game begins with the first player choosing an initial value $P_0 \in {2,3,4,5,6,7,8,9}$.

kvantmathematicsolympiad

Verified: no
Verdicts: FAIL + FAIL
Solve time: 30m23s
Source on kvant.digital

Problem

Two people play the following game: the first names a natural number from 2 to 9; the second multiplies this number by any natural number from 2 to 9; then the first multiplies the result by any natural number from 2 to 9, and so on. The winner is the player who is the first to obtain a product greater than

  1. one thousand,
  2. one million.

Who wins with correct play—the player who starts or the opponent?

V. G. Boltyansky

Step 1: Correct formulation of the game state

The game begins with the first player choosing an initial value $P_0 \in {2,3,4,5,6,7,8,9}$. After this choice, players alternate multiplying the current product by a number from ${2,3,4,5,6,7,8,9}$. A player wins immediately when their move produces a product strictly greater than $N$.

After the initial choice, the state evolves as

$$P = P_0 \cdot m_1 \cdot m_2 \cdots m_k,$$

where each $m_i \in {2,\dots,9}$. The player making the move that first produces $P > N$ is the winner, so optimal play is determined entirely by how quickly the threshold is crossed under alternating control.

Step 2: Reduction to optimal move choice

At any stage of the game, the current player chooses a multiplier $m \in {2,\dots,9}$. Since all multipliers are greater than $1$, every move strictly increases the product. This means a player who reaches the threshold earlier wins immediately, and delaying one’s own progress only gives the opponent additional opportunities to win.

Suppose a player considers replacing a move $m$ by a larger choice $m' > m$. This replacement increases the product and therefore cannot delay the moment of exceeding $N$ on that player’s future turns, while it may force the opponent to reach the threshold earlier on their turn. Because the game ends immediately upon crossing $N$, there is no defensive advantage to using smaller multipliers.

Thus in optimal play, both players always choose the maximal allowed multiplier $9$.

Step 3: Exact form of play under optimal strategy

Under optimal play, the game becomes deterministic. After the initial choice $P_0$, the product after $k$ multiplications is

$$P_k = P_0 \cdot 9^k.$$

The game ends at the smallest integer $k$ such that

$$P_0 \cdot 9^k > N.$$

Define

$$k^*(P_0) = \min \left{k \in \mathbb{N} : 9^k > \frac{N}{P_0} \right}.$$

The player who makes the $k^$-th multiplication is determined by parity: the second player moves when $k$ is odd, and the first player moves when $k$ is even. Therefore the winner is determined entirely by whether $k^(P_0)$ is odd or even.

The first player’s only strategic choice is the initial value $P_0$, which can influence $k^*(P_0)$.

Step 4: Case $N = 1000$

For $P_0 \in {2,\dots,9}$, consider the range of values

$$\frac{1000}{9} \le \frac{1000}{P_0} \le \frac{1000}{2}.$$

Taking logarithm base $9$, we estimate

$$\log_9(1000) \approx 3.145.$$

More precisely,

$$\log_9!\left(\frac{1000}{9}\right) \approx 2.14, \quad \log_9!\left(\frac{1000}{2}\right) \approx 2.83.$$

Thus for every allowed $P_0$, the value $\log_9(1000/P_0)$ lies strictly between $2$ and $3$. This implies

$$k^*(P_0) = 3$$

for all choices of $P_0$.

Since $k^*(P_0)=3$ is odd, the third multiplication is performed by the second player, and this is the move that first exceeds $1000$. Therefore the second player wins for $N=1000$ under optimal play.

Step 5: Case $N = 10^6$

Now consider $N = 10^6$. For $P_0 \in {2,\dots,9}$, we estimate

$$\frac{10^6}{9} \le \frac{10^6}{P_0} \le \frac{10^6}{2}.$$

Taking logarithm base $9$ gives the range

$$\log_9!\left(\frac{10^6}{9}\right) \approx 5.29, \quad \log_9!\left(\frac{10^6}{2}\right) \approx 5.97.$$

Thus for every allowed initial choice $P_0$, the value $\log_9(10^6/P_0)$ lies strictly between $5$ and $6$. Consequently,

$$k^*(P_0) = 6$$

for all $P_0$.

Since $k^*(P_0)=6$ is even, the sixth multiplication is performed by the first player. This move is the first one that produces a value exceeding $10^6$, so the first player wins for $N=10^6$ under optimal play.

Step 6: Final conclusion

For $N=1000$, the crossing occurs on the third multiplication regardless of the initial choice, which belongs to the second player under alternating play. For $N=10^6$, the crossing occurs on the sixth multiplication regardless of the initial choice, which belongs to the first player.

The first player wins when the threshold is $10^6$, and the second player wins when the threshold is $1000$.