Problem:
What is the minimum number of successive swaps of adjacent letters in the string ABCDEF that are needed to change the string to FEDCBA ? (For example, 3 swaps are required to change ABC to CBA ; one such sequence of swaps is .)
Answer Choices:
A.
B.
C.
D.
E.
Solution:
If the A is swapped 5 times, once with each of the other letters, the result will be BCDEFA. Now the B can be swapped 4 times in the same way to end up in the fifth position: CDEFBA. Continuing in this way gives a sequence of swaps that achieves the required result.
To see that no sequence of fewer than 15 swaps will work, note that in ABCDEF there are 15 instances of pairs of letters that are in alphabetical order , and in the required final string there are no such pairs. Each swap can decrease the number of pairs of letters that are in alphabetical order by just 1 , so at least swaps are required.
Note: The method described in the problem is called the "bubble sort" algorithm.
The problems on this page are the property of the MAA's American Mathematics Competitions