Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m
(→‎Solution: clarification)
 
(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==
 +
Note that in this solution, the term "inversions" is used synonymously with "swapped pairs."
  
−
==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 thus, of course, has the same number of inversions.
  
 +
~ v_enhance (clarified by integralarefun)
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 17:30, 7 April 2023

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

Note that in this solution, the term "inversions" is used synonymously with "swapped pairs."

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 thus, of course, has the same number of inversions.

~ v_enhance (clarified by integralarefun)

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

See also

2018 USAJMO (Problems • Resources)
Preceded by
Problem 5 		Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_USAJMO_Problems/Problem_6&oldid=191887"