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 ________.

Question

The primary purpose of mine ventilation is to:

Answer 1

We start with the row H H H T T T and want to reach T T T H H H, where a single allowed move (a "step") swaps two coins sitting next to each other without flipping either one. Since no coin is ever flipped, every H stays an H and every T stays a T for the whole process, only their positions along the row change. Let's work out the minimum number of steps by tracking how far each coin has to travel.

Label the coins by position: Call the three heads H1, H2, H3 (in positions 1, 2, 3) and the three tails T1, T2, T3 (in positions 4, 5, 6) at the start. In the final row, all three T's occupy positions 1, 2, 3 and all three H's occupy positions 4, 5, 6.
See that every H moves right past every T: Since the block of heads and the block of tails simply swap sides, each head must end up to the right of every tail it started to the left of, and there is no shortcut, since a coin can only move one position at a time and only by swapping with its immediate neighbor.
Count the crossings needed: Every single (head, tail) pair that starts with the head to the left of the tail must, at some point, have that head and that tail swap places directly. With 3 heads and 3 tails, that is 3 times 3, or 9, pairs that each need exactly one crossing swap, and no swap can resolve more than one pair's ordering at a time.
Build an actual sequence that uses exactly 9 steps: Slide T1 (originally in position 4) left past H3, H2 and H1 one swap at a time, that is 3 steps, which gives T H H H T T. Then slide the next T left past the three H's again, 3 more steps, giving T T H H H T. Finally slide the last T left past the three H's, 3 more steps, giving T T T H H H, the target row.

Adding up the steps used in this sequence, 3 plus 3 plus 3 equals 9 steps, and since we already showed no head-tail pair can be reordered in fewer than one dedicated swap, 9 is both achievable and the smallest possible count.

Let's summarize:

Coins are not flipped, so only their positions change, and each H-T pair whose order must reverse needs exactly one adjacent swap between that pair.
There are 3 heads and 3 tails, giving 3 times 3 equals 9 pairs whose order must flip.
An explicit swap sequence reaching T T T H H H in exactly 9 steps confirms this minimum is achievable.

The minimum number of steps needed is 9, which is option (C).

Answer 2

We start with the row H H H T T T and want to reach T T T H H H, where a single allowed move (a "step") swaps two coins sitting next to each other without flipping either one. Since no coin is ever flipped, every H stays an H and every T stays a T for the whole process, only their positions along the row change. Let's work out the minimum number of steps by tracking how far each coin has to travel.

Label the coins by position: Call the three heads H1, H2, H3 (in positions 1, 2, 3) and the three tails T1, T2, T3 (in positions 4, 5, 6) at the start. In the final row, all three T's occupy positions 1, 2, 3 and all three H's occupy positions 4, 5, 6.
See that every H moves right past every T: Since the block of heads and the block of tails simply swap sides, each head must end up to the right of every tail it started to the left of, and there is no shortcut, since a coin can only move one position at a time and only by swapping with its immediate neighbor.
Count the crossings needed: Every single (head, tail) pair that starts with the head to the left of the tail must, at some point, have that head and that tail swap places directly. With 3 heads and 3 tails, that is 3 times 3, or 9, pairs that each need exactly one crossing swap, and no swap can resolve more than one pair's ordering at a time.
Build an actual sequence that uses exactly 9 steps: Slide T1 (originally in position 4) left past H3, H2 and H1 one swap at a time, that is 3 steps, which gives T H H H T T. Then slide the next T left past the three H's again, 3 more steps, giving T T H H H T. Finally slide the last T left past the three H's, 3 more steps, giving T T T H H H, the target row.

Adding up the steps used in this sequence, 3 plus 3 plus 3 equals 9 steps, and since we already showed no head-tail pair can be reordered in fewer than one dedicated swap, 9 is both achievable and the smallest possible count.

Let's summarize:

Coins are not flipped, so only their positions change, and each H-T pair whose order must reverse needs exactly one adjacent swap between that pair.
There are 3 heads and 3 tails, giving 3 times 3 equals 9 pairs whose order must flip.
An explicit swap sequence reaching T T T H H H in exactly 9 steps confirms this minimum is achievable.

The minimum number of steps needed is 9, which is option (C).

Show Hint

The Correct Option is C

Solution and Explanation

Questions Asked in GATE MN exam