72nd Czech and Slovak Mathematical Olympiad

We show that the smallest possible number of chips is $36$.

In the first part, we describe the strategy of Ben in which he can ensure that the game will never end. At the beginning, Ben places $36$ chips on even cells of the game board and the odd cells he lets empty. Moreover, he firmly divides all $72$ cells into $36$ pairs of adjacent cells. Then, Ben is moving the chips in such a way that each of these pairs of cells contains exactly one chip throughout the whole game: in each round, Alice chooses an empty cell, and Ben then moves the chip from the second cell of the pair. So the game never ends.

In the second part of the solution, we assume that Ben initially places fewer than $36$ chips on the board. We describe Alice's strategy for ensuring that the game ends no later than in the $36$th round.

First, Alice imagines that the cells are colored alternately white and black. In each round, Alice chooses an empty white cell—she always finds one, because there are $36$ white cells, while the chips are fewer. So, Ben will be forced to move a token from one of the black cells to the white cell. Then, each chip will be moved at most once during the course of the game. The game will therefore end no later than in the $36$th round.

---

Alternative solution.

We present a different approach to the second part of the original solution. We again assume that Ben places less than $36$ chips on the board, and, in addition, that no three adjacent cells are empty—otherwise Alice ends the game in the first round by choosing the middle of those three cells. We show that after at most $34$ rounds, Alice can force a situation where three empty adjacent cells exist.

The empty cells are then divided into several continuous sections, each consisting of one or two cells. There are at least two sections consisting of two cells—dividing all $72$ cells into $36$ pairs of adjacent cells, at least one pair remains empty; then we use the second possible pairing and find another empty pair.

Alice places a marker between each two empty adjacent cells and she corrects the position of one marker after each round. At the beginning these $z\ge 2$ markers divide all $72$ cells into $z$ sections. Each of them contains at least $3$ cells, it starts and ends with an empty cell and does not contain two adjacent empty cells. Alice can certainly select from these segments one, let's call it $U$, that has fewer chips than empty cells (since this inequality holds for their total numbers).

Let $k\ge 1$ be such that the selected segment $U$ contains $k+1$ empty cells and at most $k$ chips. However, these chips must be exactly $k$, since any two consecutive empty cells must be separated by a cell with a chip. Thus, the section $U$ consists of $2k+1$ cells for which and $2k+1\le 72-3=69$, i.e. $k\le 34$. In the obvious marking, then, the situation in the $U$ segment looks like this: $$\dots 0\mid \underset{U}{\underbrace{0101\dots 010}}\mid 0\dots$$ Alice chooses the first empty cell from the left in the $U$ segment in the first round. Ben is then forced to move the chip from the right. This makes the left marker move two positions to the right, creating a new $U^{\prime }$ section of length $2k-1$: $$\dots 0\mid \underset{U}{\underbrace{0101\dots 010}}\mid 0\cdots \to \dots 010\mid \underset{U^{\prime }}{\underbrace{0101\dots 010}}\mid 0\dots$$ In the second round, Alice again selects the first cell from the left in the $U^{\prime }$ section. She repeats the procedure over and over again until after the $k$-th round (where, as we know $k\le 34$), she gets the section between two markers consisting of a single cell, i.e. there are three adjacent empty cells. Then she brings the game to an end in the next turn.