Ordena las monedas- otros casos

Mi amigo Abel me escribió la semana pasada sobre posibles soluciones de los posts que había publicado esos días. Me pareció interesante lo que había encontrado, así que le pedí que escribiera un pequeño texto para el blog, ¡dando lugar así a la primera colaboración autoral de "JdelCastillo's hideout"! A continuación, reproduzco el texto que me ha mandado Abel.

Los dos últimos posts han sido sobre agrupar monedas alternas. El primero tiene 3 pares de monedas y el segundo, 4. El de 3 lo resolví a mano bastante rápido, pero el de 4 me costó y se me ocurrió hacer un programa que busca todas las combinaciones hasta sacar una solución (solución por fuerza bruta). Al comprobar las soluciones, me llamó la atención la frase en ambos posts: "una posible solución es". ¿Había varias soluciones? ¿Cuántas?

Como ya tenía el programa, lo adapté para que no parase al encontrar una solución, e imprimiese todas las opciones posibles. Lo ejecuté para el de 3 parejas, y me dio 6 soluciones. Efectivamente hay varias alternativas, la que yo encontré y la del posts eran 2 de ellas. ¿Serías capaz de sacarlas todas? Las tienes aquí debajo si lo necesitas (haz click para revelarlas):

Soluciones para 3 parejas y 4 movimientos:

0- 010101__
1- 0101__01
2- 0__11001
3- 001110__
4- __111000

0- 010101__
1- 0101__01
2- 0__11001
3- 00011__1
4- 000__111

0- 010101__
1- 010__110
2- 01011__0
3- 0__11100
4- 000111__

0- 010101__
1- 01__0101
2- 01100__1
3- 0__00111
4- 000__111

0- 010101__
1- 01__0101
2- 01100__1
3- __100011
4- 111000__

0- 010101__
1- 0__10110
2- 0011__10
3- 001110__
4- __111000

Pero cuando lo ejecuté para el caso de 4 parejas... resulta que sólo sacó una solución, la del post. ¡La solución es única! Por eso es mucho más difícil.

Soluciones para 4 parejas y 4 movimientos:

0- 01010101__
1- 0__1010110
2- 0011__0110
3- 0011110__0
4- __11110000

En este momento, y dado que tenía un programa que había "generalizado", la pregunta obvia es: ¿qué pasa si añadimos más parejas? Lo ejecuté para el caso de 5 parejas, pero no encontró ninguna solución de 4 movimientos, son demasiado pocos. Subí hasta permitir 5 movimientos... y apareció una única solución.

Soluciones para 5 parejas y 5 movimientos:

0- 0101010101__
1- 0__101010110
2- 001101__0110
3- 001__1100110
4- 001111100__0
5- __1111100000

Luego llegó el caso 6. De nuevo, no hay soluciones con 5 movimientos, pero sí con 6: exactamente 1 solución también.

Soluciones para 6 parejas y 6 movimientos:

0- 010101010101__
1- 0__10101010110
2- 0011__01010110
3- 001110010__110
4- 00111__1000110
5- 00111111000__0
6- __111111000000

Lamentablemente mi algoritmo nada optimizado es exponencial y tarda demasiado para más parejas. Pero me quedó la duda: ¿sigue esto hasta el infinito? ¿En alguno momento la cadena de "1 solución única para X parejas con X movimientos" se rompe? ¿Y por qué el caso de 3 parejas con 3 movimientos no tiene soluciones?