16 Two Colored Line up v2

Question

This is the follow-up question for 16 Two Colored Line Up

This time, you are not supposed to solve it, but find the worst possible arrangement for each square, which will make the number of steps maximum to solve it.

So what is the optimally minimum number of steps to obtain the correct order for the worst case scenario with a given example?

Hint: If you switch the same colored numbers among themselves (not their own locations), it requires at least 16 moves.

I am going to share the answer if noone could solve it in a week.

Answer 1

I believe it can always be done in 16 moves. First, a couple of lemmas.

1. Any simple permutation can be done in $n-c$ where $n$ is the number of elements and $c$ is the number of cycles in the permutation (all permutations can be broken down into a number of cycles, where the cycle is shifted by one element). This means that if we did not have the color restriction we be able to solve it in at most 15 swaps.

2. If you have $2n$ elements with $n$ elements of each color, and the elements are mixed only among their own colors, then it can be solved in $2n$ moves. This can be shown with induction as follows:

2a. Note that it is true for $n=2$, and that the first swap can be any pair.

2b. Suppose that it is true for $n\leq k-1$ (including that the first move can be any swap).

2c. Consider $n=k$. Make any swap (say 1<->2), and then swap 1 and 2 into their correct positions (for a total of 3 moves). We then have $2(k-1)$ squares left unsolved, and we have already made an initial swap (whatever was in position 1 with whatever was in position 2), so we have (by 2b) $2(k-1)-1$ moves left. Total moves is therefore $2k$. QED.

This limit is met exactly when both sides are a cycle with 1 shift.

3. Suppose that we have $2n$ squares and $m(\leq n)$ of each colour are on opposite colors. These can be put on the right squares in $2m$ moves (you may need to be careful about the order), leaving you with the situation in 2, which can therefore be solved in $2(n-m)$ moves. QED

Answer 2

The optimally minimum number of steps to obtain the correct order for the worst case scenario

$19$

and the example is as below:

In order to make the puzzle the worst possible case is to make the order with one color like tail, moving every number to the next the same color.

This is the original arrangement, if I move it one forward it becomes:

As for the other color, I do interchange the numbers between them:

Originally:

And after switch:

It does not matter how to interchange the numbers, just need to switch them for the other color while moving the other one as explained above.

As a result, it will take at least:

19 moves to solve this puzzle and it is optimal.

Answer 3

My solution:

Flip every white number with another white number, and every orange number with another orange number. So 8 trades are needed just to get the numbers onto a square where they can then be traded into a solution. After that it's a minimum of another 8 trades (total of 16) to get everything right, but that would involve getting two numbers correct with every trade.