Question

From one sequence of digits, another sequence of digits has to be formed as per the following rule:
Double switch: interchange of any two digits that have at most one digit between them (that is, two digits that are either next to each other or have exactly one digit sitting between them), where one such interchange counts as one step.

Using only double switching, what is the minimum number of steps required to change 165324 to 123456?

• A. 5
• B. 6
• C. 7
• D. None of these

Hint:

Work out the fewest swaps needed if any two positions at all could be swapped. That count is already the true lower limit, even for the more restricted double switch.

Answer 1

The Correct Option is D

A cleaner way to handle this is to work out the theoretical fewest swaps first using the general rule for sorting with swaps, and only afterwards check whether the restricted double switch rule can actually reach that number.

1. General rule: for any sequence, the fewest swaps needed to sort it, using swaps between any two positions at all, equals the total count of digits minus the number of separate closed loops (cycles) the digits naturally split into, where a digit already in its correct place counts as its own loop of size one.
2. Apply it here: the sequence is 1, 6, 5, 3, 2, 4 against target 1, 2, 3, 4, 5, 6. Position 1 already holds the correct digit, 1, so that is one loop by itself. Tracing the rest: the digit at position 2 (6) belongs at position 6, the digit sitting at position 6 (4) belongs at position 4, the digit at position 4 (3) belongs at position 3, the digit at position 3 (5) belongs at position 5, and the digit at position 5 (2) belongs at position 2, which closes the loop back to where it started. That is a single loop running through all five of positions 2, 3, 4, 5, 6.
3. Count the loops: there are 2 loops in total, the lone position 1, and the big 5 position loop. With 6 digits and 2 loops, the fewest possible swaps is $6 - 2 = 4$.
4. Check double switch can still reach 4: restricting swaps to digits that are adjacent or have just one digit between them is a real limitation, so it is worth confirming 4 is still reachable, not just a lower bound. One valid sequence is: swap positions 2 and 4 to get 1 3 5 6 2 4, then positions 4 and 6 to get 1 3 5 4 2 6, then positions 3 and 5 to get 1 3 2 4 5 6, then positions 2 and 3 to get 1 2 3 4 5 6. Every one of these four swaps respects the double switch distance rule.

Let's summarize:

• The theoretical fewest swaps for this sequence, with no distance restriction, is 4.
• A concrete 4 step double switch sequence actually achieves it, so double switching cannot possibly need fewer than 4, and does not need more either.

Since 4 does not appear among options (a) 5, (b) 6 or (c) 7, the correct answer is option (d), none of these.