A thimblerigger has 2021 thimbles numbered from 1 through 2021. The thimbles are arranged in a circle in arbitrary order. The thimblerigger performs a sequence of 2021 moves; in the move, he swaps the positions of the two thimbles adjacent to thimble .
Prove that there exists a value of such that, in the move, the thimblerigger swaps some thimbles and such that .
, 2021
Solution
Assume the contrary. Say that the thimble is the central thimble of the move, and its position on that move is the central position of the move.
Step 1: Black and white colouring.
Before the moves start, let us paint all thimbles in white. Then, after each move, we repaint its central thimble in black. This way, at the end of the process all thimbles have become black.
By our assumption, in every move , the two swapped thimbles have the same colour (as their numbers are either both larger or both smaller than ). At every moment, assign the colours of the thimbles to their current positions; then the only position which changes its colour in a move is its central position. In particular, each position is central for exactly one move (when it is being repainted to black).
Step 2: Red and green colouring.
Now we introduce a colouring of the positions. If in the move, the numbers of the two swapped thimbles are both less than , then we paint the central position of the move in red; otherwise we paint that position in green. This way, each position has been painted in red or green exactly once. We claim that among any two adjacent positions, one becomes green and the other one becomes red; this will provide the desired contradiction since 2021 is odd.
Consider two adjacent positions and , which are central in the and in the moves, respectively, with . Then in the move the thimble at position is white, and therefore has a number greater than . After the move, position is green and the thimble at position is black. By the arguments from Step 1, position contains only black thimbles after the step. Therefore, on the move, position contains a black thimble whose number is therefore less than , while thimble is at position . So position becomes red, and hence and have different colours.