A coin with heads facing up is shown as a circled letter "H", and a coin with tails facing up is shown as a circled letter "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
Every step can only swap two coins that sit next to each other. Count how many H, T pairs are in the wrong relative order in the Starting Arrangement; each needs exactly one swap to fix.
Another way to find the answer is to physically walk one coin at a time into its final place and count the swaps used, instead of counting out of order pairs directly.
Move the T coins to the front one at a time: start with $H,H,H,T,T,T$. Take the first T (currently in position 4) and swap it left past the 3 H coins in front of it, one adjacent swap at a time. That takes 3 swaps and gives $T,H,H,H,T,T$.
Move the next T coin: the next T coin (now sitting right after the 3 H coins) also has to pass the same 3 H coins to reach the second position. That takes another 3 swaps, giving $T,T,H,H,H,T$.
Move the last T coin: the final T coin still has 3 H coins ahead of it, so it also needs 3 swaps to slide into place, giving $T,T,T,H,H,H$.
Add up the swaps: each of the 3 T coins needed exactly 3 swaps to cross the block of H coins, so the total is $3+3+3=9$ swaps, and no wasted or repeated swap was used anywhere in this process.
Since this step by step simulation reaches the exact Final Arrangement using 9 swaps, and no smaller number of swaps could move even one T coin fully past the 3 H coins in front of it, 9 is the minimum.
Let's summarize:
Every T coin has to cross all 3 H coins to move from the back half to the front half.
With 3 T coins each needing 3 swaps, the total comes to $3\times3=9$.
This step by step count matches the pair counting method, both giving 9.
