Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 IMO Problems/Problem 5"
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
==Problem==  
+
== 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 <math>k</math>-th move, Jumpy swaps the positions of the two walnuts adjacent to walnut <math>k</math>.
  
−
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>.
 
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>.
  
−
==Video Solution==
+
== Video Solution ==
 
https://youtu.be/vUftJHRaNx8 [Much shorter solution, video contains solutions to all day 2 problems]
 
https://youtu.be/vUftJHRaNx8 [Much shorter solution, video contains solutions to all day 2 problems]
  
−
==Solution==
+
== Solution ==
  
 
We will start by introducing some notation.
 
We will start by introducing some notation.
Line 49: Line 49:
  
 
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.
 +
 +
== See also ==
 +
{{IMO box|year=2021|num-b=4|num-a=6}}
 +
 +
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 09:34, 18 June 2023

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

Video Solution

https://youtu.be/vUftJHRaNx8 [Much shorter solution, video contains solutions to all day 2 problems]

Solution

We will start by introducing some notation.

  • Let the holes be denoted by $H_1, H_2, \dots, H_{2021}$. The index $i$ in $H_i$ is considered modulo $2021$
  • Let the nuts be denoted by $N_1, N_2, \dots, N_{2021}$ and define $N_i < N_j$ when $i < j$.
  • Let a nut $n$ in hole $H_i$ be a good nut if the two neighboring nuts $a, b$ in holes $H_{i-1}$ and $H_{i+1}$ satisfy either $a,b < n$ or $n < a,b$. A nut $n$ 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 $a,b$ in holes $H_i$ and $H_{i+1}$ respectively are an increasing pair if $a < b$ and a decreasing pair if $a > b$.
  • Just before the $k$'th move we denote all nuts $N_i$ with $i\geq k$ to be upcomming nuts.
  • During move $k$, $N_k$ 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 $B$ be the number of bad nuts and $G$ 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 $B_1$ and decreasing bad nuts be $B_2$. A good nut is part of one increasing and one decreasing pair. Let $I$ and $D$ be the number of increasing and decreasing pairs respectively. Then

$2I = G + 2B_1$

$2D = G + 2B_2$

since we are double-counting each pair. Therefore $G$ must be even, and since $2021 = G + B$ is odd, $B$ 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 $k$'th move and assume the current $n$ is good and lies in hole $H_i$. 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 $H_{i-2}, H_{i-1}, H_{i+1}, H_{i+2}$. Since the current nut is good, its two neighbors $a,b$ in $H_{i-1}, H_{i+1}$ respectively are either both smaller or larger than $n$. We tackle the two cases seperately.


Case $a,b < n$

In this case neither $a$ nor $b$ 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 $c$ in hole $H_{i-2}$. If $c$ is not upcomming, it is irrelevant. Assume $c$ is upcomming. Then $c > n$ and thus $c > a,b$. Therefore the nut pair $H_{i-2}, H_{i-1}$ is decreasing both before and after the move, so $c$ cannot change status. One can make an analogous argument for the nut on $H_{i+2}$. This completes the proof the the parity of upcomming bad nuts are unchanged in this case.


Case $a,b > n$

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

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.

See also

2021 IMO (Problems) • Resources
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_IMO_Problems/Problem_5&oldid=194581"