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 "2020 USOJMO Problems/Problem 1"

(Created page with "Let <math>n \geq 2</math> be an integer. Carl has <math>n</math> books arranged on a bookshelf. Each book has a height and a width. No two books have the same height, and no t...")
 
m
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Let <math>n \geq 2</math> be an integer. Carl has <math>n</math> books arranged on a bookshelf.
 
Let <math>n \geq 2</math> be an integer. Carl has <math>n</math> books arranged on a bookshelf.
 
Each book has a height and a width. No two books have the same height, and no two
 
Each book has a height and a width. No two books have the same height, and no two
Line 9: Line 11:
 
of moves, and when he does stop, the books are sorted in increasing order of width
 
of moves, and when he does stop, the books are sorted in increasing order of width
 
from left to right.
 
from left to right.
 +
 +
==Solution==
 +
 +
Without loss of generality, let the books have widths and heights of 1, 2, 3,..., and n. First we will show that Carl can only make finitely many moves.
 +
 +
Note that two books can never be swapped more than once with each other. This is because after a first swap, the wider book will be to the left of the other, so they can never be swapped back. Thus there can be at most <math>{n\choose 2}</math> moves.
 +
 +
Now we will show that the books are in increasing order of width when Carl is done making moves. Assume otherwise for the sake of contradiction. Now let <math>f(k)</math> be the width of the book in the kth spot from the left. Since the books are not in increasing order of width, there must be i such that <math>f(i)>f(i+1)</math>, for <math>1\leq i\leq n-1</math>.
 +
 +
<b>Claim:</b> The ith book must be shorter than the <math>(i+1)</math>th book.
 +
 +
<b>Proof:</b> Assume otherwise for contradiction. Then the ith book must have started to the right of the <math>(i+1)</math>th book, since the ith book is taller. However, the ith book is now to the left of the <math>(i+1)</math>th book, so they must have been swapped at some point. But since <math>f(i)>f(i+1)</math>, the ith book is also wider. But the ith book started to the right, so since it was wider it cannot have been swapped with the <math>(i+1)</math>th book, so we arrive at a contradiction. <math>\blacksquare</math>
 +
 +
From the claim, the ith book must be shorter than the <math>(i+1)</math>th book. But since the ith book is also wider by definition (as <math>f(i)>f(i+1)</math>), Carl can swap those two books, so he still has legal moves and we arrive at a contradiction, so we are done. <math>\blacksquare</math>
 +
 +
~MortemEtInteritum
 +
 +
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=3CfpNOhfHcY
 +
 +
==See Also==
 +
{{USAJMO newbox|year=2020|before=First Problem|num-a=2}}
 +
{{MAA Notice}}

Latest revision as of 18:14, 6 October 2023

Problem

Let $n \geq 2$ be an integer. Carl has $n$ books arranged on a bookshelf. Each book has a height and a width. No two books have the same height, and no two books have the same width. Initially, the books are arranged in increasing order of height from left to right. In a move, Carl picks any two adjacent books where the left book is wider and shorter than the right book, and swaps their locations. Carl does this repeatedly until no further moves are possible. Prove that regardless of how Carl makes his moves, he must stop after a finite number of moves, and when he does stop, the books are sorted in increasing order of width from left to right.

Solution

Without loss of generality, let the books have widths and heights of 1, 2, 3,..., and n. First we will show that Carl can only make finitely many moves.

Note that two books can never be swapped more than once with each other. This is because after a first swap, the wider book will be to the left of the other, so they can never be swapped back. Thus there can be at most ${n\choose 2}$ moves.

Now we will show that the books are in increasing order of width when Carl is done making moves. Assume otherwise for the sake of contradiction. Now let $f(k)$ be the width of the book in the kth spot from the left. Since the books are not in increasing order of width, there must be i such that $f(i)>f(i+1)$, for $1\leq i\leq n-1$.

Claim: The ith book must be shorter than the $(i+1)$th book.

Proof: Assume otherwise for contradiction. Then the ith book must have started to the right of the $(i+1)$th book, since the ith book is taller. However, the ith book is now to the left of the $(i+1)$th book, so they must have been swapped at some point. But since $f(i)>f(i+1)$, the ith book is also wider. But the ith book started to the right, so since it was wider it cannot have been swapped with the $(i+1)$th book, so we arrive at a contradiction. $\blacksquare$

From the claim, the ith book must be shorter than the $(i+1)$th book. But since the ith book is also wider by definition (as $f(i)>f(i+1)$), Carl can swap those two books, so he still has legal moves and we arrive at a contradiction, so we are done. $\blacksquare$

~MortemEtInteritum


Video Solution

https://www.youtube.com/watch?v=3CfpNOhfHcY

See Also

2020 USAJMO (Problems • Resources)
Preceded by
First Problem 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_USOJMO_Problems/Problem_1&oldid=199250"