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
Each of the 3 heads must cross past each of the 3 tails at least once, and each adjacent swap fixes exactly one such crossing.
Step 1: Understanding the Question.
The starting row of six coins is H H H T T T, and the final row is T T T H H H. A step swaps two coins that are sitting next to each other, without flipping either coin. We need the smallest number of such swaps to turn the starting row into the final row.
Step 2: Key Formula or Approach.
Since all three H coins are identical to each other, and all three T coins are identical to each other, the minimum number of adjacent swaps needed equals the number of (H, T) pairs that are in the wrong relative order compared to the target. In the starting row every H sits to the left of every T, but in the final row every T must sit to the left of every H. So every one of the 3 H coins has to cross past every one of the 3 T coins at least once, and each crossing needs exactly one adjacent swap.
Step 3: Detailed Explanation.
Count the number of (H, T) pairs that must swap their relative order. There are 3 H coins (call them \(H_1, H_2, H_3\)) and 3 T coins (\(T_1, T_2, T_3\)). In the starting row, every \(H_i\) is to the left of every \(T_j\). In the final row, every \(T_j\) must be to the left of every \(H_i\). So each of the 3 H coins needs to move past each of the 3 T coins, giving \(3 \times 3 = 9\) required crossings.
Each adjacent swap can fix exactly one such crossing (swapping one H past one T that is immediately next to it), and no single swap can fix two crossings at once. So the minimum number of adjacent swaps needed is exactly 9, no fewer.
This matches the standard result that reversing the relative order of an \(m\)-block and an \(n\)-block using only adjacent swaps takes exactly \(m \times n\) swaps; here \(m = n = 3\), giving \(3 \times 3 = 9\).
Step 4: Final Answer.
The minimum number of steps needed is 9, which is option (C).
\[ \boxed{9} \]
