# Difference between revisions of "2021 IMO Problems/Problem 5"

Almostuseful (talk | contribs) |
Almostuseful (talk | contribs) |
||

Line 1: | Line 1: | ||

+ | <h1> Problem </h1> | ||

+ | 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 <math>k</math>-th move, Jumpy swaps the positions of the two walnuts adjacent to walnut <math>k</math>. | ||

+ | Prove that there exists a value of <math>k</math> such that, on the <math>k</math>-th move, Jumpy swaps some walnuts <math>a</math> and <math>b</math> such that <math>a < k < b</math>. | ||

+ | |||

+ | <h1>Solution</h1> | ||

We will start by introducing some notation. | We will start by introducing some notation. | ||

* Let the holes be denoted by <math>H_1, H_2, \dots, H_{2021}</math>. The index <math>i</math> in <math>H_i</math> is considered modulo <math>2021</math> | * Let the holes be denoted by <math>H_1, H_2, \dots, H_{2021}</math>. The index <math>i</math> in <math>H_i</math> is considered modulo <math>2021</math> | ||

* Let the nuts be denoted by <math>N_1, N_2, \dots, N_{2021}</math> and define <math>N_i < N_j</math> when <math>i < j</math>. | * Let the nuts be denoted by <math>N_1, N_2, \dots, N_{2021}</math> and define <math>N_i < N_j</math> when <math>i < j</math>. | ||

− | * Let a nut <math>n</math> in hole <math>H_i</math> be a good nut if the two neighboring nuts <math>a, b</math> in holes <math>H_{i-1}</math> and <math>H_{i+1}</math> satisfy either <math>a,b < n</math> or <math>n < a,b</math>. A nut <math>n</math> 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. | + | * Let a nut <math>n</math> in hole <math>H_i</math> be a <i>good nut</i> if the two neighboring nuts <math>a, b</math> in holes <math>H_{i-1}</math> and <math>H_{i+1}</math> satisfy either <math>a,b < n</math> or <math>n < a,b</math>. A nut <math>n</math> is a <i>bad nut</i> 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. | + | * The <i>status</i> of a nut is wether it is good or bad. |

− | * Two adjacent nuts <math>a,b</math> in holes <math>H_i</math> and <math>H_{i+1}</math> respectively are an increasing pair if <math>a < b</math> and a decreasing pair if <math>a > b</math>. | + | * Two adjacent nuts <math>a,b</math> in holes <math>H_i</math> and <math>H_{i+1}</math> respectively are an <i>increasing pair</i> if <math>a < b</math> and a <i>decreasing pair</i> if <math>a > b</math>. |

− | * Just before the <math>k</math>'th move we denote all nuts <math>N_i</math> with <math>i\geq k</math> to be upcomming nuts. | + | * Just before the <math>k</math>'th move we denote all nuts <math>N_i</math> with <math>i\geq k</math> to be <i>upcomming nuts</i>. |

− | * During move <math>k</math>, <math>N_k</math> is the current nut. | + | * During move <math>k</math>, <math>N_k</math> is the <i>current nut</i>. |

The proof works by counting the parity of upcomming bad nuts and hinges on the fact that 2021 is odd. | The proof works by counting the parity of upcomming bad nuts and hinges on the fact that 2021 is odd. | ||

Line 28: | Line 33: | ||

− | Case <math>a,b < n</math> | + | <b>Case <math>a,b < n</math></b> |

In this case neither <math>a</math> nor <math>b</math> are upcomming nuts at the time of the move and their status after the move is | In this case neither <math>a</math> nor <math>b</math> are upcomming nuts at the time of the move and their status after the move is | ||

Line 34: | Line 39: | ||

− | Case <math>a,b > n</math> | + | <b>Case <math>a,b > n</math></b> |

In this case the nuts <math>a,b</math> are upcomming, so their status matters. Let <math>c</math> be the nut in <math>H_{i-2}</math>. If the status of either of the holes <math>H_{i-2}, H_{i-1}</math> change, it changes for both of them. This is because the pair <math>H_{i-1}, H_i</math> 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 <math>H_{i-2}, H_{i-1}</math> which changes direction (which in turn changes the status for both holes). If swapping <math>a</math> and <math>b</math> changes the direction of <math>H_{i-2}, H_{i-1}</math>, then either <math>a < c < b</math> or <math>b < c < a</math> is true. In both cases, <math>c > n</math>, so <math>c</math> is an upcomming nut. Since the nuts in both <math>H_{i-1}</math> and <math>H_{i+1}</math> are upcomming both before and after the move, changing the status of either <math>H_{i-2}</math> or <math>H_{i-1}</math> yields a status change for two upcomming nuts. A completely analogous argument can be made for <math>H_{i+1}, H_{i+2}</math>. | In this case the nuts <math>a,b</math> are upcomming, so their status matters. Let <math>c</math> be the nut in <math>H_{i-2}</math>. If the status of either of the holes <math>H_{i-2}, H_{i-1}</math> change, it changes for both of them. This is because the pair <math>H_{i-1}, H_i</math> 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 <math>H_{i-2}, H_{i-1}</math> which changes direction (which in turn changes the status for both holes). If swapping <math>a</math> and <math>b</math> changes the direction of <math>H_{i-2}, H_{i-1}</math>, then either <math>a < c < b</math> or <math>b < c < a</math> is true. In both cases, <math>c > n</math>, so <math>c</math> is an upcomming nut. Since the nuts in both <math>H_{i-1}</math> and <math>H_{i+1}</math> are upcomming both before and after the move, changing the status of either <math>H_{i-2}</math> or <math>H_{i-1}</math> yields a status change for two upcomming nuts. A completely analogous argument can be made for <math>H_{i+1}, H_{i+2}</math>. | ||

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

## Revision as of 10:36, 27 July 2021

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