Alexandre and Bernado are playing the following game. At the beginning, there are $n$ balls in a bag. At first turn, Alexandre can take one ball from the bag; at second turn, Bernado can take one or two balls from the bag, and so on. So they take turns and in $k$ turn, they can take a number of balls from $1$ to $k$. Wins the one who makes the bag empty. For each value of $n$, find who has the winning strategy.
Problem
Source: 2024 Portuguese MO Day 2 P6
Tags: Game Theory, combinatorics
bin_sherlo
25.03.2024 12:37
Answer: $A$ wins if $n=k^2+\{0,1,...,k-1\}$ and $B$ wins if $n=k^2+\{k,k+1,...,2k\}$ Claim: $A$ wins if $n$ is a perfect square. Proof: Let $n=k^2$ First $A$ writes $1$. After that, if $B$ takes $m$ in the $2i.$ move, then $A$ takes $2i+1-m$ in $(2i+1).$ move. By this algorithm, the bag will have $k^2- (1+3+...+(2i+1))$ balls after $(2i+1).$ move. After $(2k-1).$ move, there won't exist any ball in the bag and the last ball will be taken by $A$. Claim: $A$ wins if $n=k^2+t$ where $0\leq t\leq k-1$. Proof: $A$ does nearly the same strategy. $A$ can guarantee that the sum of the taken balls in moves $(2i)$ and $(2i+1)$ equals to $2i+2$. $A$ changes the sum from $2i+1$ to $2i+2$ for $t$ move pairs and wins. Claim: $B$ wins if $n=k^2+k$ Proof: If $A$ takes $m$ balls in $(2i-1).$ move, then $B$ takes $2i-m$ balls in $(2i).$ move. So after $2k$ moves, there won't exist any ball in the bag because $k^2+k=k(k+1)=(2+4+...+2k)$ Claim: $B$ wins if $n=k^2+t$ where $k\leq t\leq 2k$. Proof: Again $B$ does nearly the same strategy. $B$ can guarantee that the sum of the taken balls in moves $(2i-1)$ and $(2i)$ equals to $2i+1$. $B$ changes $t$ move pairs from $2i$ to $2i+1$ and wins.