Competition problem — Combinatorics

Library / /24 of 34

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it United States

The Bank of Pittsburgh issues coins that have a heads side and a tails side. Vera has a row of $2023$ such coins alternately tails-up and heads-up, with the leftmost coin tails-up.

In a move, Vera may flip over one of the coins in the row, subject to the following rules:

* On the first move, Vera may flip over any of the $2023$ coins.
* On all subsequent moves, Vera may only flip over a coin adjacent to the coin she flipped on the previous move. (We do not consider a coin to be adjacent to itself.)

Determine the smallest possible number of moves Vera can make to reach a state in which every coin is heads-up.

Solution

The answer is $\boxed{4044}$ . In general, replacing $2023$ with $4n + 3$ , the answer is $8n + 4$ .

Bound

Observe that the first and last coins must be flipped, and so every coin is flipped at least once. Then, the $2n + 1$ even-indexed coins must be flipped at least twice, so they are flipped at least $4n + 2$ times.

The $2n + 2$ odd-indexed coins must then be flipped at least $4n + 1$ times. Since there are an even number of these coins, the total flip count must be even, so they are actually flipped a total of at least $4n + 2$ times, for a total of at least $8n + 4$ flips in all.

Construction

For $k = 0, 1, \dots, n-1$ , flip $(4k+1, 4k+2, 4k+3, 4k+2, 4k+3, 4k+4, 4k+3, 4k+4)$ in that order; then at the end, flip $4n+1, 4n+2, 4n+3, 4n+2$ . This is illustrated below for $4n + 3 = 15$ .

It is easy to check this works, and there are $4044$ flips, as desired.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.