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$.

Step 1 (Setup): Walnuts $1,2,\dots ,2021$ are placed in 2021 holes on a circle. At step $k$, the two walnuts adjacent to walnut $k$ on the circle are swapped.

Step 2 (Classify each swap): At step $k$, let the neighbors of walnut $k$ be $a$ and $b$. The swap is of type:

• "good" if $a<k<b$ (what we want to find),

• "ascending" if $a,b>k$,

• "descending" if $a,b<k$.

Step 3 (Monovariant approach): Consider the number of inversions in the circular permutation (pairs $i<j$ where $j$ appears before $i$ in clockwise order). Each "ascending" swap changes the inversion count by $\pm 1$, as does each "descending" swap. A "good" swap also changes it by $\pm 1$.

Step 4 (Parity/counting argument): Consider the sum ${\sum }_{k=1}^{2021}f(k)$ where $f(k)=1$ if the swap at step $k$ is "good" and $f(k)=0$ otherwise. If no good swap exists, then every step $k$ has both neighbors on the same side of $k$. But this leads to a contradiction: the permutation structure on a circle requires that as $k$ traverses $1,2,\dots ,2021$, the neighbors must "cross" $k$ at some point, since the walnuts wrap around the circle.

Step 5 (Formal proof): For each $k$, let $L_k$ = number of neighbors of $k$ that are $<k$, and $R_k$ = number that are $>k$. We need $L_k=R_k=1$ for some $k$. Since walnut $k$ has exactly 2 neighbors: $(L_k,R_k)\in \{(0,2),(1,1),(2,0)\}$. We want to exclude $(1,1)$ for all $k$.

But ${\sum }_{k=1}^{2021}{L}_k={\sum }_{k=1}^{2021}{R}_k$ (each adjacency $i<j$ contributes 1 to $L_j$ and 1 to $R_i$). If $(L_k,R_k)\ne (1,1)$ for all $k$, then each $k$ contributes either 0 or 2 to $\sum L_k$. So $\sum L_k$ is even. But $\sum L_k=$ total number of adjacencies $\{i,j\}$ with $i<j$ = total adjacencies = 2021. Contradiction since 2021 is odd.

$■$