Difference between revisions of "2018 USAJMO Problems/Problem 6"

(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...")
 
(Problem 6)
(4 intermediate revisions by 3 users not shown)
Line 4: Line 4:
 
He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had <math>i</math> card to its left, then it now has <math>i</math> cards to its right. He then picks up the card labeled <math>2</math> and reinserts it in the same manner, and so on until he has picked up and put back each of the cards <math>1,2,\dots,n</math> exactly once in that order. (For example, the process starting at <math>3,1,4,2</math> would be <math>3,1,4,2\to 3,4,1,2\to 2,3,4,1\to 2,4,3,1\to 2,3,4,1</math>.)
 
He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had <math>i</math> card to its left, then it now has <math>i</math> cards to its right. He then picks up the card labeled <math>2</math> and reinserts it in the same manner, and so on until he has picked up and put back each of the cards <math>1,2,\dots,n</math> exactly once in that order. (For example, the process starting at <math>3,1,4,2</math> would be <math>3,1,4,2\to 3,4,1,2\to 2,3,4,1\to 2,4,3,1\to 2,3,4,1</math>.)
  
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.
+
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==
  
==Solution==
+
We define a new process <math>P'</math> where, when re-inserting card <math>i</math>, we additionally change its label from <math>i</math> to <math>n+i</math>. For example, an example of <math>P'</math> also starting with <math>3142</math> is: <cmath> 3142 \longrightarrow 3452 \longrightarrow 6345 \longrightarrow 6475 \longrightarrow 6785. </cmath>Note that now, each step of <math>P'</math> preserves the number of inversions. Moreover, the final configuration of <math>P'</math> is the same as the final configuration of <math>P</math> with all cards incremented by <math>n</math>, and of course thus has the same number of inversions.
 +
 
 +
~ v_enhance
 +
 
 +
{{MAA Notice}}
 +
 
 +
==See also==
 +
{{USAJMO newbox|year=2018|num-b=5|aftertext=|after=Last Problem}}

Revision as of 20:25, 14 March 2019

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