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...") |
|||
| 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 | ||
Revision as of 17:05, 23 June 2020
Problem
Let 
be an integer. Carl has 
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.
