Maths Olympiad Prep

Library / /10 of 12

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Czech Republic

Alice and Ben play the game on a board with 7272 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 cells 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 20232023 rounds.
(Václav Blažej)

Solutions — 2

Solution 1

We show that the smallest possible number of chips is 3636.

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 3636 chips on even cells of the game board and the odd cells he lets empty. Moreover, he firmly divides all 7272 cells into 3636 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 3636 chips on the board. We describe Alice's strategy for ensuring that the game ends no later than in the 3636th 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 3636 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 3636th round.

Solution 2

We present a different approach to the second part of the original solution. We again assume that Ben places less than 3636 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 3434 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 7272 cells into 3636 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 z2z \ge 2 markers divide all 7272 cells into zz sections. Each of them contains at least 33 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 UU, that has fewer chips than empty cells (since this inequality holds for their total numbers).

Let k1k \ge 1 be such that the selected segment UU contains k+1k+1 empty cells and at most kk chips. However, these chips must be exactly kk, since any two consecutive empty cells must be separated by a cell with a chip. Thus, the section UU consists of 2k+12k+1 cells for which and 2k+1723=692k+1 \le 72-3=69, i.e. k34k \le 34. In the obvious marking, then, the situation in the UU segment looks like this:
00101010U0 \dots 0 \mid \underbrace{0101\dots010}_{U} \mid 0\dots
Alice chooses the first empty cell from the left in the UU 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 UU' section of length 2k12k-1:
00101010U00100101010U0 \dots 0 \mid \underbrace{0101\dots010}_{U} \mid 0\dots \rightarrow \dots 010 \mid \underbrace{0101\dots010}_{U'} \mid 0\dots
In the second round, Alice again selects the first cell from the left in the UU' section. She repeats the procedure over and over again until after the kk-th round (where, as we know k34k \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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.