During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

2020 USOJMO Problems/Problem 1

Revision as of 20:23, 21 June 2020 by Yoda2187 (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

Invalid username
Login to AoPS