2018 USAJMO Problems/Problem 6

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

We define a new process $P'$ where, when re-inserting card $i$, we additionally change its label from $i$ to $n+i$. For example, an example of $P'$ also starting with $3142$ is: \[3142 \longrightarrow 3452 \longrightarrow 6345 \longrightarrow 6475 \longrightarrow 6785.\]Note that now, each step of $P'$ preserves the number of inversions. Moreover, the final configuration of $P'$ is the same as the final configuration of $P$ with all cards incremented by $n$, and of course thus has the same number of inversions.

~ v_enhance

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

See also

2018 USAJMO (ProblemsResources)
Preceded by
Problem 5
Last Problem
1 2 3 4 5 6
All USAJMO Problems and Solutions
Invalid username
Login to AoPS