What is the minimum number of successive swaps of adjacent letters in the string that are needed to change the string to ? (For example, 3 swaps are required to change to ; one such sequence of swaps is ABC BAC BCA CBA.)
Pick one
Solution
If the is swapped 5 times, once with each of the other letters, the result will be . Now the can be swapped 4 times in the same way to end up in the fifth position: . 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 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 15 swaps are required.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.