Maths Olympiad Prep

Library / /117 of 383

, 2021

Combinatorics Difficulty 8.3 Shortlist Prove it IMO

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 kthk^{\text{th}} move, he swaps the positions of the two thimbles adjacent to thimble kk.
Prove that there exists a value of kk such that, in the kthk^{\text{th}} move, the thimblerigger swaps some thimbles aa and bb such that a<k<ba < k < b.

Solution

Assume the contrary. Say that the kthk^{\text{th}} thimble is the central thimble of the kthk^{\text{th}} 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 kk, the two swapped thimbles have the same colour (as their numbers are either both larger or both smaller than kk). 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 kthk^{\text{th}} move, the numbers of the two swapped thimbles are both less than kk, 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 AA and BB, which are central in the atha^{\text{th}} and in the bthb^{\text{th}} moves, respectively, with a<ba < b. Then in the atha^{\text{th}} move the thimble at position BB is white, and therefore has a number greater than aa. After the atha^{\text{th}} move, position AA is green and the thimble at position AA is black. By the arguments from Step 1, position AA contains only black thimbles after the atha^{\text{th}} step. Therefore, on the bthb^{\text{th}} move, position AA contains a black thimble whose number is therefore less than bb, while thimble bb is at position BB. So position BB becomes red, and hence AA and BB have different colours.

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.