The official solution is really tricky (I did not solve this and I personally think it's way too hard for JMO).

how? do? you? think of that??? Some person had some weird solutions with cyclic shifts, idk. Is there any way to do this with induction?

Th3Numb3rThr33 wrote: how? do? you? think of that??? ^^ More specific: I was thinking in that direction but my version didn't lead anywhere

Who thought of this...

um... wow

v_Enhance wrote: Note that now, each step of $P'$ preserves the number of inversions. How do you know that?

Th3Numb3rThr33 wrote: how? do? you? think of that??? Some person had some weird solutions with cyclic shifts, idk. Is there any way to do this with induction? Idk, I tried induction but it didn't really work because the swapping changes dramatically when you increment the length of the permutation

It seems to be true that the order in which the cards are taken do not matter, so we should be able to produce an algorithm that involves "switching" the order of two cards being removed; however I was not able to prove this during the competition.

how are you supposed to get that official solution?!?!

divine inspiration

alternatively, bribery EDITOR'S NOTE: I do not condone bribery or graft in any manner. I'm just saying though...

Yea, if you got a lot of money and not a lot of brains, that's what you should do.

kootrapali wrote: Yea, if you got a lot of money and not a lot of brains, that's what you should do. You should, but I don't condone it, so you can't legally do anything about it.

Is there another way to do this problem that does not involve bribery?

pandadude wrote: Is there another way to do this problem that does not involve bribery? No the intended solution was bribing Evan... This is joke pls dont kill me

Well... I did something like induction. I used a $v$ notation which went like "$v_r$ is the number of times in which card $r$ is the $b$ in the $swapped$ pair definition", and then a grand $v$ for the sum of the $v_r$ for a certain case. Then I laid the base case out, which is pretty simple (for $n$ equals 1, 2) and eventually went up to the next case. I think I showed that the grand $v_{n+1}$ before the swap minus the grand $v_{n+1}$ after the swap was equal to the difference between the $v_{n+1}$, and somewhere in there I threw in ceiling/floor functions, as well as the assumed step for $v_n$. It took ~1.3 hours. Meanwhile I thought #4 was far harder! Cheers. Honestly it looked like a physics problem to me with the "after-before" = "change in" notation in my proof. I sure do hope it is valid,

such a genius how???

Ok... let me clarify. I suck at notation-rich stuff, especially complicated sentences with 45 variables. So I am forced to look for simplicity and elegance. I tend to have good instinct and an eye for harmony... I basically spend 5 hours on any textbook page with lots of variables or notations (not an exaggeration). Wouldn't call it genius because honestly, these problems practically call for some lucky guess or trying lots of things. In my official solution I said "either recursion or induction", and recursion didn't look promising (you can see that I am a tyro at writing proofs) so I used induction. Luckily, the signs were correct (i.e. I didn't get the result was the negative of the result).

+1 for the title.

I think USAMO problem 6 would work better...

yes please

@sujaykazi: The card moved in each step will be the one with the lowest label. Immediately after being moved, it will be the card with the highest label. The only inversions that can change as this card moves are those involving said card. Before the move, the number of inversions involving the card will be exactly the number of cards to the left of it in line (one inversion involving each). Likewise, the number of inversions will after the move be equal to the number of cards to the right of it in the line. By the definition of the process these two numbers are equal, and thus the number of inversions remains constant with each move.

A pretty cool solution from my friend rah4927. It's similar mathematically to the official solution, though it's a lot more general. We define inversions to be pairs which have different orders in two permutations $P$ and $Q$. Note that what the problem refers to as a swapping is an inversion to a permutation $P$ with $ (1, 2, \dots, n ) $. Now, what we do is apply the same transformation to both $P$ and $N = (1, 2, \dots, n ) $. So after we move $1$, we obtain a new permutation $P_1$ and $N_1 = (2, 3, \dots, n, 1)$. The order of all pairs with $1$ switch for $N_1$, and the number of inversions of $1$ flips in $P_1$. These two effects cancel out, and we find that the number of inversions between $N, P$ and $N_1, P_1$ is the same. Note that the argument here is similar to the one used in the official solution. So we apply this transform similarly for $2, 3$ and so on. So in the end we arrive at some $P_n$, which should have the same number of inversions with $N$ as $P$. And so we are done! When I asked him how he came up with this, he said that he looked at the cycles which are formed with these transforms. These cycles take the form of some blocks of size n each. We know the first permutation in each block should have the same number of swaps. But the pattern does not continue for the rest of the block - why? He thought about it, and realized that the problem wasn't about > or < order, but instead order relative to some other permutation. Which is pretty cool.

awe-sum wrote: This problem was actually quite easy conceptually after I used invariants--just scary to write because who knows what the graders wont accept oops For any card, let its charge be how many units to the left it will move if Karl moves it right now. So in {3,1,4,2}, 4 would have a charge of +1 and 3 would have a charge of -3. Let the net charge of a position be the sum of the charges of all the cards Karl hasn't moved; we can show that adding this to the number of swapped pairs produces an invariant. Since beginning net charge is 0 as all cards can move and ending net charge is 0 as no cards can move this just means that the number of swapped pairs is the same. After this it's just rigorous proofwriting (5 pages and 2 lemmas ). wait how do you know that the number of swapped pairs is the same if the total net change of posiitons is 0?

What a beautiful problem! Th3Numb3rThr33 wrote: 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. Define subtraction of a permutation string by an integer as follows: Suppose we have a permutation string $\sigma$ with $n$ numbers. Then $\sigma-k$ would involve subtracting each digit by $k$ modulo $n.$ For instance, $(14523)-3=(31245).$ Let $\delta$ denote the number of inversions (swapped pairs) in a string. The key claim is the following: Claim: In a process, let $\sigma_i$ denote the $i$th string with $0 \le i \le n.$ Then $\delta(\sigma_i-i)$ is fixed throughout. Notice that this implies $\delta(\sigma_0)=\delta(\sigma_n-n),$ and since $\sigma_n-n=\sigma_n,$ hence $\delta(\sigma_0)=\delta(\sigma_n)$ as desired. To show this, we prove the following lemma: Lemma: For a permutation string $\sigma,$ consider $\sigma^\ast$ to be string which is the same as $\sigma$ except for $n$ is reflected about the midpoint (just as in the process). Then $\delta(\sigma)=\delta((\sigma-1)^\ast).$ For instance, if $\sigma=21435,$ then $\sigma-1=15324$ and $(\sigma-1)^\ast=13254.$ Also, $\delta(21435)=2=\delta(13254).$ Proof: The proof is simple. Let $1$ have $i$ digits on its left and $j$ on its right in $\sigma.$ Then in $\sigma-1,$ the relative order of all digits stays the same since they are subtracted by $1.$ For $1 \to n$ in $\sigma,$ $1$ contributed to $i$ inversions. Now in $\sigma-1,$ $n$ contributes to $j$ inversions. On reflecting it, again it contributes to $i$ inversions, so done. $\square$ Now, in our process, notice that $\sigma_{i+1}-(i+1)=((\sigma_{i}-i)-1)^\ast.$ Then the lemma applies. Hence, we are done. For instance, in the example process, the list for $\sigma_i-i$ is $$3142 \to 2341 \to 4123 \to 2431 \to 2341$$The following form of writing explains the lemma better: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; usepackage("amsmath"); size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -7.116410934570116, xmax = 2.772809359819516, ymin = -5.133963842923042, ymax = 1.2677082297759459; /* image dimensions */ /* draw figures */ label("$3142$",(-6.364378973019575,0.5062758687060223),SE*labelscalefactor); draw((-6,0)--(-6,-1), linewidth(0.7),EndArrow(6)); draw((-6,-1)--(-5,-1), linewidth(0.7),EndArrow(6)); draw((-5,-1)--(-5,-2), linewidth(0.7),EndArrow(6)); draw((-5,-2)--(-4,-2), linewidth(0.7),EndArrow(6)); draw((-4,-2)--(-4,-3), linewidth(0.7),EndArrow(6)); draw((-4,-3)--(-3,-3), linewidth(0.7),EndArrow(6)); draw((-3,-3)--(-3,-4), linewidth(0.7),EndArrow(6)); draw((-3,-4)--(-2,-4), linewidth(0.7),EndArrow(6)); draw((-6,0)--(-5,-1), linewidth(0.7),EndArrow(6)); draw((-5,-1)--(-4,-2), linewidth(0.7),EndArrow(6)); draw((-4,-2)--(-3,-3), linewidth(0.7),EndArrow(6)); draw((-3,-3)--(-2,-4), linewidth(1),EndArrow(6)); label("$-1$",(-6.458382968213392,-0.273957291402665),SE*labelscalefactor); label("$2431$",(-6.279775377345138,-1.1669952457439337),SE*labelscalefactor); label("$2341$",(-4.869715449437871,-0.8003796644880443),SE*labelscalefactor); label("$1234$",(-5.198729432616234,-2.135236396240256),SE*labelscalefactor); label("$4123$",(-3.8826734999027845,-1.8344236116200394),SE*labelscalefactor); label("$3142$",(-2.811027954693262,-2.859067159232653),SE*labelscalefactor); label("$2341$",(-1.8521872037163203,-3.987115101558466),SE*labelscalefactor); label("$3412$",(-4.324492277313729,-3.178680742891633),SE*labelscalefactor); label("$2431$",(-3.3656515263367868,-4.128121094349193),SE*labelscalefactor); label("$-1$",(-5.330335025887579,-1.3644036356509508),SE*labelscalefactor); label("$-1$",(-4.324492277313729,-2.4078479823023278),SE*labelscalefactor); label("$-1$",(-3.309249129220496,-3.385489532318032),SE*labelscalefactor); label("$\delta \text{ same}$",(-5.518343016275214,-0.067148501976266),SE*labelscalefactor); label("$\delta \text{ same}$",(-4.456097870585073,-1.1857960447826972),SE*labelscalefactor); label("$\delta \text{ same}$",(-3.48785672008875,-2.144636795759638),SE*labelscalefactor); label("$\delta \text{ same}$",(-2.3974103758404635,-3.197481541930397),SE*labelscalefactor); /* dots and labels */ dot((-6,0),linewidth(4pt) + dotstyle); dot((-6,-1),linewidth(4pt) + dotstyle); dot((-5,-1),linewidth(4pt) + dotstyle); dot((-5,-2),linewidth(4pt) + dotstyle); dot((-4,-2),linewidth(4pt) + dotstyle); dot((-4,-3),linewidth(4pt) + dotstyle); dot((-3,-3),linewidth(4pt) + dotstyle); dot((-3,-4),linewidth(4pt) + dotstyle); dot((-2,-4),linewidth(4pt) + dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Motivation: This problem was kind of inviting for an invariant type thing, so I tried to relate the give sequences to many other sequences. I'll admit I took a hint here, which was basically relate it to another sequences by changing the labels somehow in which the inversion stayed fixed throughout. Eventually, after trying to match the elements from this process to other strings with the same number of inversions (that we care about), I discovered that subtraction by a particular number would always lead to a string with the same number of inversions, so I had some progress. After some examples I found that we had to subtract $1$ each time from $\sigma_1$ and $0/2$ from $\sigma_2.$ So I actually guessed that we have to subtract $i$ from $\sigma_i,$ and it worked! The staircase lead to an easy visualisation of why this was true and made it easy for me to prove the claims.

Th3Numb3rThr33 wrote: 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. Ok, bear me. I am Combi oriented participant and in no way I am excellent as such in Combi, but hear me out how I got this answer (I first checked all solutions and people reacting to the solution wasn't quite well received in the manner that, the process seemed too ingenious to be in USAJMO) What we do is do this algorithm : Pick up $i$ at place $P_i$ and puts it to $P_{n-i+1}$ In this process, we add $n$ to $i$ Why did I do this? I first tried an approach of valuing the $k^{th}$ digit $2^kt$ where $t$ is $k^{th}$ digit and then afterwards tried cyclic shifts, but then I stumbled upon this soon as I observe that this maintains the number of inversions. I'll add this proof later tomorrow, as I have to add solution to $6$ Geos and this is a bad one to LaTeX. Observe that incrementing $n$ preserves inversion and our algorithm preserves inversion throughout every steps which proves our desired problem. Sorry for not adding the prood of preserving inversion I promise I'll add soon.

Zero Marx

mira74 wrote: v_Enhance wrote: Note that now, each step of $P'$ preserves the number of inversions. How do you know that?

@above $P'$ preserves number of swapping pairs because before $x \rightarrow x+n$ only swapping pairs are $(i,x)$ where $i$'s are the numbers left to $x$ (x is the smallest) and after $x \rightarrow x+n$ the only swapping pairs are $(x+n,i)$ where $i$'s are the numbers right to the $x+n$ (x+n is the largest). Also $($numbers left to $x)=($right to the $x+n$$)$ because of the symmetry condition.

I know the writeup below is most likely incomprehensible, but too bad lol cope also this problem is basically just a tricky variant of 2021 IMO/5; both problems are about size comparisons and performing operations on each number from least to greatest. First, some definitions: Call a number changed/unchanged if Karl has done the reversing operation thing on it. Consider a number to be "shuffled around" when it is not the number being reversed, but one of the numbers whose position gets switched as a consequence. For example, if we go from 12345 to 13425, then, 3 and 4 got shuffled in that operation. Denote the "position" of a number to be $(\text{index from left}) - \frac{n+1}{2}$ if the number is unchanged, and $\frac{n+1}{2} - (\text{index from left})$ if the number is changed. Thus, the sum of the positions of all the numbers at the start and end of Karl's process is $0$. When Karl reverses a number, it does not change the number's position. When an unchanged number gets shuffled left one index, this means that a number less than it has just been reversed, going from the left of that unchanged number to the right; this adds one inversion. So, an unchanged number getting shuffled left corresponds with one inversion being added - similarly, an unchanged number getting shuffled right one index corresponds with one inversion being removed. Oppositely, a changed number getting shuffled left one index corresponds with one inversion being removed, and a changed number getting shuffled right one index corresponds with one inversion being added. This can all be summarized by one rule: increasing the position of a number by $1$ decreases the number of inversions by $1$, and decreasing the position of a number by $1$ increases the number of inversions by $1$. But since the sum of the positions of all numbers starts and ends at $0$, the total number of inversions added must total out to be $0$ as well. (I hope this solution is not a fakesolve. If it's indeed not a fakesolve, then I hope this solution is much more motivated than the solution provided by Evan Chen - this solution comes from trying to relate the position of numbers to the number of inversions, since the former is clearly invariant.)

Consider the modified process in which, when the number $k$ is moved, it changes to $n+k$. Then note that the final permutation is the same as in the original process, but with $n$ added to each number, and the number of inversions is preserved. Thus the original ending permutation has the same number of inversions as the original starting permutation, as desired. Remark: The modified process is motivated by the popular generating functions technique of tagging, in which modified elements are given a tag of some sort, so that we can only compare the tagged elements. In this case, our tags are just adding a constant, because that is the simplest way to preserve inversions among tagged elements. We use $n$ as our constant since that is the smallest constant for which this process works.

On the first turn, consider adding $n$ to $1$ when it is inserted in the deck. Now, the number of swapped pairs does not change since the $i$ cards to the left of $1$ before the insertion contribute to $i$ swapped pairs, which are deleted and replaced by the $i$ pairs caused by the $i$ cards to the right of $n + 1$. Now, subtract $1$ from all cards and repeat the process for a total of $n$ times. Notice the number of swapped pairs is invariant throughout. If the value of some initial card is $k$, then its final value is $k + n - (1 \cdot n)$ since we subtract $1$ $n$ times, giving us our desired final lineup, so we are done.

Done with hints, still agree it's more motivated We instead consider all cards to be initially white, becoming black when operated on. For instance, in the problem given, this becomes \[ WWWW \longrightarrow WWBW \longrightarrow BWWB \longrightarrow BWBB \longrightarrow BBBB \]We claim then that the change in the number of inversions is the difference between the number of pairs $WB$ with a $W$ card preceeding a $B$ card by some number of cards, subtracting the pairs $BW$. Then we can pair up the cards before and after the swapped card that aren't affected, as \[ WWW \mapsto WBW, WWB \mapsto WBB, BWW \mapsto BBW, BWB \mapsto BBB \]doesn't change the difference. Conversely, $WB \mapsto BB, WW \mapsto WB$ when moving a card on the left hand of the deck change the difference and number of inversions equally, and likewise. Since the difference is zero for all white and all black cards, the result follows. Remark: This also turns into the idea where you consider the sum of the positions of the moved cards, where adjacent positions differ by two and the signs are symmetric about the middle. Then the position invariant comes into play because you just flip a sign.

Color all the cards white initially, then switch the color to black after the card is moved. Observe the change in the number of swapped pairs each swap is the number of white cards to the left of a black card just after its swap minus the number of black cards on the right of the same black card that was white right before its swap. Observe that if we sum the number of black cards to the right of each white card over all white cards as this process is iterated, we count each white card to the left of each black card exactly once. To prove this, choose a certain card that is black right after a swap. For each white card to its left, it will stay to its left until it is swapped. Therefore, as we sum each white card before it is swapped, every white card to its left will count this black card to its right exactly once in our sum. The counting of the other white cards does not affect this black card as they are either \begin{itemize} \item To its right \item Or having been swapped to a black card before our card turned black, and thus were not considered in the swap. \end{itemize} Therefore, summing all the differences simply yields a change of $0,$ so we are done.