2011 OIM Problems/Problem 1

Problem

The number 2 is written on the board. Ana and Bruno play alternately, starting with Ana. Each one in turn replaces the written number with the one obtained by applying exactly one of the following operations: multiply it by 2, multiply it by 3, or add 1. The first person to obtain a result greater than or equal to 2011 wins. Find which if they both have a winning strategy and describe said strategy.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

We claim that Bruno can always win, and we painfully work our way downwards from $2011$ . Suppose we are playing the game; below, each letter represents an interval of numbers; if our opponent replaces the previous number with a number in that interval, then we perform the action described.

If the number is in $A=[671,2011]$ , then clearly we can multiply by $3$ to win on the spot.

If the number is in $B=[336,670]$ , then multiplying by $2$ or $3$ would result in $A$ and thus a loss, so the optimal continuation is to add $1$ . Notice that we can only do this for a finite amount of time; once either player writes down $671$ , the other player wins. Thus, if we backtrack, the player who writes down an even number will win (since neither player is incentivized to multiply, we are forced to add $1$ , and parity shows that the player who writes down an odd number will eventually write down $671$ , so the other player wins).

If the number is in $C=[168,335]$ , then multiplying by $2$ results in writing an even number in $B$ , so we win. This case is an automatic loss for any player who writes down a number in $C$ .

If the number is in $D=[112,167]$ , then multiplying by $2$ results in $C$ , so we lose. Multiplying by $3$ results in $B$ , so if the product is even (and thus our original number in $D$ that we received), then we win. Otherwise, we are forced to continue adding $1$ . However, if the number we receive in $D$ is not even, then it is odd, and our opponent can win with the same logic.

If the number is in $E=[84,111]$ , then we eliminate multiplying by $2$ since that would land us in $C$ , an automatic loss. Multiplying by $3$ would land in $C$ , also an automatic loss. Thus both players keep adding $1$ , so once again, the player who receives an even number wins.

If the number is in $F=[56,83]$ , then multiplying by $2$ results in $D$ , and the opponent receives an even number, so they win. If we multiply by $3$ , then we fall in $C$ , which is an automatic loss. Thus both players keep adding $1$ , so we can extend from $E$ that the player who receives an even number wins.

If the number is in $G=[42,55]$ , then multiplying by $2$ results in $E$ writing down an even number, which we lose. Multiplying by $3$ , however, results in $D$ , so if we received an odd number, then the product will also be odd, so we are incentivized to multiply. Thus the player who receives an odd number wins.

If the number is in $H=[38,41]$ , then multiplying by $2$ results in $F$ with an even number, so we lose. Multiplying by $3$ results in $D$ with a similar scenario to if the number is in $G$ , so the player who receives an odd number wins.

If the number is in $I=[28,37]$ , then multiplying by $2$ results in $F$ with an even number, so we lose. Multiplying by $3$ results in a similar scenario as in $G$ and $H$ , so the player who receives an odd number wins.

If the number is in $J=[14,27]$ , then multiplying by $2$ results in one of $G,H,I$ writing down an even number, so either the opponent is forced to give us an odd number or multiply by $3$ , giving us an even number in $E$ or $D$ , which we win. Thus we are guaranteed to win in this case.

If the number is in $K=[10,13]$ , then multiplying by $2$ results in $J$ , which we lose. Multiplying by $3$ results in $I$ or $H$ , which we win only if the original number is even.

Finally, if the number is in $L=[7,9]$ then multiplying by $2$ or $3$ results in $J$ , which we lose. Thus we combine parities with $K$ , so we win only if the number we receive is even.

We can end with casework on the first few turns. If Ana starts by multiplying by $3$ , yielding $6$ , then Bruno can convert this to $7$ , which he wins. If Ana adds $1$ first, then Bruno multiplies by $3$ , yielding $9$ , which he wins. Finally, if Ana starts with multiplying by $2$ , resulting in $4$ , then Bruno can add $1$ . Here Ana cannot multiply by $2$ (Bruno receives even number in $K$ ) or $3$ (guaranteed win in $J$ ), so she must add $1$ , and Bruno can simply add $1$ , resulting in $7$ , which he wins. Since all possibilities are considered, Bruno wins with optimal play.

~ eevee9406

Page

Toolbox

Search

2011 OIM Problems/Problem 1

Problem

Solution

See also