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

with

a<k<b

Step 2 of 5: Colour walnuts red as they are processed

Previous step Next step

In plain words

Recording which walnuts have already been "used" as a colour turns the swapping process into a purely combinatorial colouring problem.

\text{colour walnut } k \text{ red right after move } k

Detailed analysis

Right after move $k$ is performed, colour walnut $k$ red; all other walnuts keep their previous colour (initially all black). By the assumption of the first step, the walnut that turns red at move $k$ always has two same-coloured neighbours at that moment — both black, or both already red — never one of each.