IMO 2021 · Problem 5

Two squirrels, Bushy and Jumpy, have collected 2021 walnuts for the winter. Jumpy numbers the walnuts from 1 through 2021, and digs 2021 little holes in a circular pattern in the ground around their favourite tree. The next morning Jumpy notices that Bushy had placed one walnut into each hole, but had paid no attention to the numbering. Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of 2021 moves. In the \(k\)-th move, Jumpy swaps the positions of the two walnuts adjacent to walnut \(k\).

Prove that there exists a value of \(k\) such that, on the \(k\)-th move, Jumpy swaps some walnuts \(a\) and \(b\) such that \(a<k<b\).

Official text of the problem. Official problem paper (PDF)

Solution

Suppose, for a contradiction, that no such move exists. Thus, immediately before each move \(k\), the two neighbours of walnut \(k\) either both have numbers smaller than \(k\), or both have numbers greater than \(k\).

Initially colour all walnuts white. After each move \(k\), recolour walnut \(k\) black. Consequently, immediately before move \(k\), precisely the walnuts numbered \(1,\ldots,k-1\) are black.

Let \(D\) denote the number of pairs of adjacent holes containing walnuts of different colours. Initially \(D=0\), and after all 2021 moves and recolourings, \(D=0\) again, since all walnuts are then black.

Consider move \(k\) together with its subsequent recolouring. By our assumption, the two walnuts being swapped have the same colour. Their exchange therefore leaves the colour in every hole unchanged, so it does not change \(D\). Walnut \(k\), which is still white, is then recoloured black. There are two cases:

  • If its two neighbours are white, the two adjacent pairs involving walnut \(k\) both change from having equal colours to having different colours. Thus \(D\) increases by \(2\).
  • If its two neighbours are black, those two pairs both change from having different colours to having equal colours. Thus \(D\) decreases by \(2\).

All other adjacent pairs remain unchanged. Hence each of the 2021 moves and recolourings changes \(D\) by exactly \(+2\) or \(-2\).

Since \(D\) starts and ends at zero, the number of increases must equal the number of decreases. The total number of moves must therefore be even, contradicting the fact that it is 2021.

Thus some move \(k\) swaps a walnut numbered below \(k\) with one numbered above \(k\), as required. \(\square\)

The solution was checked against the official IMO shortlist solutions.