2021 IMO #C3 (#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 favorite 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$.

We will prove this by contradiction.

At each $k$th iteration, we will swap and then color the nut in the middle ($k$ itself). Alongside, we will keep track of the number of pairs of adjacent colored nuts. 

 So, we must always swap either both colored or both uncolored walnuts.  This gives us either $2$ or $0$ new pairs of colored adjacent walnuts, respectively. So, the parity of pairs of colored adjacent walnuts never changes. However, we start at $0$ pairs of colored adjacent walnuts, and end up with $2021$ pairs, 
which means that parity must change at least once, which is a contradiction. 

So, $a<k<b$ must hold for some $k$. $\square$


Popular posts from this blog

1995 IMO #2

2014 IMO SL #C2

2015 IMO SL #A1