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: Understand what one step can fix. A step swaps two coins that are sitting next to each other, without flipping either one. A useful step always swaps a coin that is out of place with its neighbour, moving it one place closer to where it needs to end up.
Step 2: Compare the two arrangements. Starting Arrangement: H H H T T T (positions 1 to 6). Final Arrangement: T T T H H H. Every H needs to end up to the right of every T, the exact opposite of how they start.
Step 3: Count how many H-T pairs are "wrongly ordered" to begin with. In the Starting Arrangement, all 3 H coins sit to the left of all 3 T coins. In the Final Arrangement, every H must sit to the right of every T. So every one of the 3 H coins must cross over every one of the 3 T coins at least once. This gives \( 3 \times 3 = 9 \) required H-T crossings.
Step 4: Relate crossings to steps. Each step swaps exactly one adjacent pair. A step that swaps an H past a T fixes exactly one H-T crossing and never needs to be reversed, since coins of the same kind (H with H, or T with T) never need to change places with each other; only H-T pairs need to trade places. So the minimum number of steps equals the number of H-T crossings needed, which is 9.
Final Answer: The minimum number of steps needed is \[ \boxed{9} \]
