2018 USAJMO Problems/Problem 6

Revision as of 02:01, 21 April 2018 by Sujaykazi (talk | contribs) (Created page with "==Problem 6== Karl starts with <math>n</math> cards labeled <math>1,2,3,\dots,n</math> lined up in a random order on his desk. He calls a pair <math>(a,b)</math> of these card...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem 6

Karl starts with $n$ cards labeled $1,2,3,\dots,n$ lined up in a random order on his desk. He calls a pair $(a,b)$ of these cards swapped if $a>b$ and the card labeled $a$ is to the left of the card labeled $b$. For instance, in the sequence of cards $3,1,4,2$, there are three swapped pairs of cards, $(3,1)$, $(3,2)$, and $(4,2)$.

He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had $i$ card to its left, then it now has $i$ cards to its right. He then picks up the card labeled $2$ and reinserts it in the same manner, and so on until he has picked up and put back each of the cards $1,2,\dots,n$ exactly once in that order. (For example, the process starting at $3,1,4,2$ would be $3,1,4,2\to 3,4,1,2\to 2,3,4,1\to 2,4,3,1\to 2,3,4,1$.)

Show that, no matter what lineup of cards Karl started with, his final lineup has the same number of swapped pairs as the starting lineup.


Solution