
1. Alice and Ben play the game on a board with 72 cells around a circle. First, Ben chooses some cells and places one chip on each of them. Each round, Alice first chooses one empty cell and then Ben moves a chip from one of the adjacent cell onto the chosen one. If Ben fails to do so, the game ends; otherwise, another round follows. Determine the smallest number of chips for which Ben can guarantee that the game will last for at least 2023 rounds.

(Václav Blažej)


Solution. 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 36th 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 cell 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 36th round.

Another 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 \geq 2$ markers divide[^6]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 \geq 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 $2 k+1$ cells for which and $2 k+1 \leq 72-3=69$, i.e. $k \leq 34$. In the obvious marking, then, the situation in the $U$ segment looks like this:

$$
\ldots 0|\underbrace{0101 \ldots 010}_{U}| 0 \ldots
$$

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 $2 k-1$ :

$$
\ldots 0|\underbrace{0101 \ldots 010}_{U}| 0 \ldots \rightarrow \ldots 010|\underbrace{0101 \ldots 010}_{U^{\prime}}| 0 \ldots
$$

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 \leq 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.

REMARK. It can be proved that there must be at least two segments of odd length. Alice can then choose the segment $U$ from the previous solution so that it consists of at most 35 cells. In addition, Alice can modify her strategy so that in the segment $U$ she points not to the outside cell but to the middle empty cell, or to one of the cells next to the middle occupied cell. Then, after Ben's move, a new marker will appear in $U$ that splits $U$ into two sections and Alice then selects the shorter of them. Repeating this procedure gives Alice a sequence of sections with number of cells that does not exceed $35,17,7,3$, and 1, respectively, so Alice ends the game no later than in the fifth round.
