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
Count how many times each H coin must cross an adjacent T coin; the total number of such crossings is the minimum number of steps.
This type of problem is best solved by counting inversions between the starting and final sequences, since the minimum number of adjacent transpositions needed to sort one sequence into another always equals the number of inversions between them.
Label the starting sequence positions $1$ to $6$ with values $H,H,H,T,T,T$, where the target order requires every $T$ to rank before every $H$. An inversion is any pair of positions $(i,j)$ with $i<j$ where the coin at position $i$ should actually come after the coin at position $j$ in the final order.
In the starting sequence, every $H$ (at positions $1,2,3$) is paired with every $T$ (at positions $4,5,6$), and in every one of these pairs the $H$ appears before the $T$, which is backwards relative to the target order $T,T,T,H,H,H$. The number of such crossing pairs is $3 \times 3 = 9$.
There are no inversions among the three H's themselves, since they are identical and already in a valid relative order, and none among the three T's either, so they contribute $0$ extra swaps.
Since each adjacent swap can remove at most one inversion, and there are exactly $9$ inversions to remove, the minimum number of steps is exactly $9$.
\[\boxed{\text{Minimum steps} = 9}\]
Was this answer helpful?
0
Top Questions on Analytical Reasoning - Arrangements and Permutations
