2024 AMC 10A Problems/Problem 6

Problem

What is the minimum number of successive swaps of adjacent letters in the string that are needed to change the string to (For example, swaps are required to change to one such sequence of swaps is )

Solution 1 (Analysis)

Procedurally, it takes:

• swaps for to move to the sixth spot, giving

• swaps for to move to the fifth spot, giving

• swaps for to move to the fourth spot, giving

• swaps for to move to the third spot, giving

• swap for to move to the second spot (so becomes the first spot), giving

Together, the answer is

~MRENTHUSIASM

Solution 2 (Recursive Approach)

We can proceed by a recursive tactic on the number of letters in the string.

Looking at the string , there are moves needed to change it to the string

Then, there is move to change to .

Similarly, there is moves needed for three letters (said in the problem).

There are moves needed to change to .

We see a pattern of . We notice that the difference between consecutive terms is increasing by , so in the same way, for letters, we would need moves, and for , we would need moves.

Thinking why, when we start making these moves, we see that for a string of length , it takes moves to move the last letter to the front. After, we get a string that will be changed identically to a string of length . This works in our pattern above and is another way to think about the problem!

~world123

Note:

The sequence consists of triangular numbers shifted a term up (as it starts with on term and on term .) Thus, our explicit formula is and as in this case ( letters), our answer is ~ NSAoPS

Solution 3 (Solution 2 Done Fast)

We can see that the most efficient way to change to is the same as changing to and then moving to the front in moves. Similarly, this would carry on downwards, where to change to would be to change to and move times to the front. This pattern will carry on until to would be , and to would be . The answer would be , which is moves.

~Moonwatcher22

Solution 4 (If you don't notice anything)

Simply, just blindly doing it, the most straightforward way is to shift F all the way back. From ABCDEF:

ABCDFE -> ABCFDE -> ABFCDE -> AFBCDE -> FABCDE

For E:

FABCED -> FABECD -> FAEBCD -> FEABCD

For D:

FEABDC -> FEADBC -> FEDABC

For C:

FEDACB -> FEDCAB

For B:

FEDCBA

That's it, you don't need to do it with A. Still moves.

~pepper2831

Solution 5 (Inversions of Permutations)

Let the letters correspond to the numbers respectively. We want to find the number of swaps required to transform the permutation into the permutation .

Here, we let be the natural order. Then the total number of inversions of the permutation is . Hence the answer is

~tsun26

Video Solution by Pi Academy

https://youtu.be/6qYaJsgqkbs?si=K2Ebwqg-Ro8Yqoiv

Video Solution 1 by Power Solve

https://youtu.be/j-37jvqzhrg?si=ieBRx0-CUihcKttE&t=616

Video Solution by Daily Dose of Math

https://youtu.be/-EFTk2pBFug

~Thesmartgreekmathdude

Video Solution by SpreadTheMathLove

https://www.youtube.com/watch?v=_o5zagJVe1U

Video Solution by Just Math⚡

https://youtu.be/KrkjGpk1uZs

See also

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