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
walnuts
for some
. Then if we add the walnut labeled with
, 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
and
are the neighbours of
and
, the number of neighbours of
greater than
stays the same, and the same number for
changes by
.
Thus, the lemma is proven.
Lemma 2. In a bad process, for any
, after
moves, the number of obedient walnuts with labels greater than
is odd.
Proof
For
, the claim is true by Lemma 1. Suppose the claim was true for some
. Consider the situation before the
-th move. Note that changing the neighbours of
only affects obedience of two walnuts from each side of
, and note that
is not obedient since the process is bad.
Let
be the mentioned walnuts, in that order. If
or
are less than
, then their obedience doesn't matter to us, and the obedience of
and
either doesn't change or doesn't matter to us.
If
and
are greater than
, then the obedience of
(or
) changes if and only if
(or
) is between
and
, and the obedience of
(or
) changes if and only if
(or
) is between
and
. Note that the obedience of
(or
) doesn't change when
(or
) is less than
, so the total number of obedience changes equals the number of significant obedience changes.
If there are no numbers between
and
, then there are either no obedience changes, or both
and
change their obedience. If there is exactly one number between
and
, there is also exactly one number between
and
, and the obedience of two numbers changes. If there are two numbers between
and
, then the obedience of
and
changes. Therefore, the number of significant obedience changes is even, so the number of obedient numbers greater than
stays odd. Thus, the lemma is proven.
Now, if a process is bad, after
moves there is an odd number of obedient walnuts greater than
, which is a contradiction. Therefore, bad processes don't exist.