Difference between revisions of "2018 USAJMO Problems/Problem 6"
Nukelauncher (talk | contribs) m |
m (deleted extra comma) |
||
| 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 | + | 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. |
Revision as of 14:25, 21 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
These problems are copyrighted © by the Mathematical Association of America, as part of the 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 | ||
