Maths Olympiad Prep

Library / /16 of 26

Combinatorics Difficulty 4.6 AIME Find the answer United States

What is the minimum number of successive swaps of adjacent letters in the string ABCDEFABCDEF that are needed to change the string to FEDCBAFEDCBA? (For example, 3 swaps are required to change ABCABC to CBACBA; one such sequence of swaps is ABC \to BAC \to BCA \to CBA.)

Pick one

Solution

If the AA is swapped 5 times, once with each of the other letters, the result will be BCDEFABCDEFA. Now the BB can be swapped 4 times in the same way to end up in the fifth position: CDEFBACDEFBA. Continuing in this way gives a sequence of 5+4+3+2+1=155 + 4 + 3 + 2 + 1 = 15 swaps that achieves the required result.

To see that no sequence of fewer than 15 swaps will work, note that in ABCDEFABCDEF there are 15 instances of pairs of letters that are in alphabetical order (ABAB, ACAC, ADAD, AEAE, AFAF, BCBC, BDBD, BEBE, BFBF, CDCD, CECE, CFCF, DEDE, DFDF, EFEF), 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.