Difference between revisions of "2018 USAJMO Problems/Problem 6"
m (deleted extra comma) |
(→Solution) |
||
Line 9: | Line 9: | ||
==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}} | {{MAA Notice}} | ||
==See also== | ==See also== | ||
{{USAJMO newbox|year=2018|num-b=5|aftertext=|after=Last Problem}} | {{USAJMO newbox|year=2018|num-b=5|aftertext=|after=Last Problem}} |
Revision as of 19:47, 27 April 2018
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.
Solution
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 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.
See also
2018 USAJMO (Problems • Resources) | ||
Preceded by Problem 5 |
Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |