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

proposed by Spain
Solution

Call a walnut obedient if one of its neighbours is larger than it, an the other one is smaller. We call a process bad if the problem's condition is not satisfied. We want to prove that there are no bad processes.

Lemma 1. The number of obedient walnuts is of the same parity as the number of walnuts.
Proof

We induct on the number of walnuts. If there are three walnuts, the claim is obvious. Suppose the claim is true when we have $n-1$ walnuts $1,2,\ldots, n-1$ for some $n$. Then if we add the walnut labeled with $n$, it can only change the obedience status of its two neighbours, and checking all cases, we can prove that it actually changes the obedience of exactly one of its neighbours.
Indeed, if $u$ and $v$ are the neighbours of $n$ and $u<v$, the number of neighbours of $u$ greater than $u$ stays the same, and the same number for $v$ changes by $1$.
Thus, the lemma is proven.

Lemma 2. In a bad process, for any $j \in \{0,\ldots, 2021\}$, after $j$ moves, the number of obedient walnuts with labels greater than $j$ is odd.
Proof

For $j=0$, the claim is true by Lemma 1. Suppose the claim was true for some $j$. Consider the situation before the $j$-th move. Note that changing the neighbours of $j$ only affects obedience of two walnuts from each side of $j$, and note that $j$ is not obedient since the process is bad.
Let $a, b, j, c, d$ be the mentioned walnuts, in that order. If $b$ or $c$ are less than $j$, then their obedience doesn't matter to us, and the obedience of $a$ and $d$ either doesn't change or doesn't matter to us.
If $b$ and $c$ are greater than $j$, then the obedience of $a$ (or $d$) changes if and only if $a$ (or $d$) is between $b$ and $c$, and the obedience of $b$ (or $c$) changes if and only if $b$ (or $c$) is between $a$ and $d$. Note that the obedience of $a$ (or $d$) doesn't change when $a$ (or $d$) is less than $j$, so the total number of obedience changes equals the number of significant obedience changes.
If there are no numbers between $a$ and $d$, then there are either no obedience changes, or both $a$ and $d$ change their obedience. If there is exactly one number between $a$ and $d$, there is also exactly one number between $b$ and $c$, and the obedience of two numbers changes. If there are two numbers between $a$ and $d$, then the obedience of $a$ and $c$ changes. Therefore, the number of significant obedience changes is even, so the number of obedient numbers greater than $j$ stays odd. Thus, the lemma is proven.

Now, if a process is bad, after $2021$ moves there is an odd number of obedient walnuts greater than $2021$, which is a contradiction. Therefore, bad processes don't exist.

 
 

 
ББ © 2024
Авторски права ББ © 2024