Library / /722 of 740

, 2014

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Mark and William are playing a game with a stored value. On his turn, a player may either multiply the stored value by 2 and add 1 or he may multiply the stored value by 4 and add 3. The first player to make the stored value exceed $2^{100}$ wins. The stored value starts at 1 and Mark goes first. Assuming both players play optimally, what is the maximum number of times that William can make a move?

(By optimal play, we mean that on any turn the player selects the move which leads to the best possible outcome given that the opponent is also playing optimally. If both moves lead to the same outcome, the player selects one of them arbitrarily.)

Solution

Solution:

Answer: 33

We will work in the binary system in this solution.

Let multiplying the stored value by 2 and adding 1 be Move $A$ and multiplying the stored value by 4 and adding 3 be Move $B$ . Let the stored value be $S$ . Then, Move $A$ affixes one 1 to $S$ , while Move $B$ affixes two 1s. The goal is to have greater than or equal to 101 1s. If any player makes the number of 1s in $S$ congruent to $2 \bmod 3$ , then no matter what the other player does, he will lose, since the number of 1s in $S$ reaches 101 or 102 only from $99 \equiv 0 (\bmod 3)$ or $100 \equiv 1 (\bmod 3)$ .

Mark's winning strategy: Do Move $A$ . In the succeeding moves, if William does Move $B$ , then Mark does Move $A$ , and vice versa, which in total, affixes three 1s to $S$ . This ensures that William always takes his turn while the number of 1s in $S$ is congruent to $2 \bmod 3$ . Note that Mark has to follow this strategy because once he does not, then William can follow the same strategy and make Mark lose, a contradiction to the required optimal play. Since $S$ starts out with one 1, this process gives William a maximum of 33 moves.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.