Library / /117 of 120

, 2012

Combinatorics Difficulty 6.8 National olympiad Prove it Saudi Arabia

Let $n \ge 3$ be a positive integer. Suppose we have a circle with $n$ positions labeled $1, 2, \dots, n$ in clockwise order. $n$ counters, each with one side white and the other side black, are placed on the circle with one counter in each of the numbered positions. Initially all counters have the white side facing up, except the counter at position $1$ which shows black. We are allowed to perform the following operation:
(i) Choose a counter $X$ whose black side is facing up, and let $Y, Z$ be the next two counters in clockwise order.
(ii) Flip counter $Y$ so that it is showing the other color.
(iii) Move $X$ two spaces clockwise, and move $Y, Z$ one space counterclockwise. (So after the operation we still have one counter in each position.)
Let $S$ be any nonempty subset of $\{1, 2, \dots, n\}$ . Show that we can perform a finite sequence of moves after which the numbers in $S$ correspond exactly to the positions of the black counters.

Solution

The operation is invertible; its inverse is to take consecutive counters $Y, Z, X$ with $X$ black, move $X$ to the front, and flip $Y$ . We will work with this operation instead, and show that from any initial position with at least one black counter, we can reach the configuration with one black counter on position $1$ .

Let $B$ denote a black counter and $W$ denote a white counter. Suppose we do not have two consecutive counters of the same color anywhere. Take a configuration $BWB$ and perform the move changing it to $BWW$ . Given that we have two consecutive white counters, we can find a configuration $WWB$ and perform the move changing it to $BBW$ . So no matter what we start with, we will be able to obtain two consecutive black counters somewhere.

Now we use our two consecutive black counters to turn everything black. Suppose there is a white counter; by taking the first white counter preceding a run of at least two consecutive black counters we have a configuration of the form $WBB$ . Perform the move to obtain $BBB$ , eliminating this white counter. By repeating this process we change all the counters to black.

It now suffices to show that we can get to just one black counter from this, since we can cyclically shift any moves from this point to ensure it ends up on space $1$ . Given the configuration $BBB$ , two moves will change it to $BWW$ . So we can change the black counters to white in pairs. Repeat this process in a way that keeps all the white counters and black counters consecutive. If $n$ is odd, this gives us one black counter at the end. If $n$ is even, we get two consecutive black counters with the rest white. Then perform three moves on $WBB$ , which changes it to $BWW$ . This completes the proof.

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.