Competition problem — Combinatorics

Library / /19 of 520

Combinatorics Difficulty 4.8 AIME 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, each player chooses a pile with an even number of coins and moves half of the coins of this pile to the other pile. The game ends if a player cannot move, in which case the other player wins.
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.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

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$ .

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

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.