Track / Stage 4 / 276 of 340 #536 of 2000

Problem 536

AMC 12 late, AIME early

Combinatorics Difficulty 5.0 Find the answer

Alice and Bob play the following game: They start with two non-empty piles of coins. Taking turns, with Alice playing first, they choose a pile with an even number of coins and move half of the coins of this pile to the other pile. The game ends if a player cannot move, or if we reach a previously reached position. In the first case, the player who cannot move loses. In the second case, the game is declared a draw.
Determine all pairs $(a, b)$ of positive integers such that if initially the two piles have $a$ and $b$ coins respectively, then Bob has a winning strategy.
(Cyprus)

Your answer

Official solution

By $v_{2}(n)$ we denote the largest nonnegative integer $r$ such that $2^{r} \mid n$ .
A position $(a, b)$ (i.e. two piles of sizes $a$ and $b$ ) is said to be $k$ -happy if $v_{2}(a)=v_{2}(b)=k$ for some integer $k \geqslant 0$ , and $k$ -unhappy if $\min \left\{v_{2}(a), v_{2}(b)\right\}=k+1$ , then $v_{2}\left(a+\frac{1}{2} b\right)=$ $v_{2}\left(\frac{1}{2} b\right)=k$ .

Hence a $k$ -unhappy position is winning for Alice if $k$ is odd, and drawing if $k$ is even.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.