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
Think about how many times a head and a tail have to swap places directly for every head to end up on the right side and every tail on the left.
Step 1: Understand what a step allows.
A step swaps two coins that are sitting right next to each other, without flipping either one, so a head stays a head and a tail stays a tail throughout, only their positions change.
We start at H H H T T T and must reach T T T H H H using the fewest such adjacent swaps.
Step 2: Notice that every head must cross every tail.
In the starting row, each of the 3 heads sits to the left of each of the 3 tails.
In the final row, each of the 3 heads sits to the right of each of the 3 tails, so the left-right order of every head and tail pair has flipped.
An adjacent swap can only change the relative order of the two coins it swaps, so to flip the order of one head-tail pair, that specific head and that specific tail must be swapped past each other at least once.
Step 3: Count how many head-tail pairs need reordering.
There are 3 heads and 3 tails, so the number of (head, tail) pairs whose order must flip is \(3 \times 3 = 9\).
Two heads never need to cross each other, since heads are identical and their own internal order does not matter, and the same is true among the tails, so no swaps are wasted reordering coins of the same face.
Step 4: Confirm this count is achievable.
One way to do it: repeatedly take the tail that is furthest to the left among the T's and adjacent-swap it leftward past every H still ahead of it.
Moving the first T past all 3 H's takes 3 swaps, moving the second T past all 3 H's takes another 3 swaps, and moving the third T past all 3 H's takes 3 more swaps, giving 3 + 3 + 3 = 9 swaps in total, and this reaches T T T H H H exactly.
Final Answer:
The minimum number of steps needed is 9, so the correct option is (C).
\[ \boxed{9} \]
