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. Starting Arrangement: H H H T T T Final Arrangement: T T T H H H The minimum number of steps needed to go from the Starting Arrangement to the Final Arrangement, as shown in the figure, is ________.
Show Hint
Each of the 3 heads must move past each of the 3 tails at least once; count how many such crossings are needed in total.
Step 1: Track the target position of each coin type. There are 3 H coins, starting at positions 1, 2 and 3, and 3 T coins, starting at positions 4, 5 and 6. In the Final Arrangement, all 3 T coins must occupy positions 1, 2 and 3, and all 3 H coins must occupy positions 4, 5 and 6.
Step 2: Work out how far each H coin must move past T coins. Take the H coin at position 1: to reach the H-block on the right side of the row, it must move past all 3 T coins that currently sit to its right, since every T coin needs to end up to its left. That is 3 required adjacent swaps for this one H coin. The same reasoning applies to the H coin at position 2 and the H coin at position 3: each of them must also cross past all 3 T coins, since the coins keep their internal order (an H never needs to swap past another H, and a T never needs to swap past another T).
Step 3: Add up the moves for all three H coins. Each of the 3 H coins needs 3 adjacent swaps against T coins, and these swaps never overlap or cancel out. Total swaps: $3 + 3 + 3 = 9$.
Step 4: Confirm this is the minimum, not just one way of doing it. Since every H coin genuinely must end up to the right of every T coin, and an adjacent swap can only fix one H-T pair at a time, no sequence of swaps can do the job in fewer than 9 steps.
