2021 IMO Problems/Problem 5
Problem
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 -th move, Jumpy swaps the positions of the two walnuts adjacent to walnut
.
Prove that there exists a value of
such that, on the
-th move, Jumpy swaps some walnuts
and
such that
.
Solution
We will start by introducing some notation.
- Let the holes be denoted by
. The index
in
is considered modulo
- Let the nuts be denoted by
and define
when
.
- Let a nut
in hole
be a good nut if the two neighboring nuts
in holes
and
satisfy either
or
. A nut
is a bad nut if it is not good. When good or bad is used for a hole, it refers to the nut in the hole.
- The status of a nut is wether it is good or bad.
- Two adjacent nuts
in holes
and
respectively are an increasing pair if
and a decreasing pair if
.
- Just before the
'th move we denote all nuts
with
to be upcomming nuts.
- During move
,
is the current nut.
The proof works by counting the parity of upcomming bad nuts and hinges on the fact that 2021 is odd.
We start by proving that at any point in time there are an odd number of bad
nuts. Let be the number of bad nuts and
the number of good nuts. A bad
nut is either part of two increasing or two decreasing pairs. Let the number
of increasing bad nuts be
and decreasing bad nuts be
. A good nut
is part of one increasing and one decreasing pair. Let
and
be the
number of increasing and decreasing pairs respectively. Then
since we are double-counting each pair. Therefore must be even, and since
is odd,
must be odd.
If we can prove the existence of a bad current nut, we are done. We show that when a current nut is good, the number of bad upcomming nuts does not change parity after the move. Since there are and odd number of upcomming bad nuts before the first move (every nut is upcomming) and 0 upcomming bad nuts after the last move (there are 0 upcomming nuts), this will show not all current nuts can be good which completes the proof.
We now show that when the current nut is good, the number of bad upcomming nots does not change parity. Consider the 'th move and assume the current
is good and lies in hole
. After the move, the current nut is no longer upcomming, but since it was asummed to be good, this does not contrubute to the number of bad upcomming nuts. The only nuts whose status can possibly change is the nuts in holes
. Since the current nut is good, its two neighbors
in
respectively are either both smaller or larger than
. We tackle the two cases seperately.
Case
In this case neither nor
are upcomming nuts at the time of the move and their status after the move is
irrelevant for the parity of bad upcomming nuts. Consider the nut
in hole
. If
is not upcomming, it is irrelevant. Assume
is upcomming. Then
and thus
. Therefore the nut pair
is decreasing both before and after the move, so
cannot change status. One can make an analogous argument for the nut on
. This completes the proof the the parity of upcomming bad nuts are unchanged in this case.
Case
In this case the nuts are upcomming, so their status matters. Let
be the nut in
. If the status of either of the holes
change, it changes for both of them. This is because the pair
is decreasing both before and after the move, so for a status change to occur it must be the case that it is the pair
which changes direction (which in turn changes the status for both holes). If swapping
and
changes the direction of
, then either
or
is true. In both cases,
, so
is an upcomming nut. Since the nuts in both
and
are upcomming both before and after the move, changing the status of either
or
yields a status change for two upcomming nuts. A completely analogous argument can be made for
.
This shows that if some upcomming nut changes status after the move, then an even number of upcomming nuts change status. This preserves the parity of the number of upcomming bad nuts and completes the proof.