2018 USAJMO Problems/Problem 6
Karl starts with cards labeled lined up in a random order on his desk. He calls a pair of these cards swapped if and the card labeled is to the left of the card labeled . For instance, in the sequence of cards , there are three swapped pairs of cards, , , and .
He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had card to its left, then it now has cards to its right. He then picks up the card labeled and reinserts it in the same manner, and so on until he has picked up and put back each of the cards exactly once in that order. (For example, the process starting at would be .)
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.
Note that in this solution, the term "inversions" is used synonymously with "swapped pairs."
We define a new process where, when re-inserting card , we additionally change its label from to . For example, an example of also starting with is: Note that now, each step of preserves the number of inversions. Moreover, the final configuration of is the same as the final configuration of with all cards incremented by , and thus, of course, has the same number of inversions.
~ v_enhance (clarified by integralarefun)
|2018 USAJMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|