A coin with heads facing up is shown as (H) and a coin with tails facing up is shown as (T). Six coins are placed in the Starting Arrangement, as shown in the figure below. A “step” is defined as interchanging a pair of adjacent coins without flipping them. The minimum number of steps needed to go from the Starting Arrangement to the Final Arrangement, as shown in the figure, is ________.
Show Hint
Count how many times each H coin must cross an adjacent T coin; the total number of such crossings is the minimum number of steps.
Step 1: Write down the starting and final arrangements. The starting arrangement is H H H T T T (positions 1 through 6), and the final arrangement is T T T H H H.
Step 2: Understand what a single step can achieve. A step swaps two coins sitting next to each other, without flipping either one. Since all H coins are identical to each other and all T coins are identical to each other, the only useful swaps are ones that exchange an H with an adjacent T, since swapping two identical coins changes nothing.
Step 3: Count how far each coin must travel. In the final arrangement, all three T coins must end up to the left of all three H coins. Consider the three H coins in the starting arrangement, sitting at positions 1, 2, and 3, and the three T coins sitting at positions 4, 5, and 6. Every single H coin must cross over every single T coin at least once to reverse their relative order, because right now every H is to the left of every T, and in the final layout every H must be to the right of every T.
Step 4: Multiply out the total number of crossings. There are 3 H coins and 3 T coins, and each of the 3 H coins must individually swap past each of the 3 T coins exactly once. This gives 3 x 3 = 9 required adjacent swaps in total, and no single swap can achieve more than one such crossing.
Conclusion: The minimum number of steps needed is 9, which is option 3.
