Alice and Bob are playing a game on a plane consisting of $72$ cells arranged in circle. At the beginning of the game, Bob places a stone on some of the cells. Then, in every round first Alice picks one empty cell and then Bob must move a stone from one of the two neighboring cells on this cell. If he is unable to do that, game ends. Determine the smallest number of stones he has to place in the beginning so he has a strategy to make the game last for at least $2023$ rounds.
Problem
Source: czechoslovak national mo round
Tags: combinatorics
Ritwin
29.03.2024 04:20
Replace the stones on cells with dumplings on plates.
The smallest possible is $n = 36$.
Bob's strategy for $\color{blue}n = 36$. Bob will start by placing a dumpling on every other plate. Then, he will partition the circle into $36$ groups of $2$ plates; whenever Alice points to an empty plate in some group, Bob will swap the two plates in that group. This game can continue indefinitely, so Bob will prevail after $2023$ rounds.
Alice's strategy for $\color{blue}n < 36$. Describe the circle by a bitstring, with $\texttt{0}$ meaning empty and $\texttt{1}$ meaning full (with a dumpling). If $\texttt{001}$ or $\texttt{100}$ appears anywhere, and Alice picks the middle plate for some turn, call this a forcing move, since Bob will be forced to move the dumpling from the $\texttt{1}$ to the middle plate.
Now consider the gaps between consecutive filled plates (where the gap size is defined as the number of empty plates in between). If any gap has size at least $3$ at any time, Alice can pick the middle and win. So, we may assume all gaps have size at most $2$.
Call a gap large if it has size $2$, small if it has size $1$, and zero if it has size $0$.
Claim: When $n < 36$, there must be two large gaps with only small gaps in between.
Proof. When $n \leq 35$ there are at least two more empty than filled plates, so there are certainly at least two large gaps. Let $c_2$, $c_1$, and $c_0$ be the number of gaps of the respective sizes. Notice that $n = c_0+c_1+c_2$ and $72-n = c_1+2c_2$, so \[ c_2-c_0 = (72-n)-n > 0 \]means it is impossible for every consecutive pair of large gaps to have a zero gap somewhere in between. $\square$
Claim: If there are two consecutive large gaps with only small gaps in between, then Alice can win.
Proof. Let $d$ be the number of small gaps in between. Alice can use a forcing move on one of the large gaps to decrease $d$ by $1$. Repeating this until $d = 0$ will result in a gap of length $3$, at which point Alice will win. $\square$
This strategy uses less than $72$ moves. Hence Alice wins for all $n \leq 35$. $\blacksquare$
If $72$ is replaced by a general $m$, then by similar methods we can show that the smallest possible is $n_B = \bigl\lceil \tfrac m2 \bigr\rceil$, and that if $n < n_B$, then Alice can win in at most $\bigl\lfloor \tfrac{m+2}{4} \bigr\rfloor$ when $m$ is even, and $\tfrac{m-1}{2}$ when $m$ is odd.