2021 IMO Problems/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 -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 .
https://www.youtube.com/watch?v=vUftJHRaNx8 [Video contains solutions to all day 2 problems]
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.
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.
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.