Alice and Bianca have one hundred marbles. At the start of the game they split these hundred marbles into two piles. Thereafter, a move consists of choosing a pile, then choosing a positive integer not larger than half of the number of marbles in that pile, and finally removing that number of marbles from the chosen pile. The first player unable to remove any marbles loses. Alice makes the first move of the game. Determine all initial pile sizes for which Bianca has a winning strategy.
Problem
Source: Nordic MC 2023 P1
Tags: combinatorics
SerdarBozdag
22.04.2023 17:13
Bianca wins if the pile sizes are $(k, 2^nk+2^n-1)$ for any $k \in Z^+$ and $n \in Z ^{ \ge 0}$.
If Bianca performs a move on $(k, 2^nk+2^n-1)$ then Alice can make a move to get piles $(k, 2^{n-1}k+2^{n-1}-1)$. Moreover if Alice does not start with $(k, 2^nk+2^n-1)$ then he can make a move to get $(k, 2^nk+2^n-1)$. Thus if Alice starts with initial pile size different than $(k, 2^nk+2^n-1)$ then Bianca performes any of her moves onto $(k, 2^nk+2^n-1)$ which guarantees Alice to make a move on her turn and Alice wins.
If Alice starts with $(k, 2^nk+2^n-1)$ then Bianca can do the same to win the game.
Tintarn
29.04.2023 22:32
A slightly more symmetric way to write the solution is to say that $(a,b)$ is a losing position iff $\frac{a+1}{b+1}$ is a power by $2$ (which could be less than $1$). This also makes the proof quite obvious: We always change $a+1$ or $b+1$ by a factor of less than $2$, so from a losing position we must move to a winning position. Conversely, from a winning position we can round off to the nearest power of $2$ to obtain a losing position. For the concrete value of $a+b=100$, the losing positions turn out to be $(50,50), (67,33), (33,67), (95,5)$ and $(5,95)$.