¿El rompecabezas de clasificación de bolas tiene siempre una solución?

Question

En este juego tenemos $4$ bolas de cada color y $n$ diferentes colores, para un total de $4\times n$ bolas, dispuestas en $n$ pilas. Además, tenemos $2$ pilas vacías. Un máximo de $4$ las bolas pueden estar en una pila cualquiera en un momento dado. El objetivo del juego es ordenar las bolas por colores. Sólo se puede mover la bola superior de cada pila. Una bola sólo puede dejarse encima de otra del mismo color o en una pila vacía. En el juego, $n$ es $9$ o $12.$ ¿Se puede resolver este juego para cualquier $n$ ? Supongo que es para $n=12$ o inferior, pero no creo que sea para grandes $n$ . ¿Cuántas pilas vacías se necesitan para que se pueda resolver para un número arbitrario de $n$ ?

Answer 1

Solución parcial: Incluso para $n = 12$ y $2$ pilas vacías, el juego no es resoluble para esta configuración inicial:

a a a a b b b b c c c c
d e f g g h i j j k l d
i i k k l l e e f f h h
. . . . . . . . . . . .

Este diagrama utiliza $4$ bolas de colores a, b, c , repartidos en las capas superiores, y $2$ o $3$ bolas de colores d, e, f, g, h, i, j, k, l . Cada . representa un "no me importa", es decir, se pueden rellenar arbitrariamente con las restantes bolas de colores d a través de l .

La observación clave es que los cuatro primeros movimientos podrían ser todos del mismo color (superior):

• El primer movimiento, sin pérdida de generalidad, podría ser a a una pila vacía $E_1$ .

• Cada movimiento futuro que implique un a debe ser a $E_1$ o la otra pila vacía $E_2$ porque cada a comenzó en la parte superior y es imposible poner otro a encima.

• Trasladar a otro a a $E_1$ no puede hacer daño, ya que nada más puede entrar en $E_1$ y el a en $E_1$ no puede ir a ningún otro sitio (excepto $E_2$ que no mejora el estado del juego).

• Por lo tanto, los primeros cuatro movimientos bien podrían mover los cuatro a 's en $E_1$ .

Mover todo el a 's expuso cuatro nuevas bolas, pero por construcción, todas son de diferentes colores defg , y, si mueve alguno de ellos a $E_2$ Esto expone otro nuevo color i o k y el juego está en un callejón sin salida (gracias a @JaapScherphuis por señalarlo). Lo mismo ocurre si los primeros cuatro movimientos movieron los cuatro b o los cuatro c 's. Así que para los próximos cuatro movimientos, podríamos mover las cuatro bolas de otro color superior. Otras cuatro bolas quedarán expuestas. Sin embargo, después de estos ocho movimientos:

• Si movemos todo a y b el único color común expuesto es g . Este es el único movimiento legal que queda, y cualquiera que sea g se mueve, expondrá aún un nuevo color ( k o l ) y el juego está en un punto muerto.

• Si movemos todo a y c el único color común expuesto es d y moviendo d expondrá un nuevo color ( h o i ) y el juego está en un punto muerto.

• Si movemos todo b y c el único color común expuesto es j y moviendo j expondrá un nuevo color ( e o f ) y el juego está en un punto muerto.

Otras reflexiones: Me pregunto si, por una lógica similar, para cualquier número de pilas vacías $m$ (arriba discute $m=2$ ), existe un tamaño suficientemente grande $n$ s.t. algunas configuraciones de partida serán irresolubles. Todo lo que necesitamos es $n$ tan grande que no importa qué $m$ colores superiores que elija para mover primero, el $4m$ bolas su expuestas en la capa $3$ tienen muy pocos colores comunes, y después de hacer esos movimientos, las nuevas bolas expuestas en la capa $2$ son todos nuevos.

Answer 2

Creo que también es bastante obvio que la siguiente posición para n=12 no se puede resolver

a a b b a a b b i i i i
c c c c d d d d j j j j
e e e e f f f f k k k k
g g g g h h h h l l l l

Este método también funciona para n=8 si sólo eliminamos las últimas cuatro pilas.

a a b b a a b b
c c c c d d d d
e e e e f f f f
g g g g h h h h

Esta posición no se puede resolver con dos pilas vacías.

En general, el método funciona para n=4*j con j>=2 simplemente añadiendo j-2 pilas con la estructura

w w w w
x x x x
y y y y
z z z z

Answer 3

SUPUESTO : Supongo que para cada altura $1\leqslant h \leqslant 4$ y para cada color $c$ Hay una pila en la que hay una bola de color $c$ en la altura $h$ .

Si hacemos esta suposición sobre la configuración inicial, este juego es resoluble (aunque bastante aburrido) para cualquier $n$ y sólo se necesitan dos pilas vacías. Además, el número $4$ puede ser sustituido por cualquier número. Aquí hay un algoritmo que lo resuelve :

En cada profundidad $d$ empezaremos con todas las pilas que tengan la parte superior $d$ bolas del mismo color más dos pilas vacías, y haremos una permutación de la parte superior $d$ capas, moviendo cada vez la parte superior $d$ bolas de alguna pila completa a una pila con al menos $d$ ranuras vacías. Después de realizar esta permutación, obtendremos todas las pilas que tengan la parte superior $d+1$ bolas del mismo color más dos pilas vacías y pasar a la profundidad $d+1$ hasta llegar a la profundidad 4.

(estado 1) Supongamos que estamos en la profundidad $d$ con dos pilas vacías.
Llamar a una pila hecho si su parte superior $d+1$ las bolas son del mismo color. Si todas las pilas están hechas, podemos pasar a la profundidad $d+1$ .

De lo contrario, hay alguna pila $s$ , digamos, cuya parte superior $d$ bolas son del mismo color, pero cuya siguiente bola es de un color diferente. Ponemos estas $d$ bolas en una pila vacía, que ahora llamamos pila de almacenamiento y pasar al estado 2 abajo. La rutina de abajo nos pondrá eventualmente en el estado 1 de nuevo, pero con al menos una pila menos que no es apta para la profundidad $d+1$ .

(estado 2) Estamos en la profundidad $d$ excepto en el caso de la pila de tres distinguidos :

• una pila vacía $E$
• una pila de almacenamiento (una pila que contiene $d$ bolas, todas del mismo color) $S$
• una pila incompleta $I$

Por nuestra suposición anterior (y dado que no afectamos al número de bolas de cada color a ninguna altura $h$ antes), debe haber una bola del mismo color que en el almacén situado a la profundidad $d+1$ en alguna pila $T$ . A partir de ahora :

• O bien $T \neq I$ Entonces movemos la parte superior $d$ bolas de $T$ en $E$ (que se convertirá en la nueva pila de almacenamiento) y luego mover todas las bolas de $S$ (que se convierte en vacío) en $T$ . Observe que $T$ ya está hecho, y que por lo tanto hemos aumentado el número de pilas hechas al volver al estado 2 .
• Si $T = S$ , entonces ponemos las bolas de $S$ en $I$ que ya está hecho, y llegamos al estado 1 de nuevo.

Como este proceso aumenta el número de pilas ordenadas, finalmente llegamos al caso $T=S$ arriba y volver al estado 1 como se ha dicho. Repitiendo este proceso, finalmente alcanzamos la profundidad $d+1$ .

Se requieren condiciones en la configuración inicial

@antkam exhibió una configuración inicial para la cual el juego no es resoluble para $n=12$ .

Las dificultades parecen surgir cuando hay un gran número de bolas del mismo color en una fila determinada en la configuración inicial. Además de los parámetros $m$ y $n$ discutido anteriormente, vamos a añadir un parámetro $k$ correspondiente al mayor número de bolas permitidas en una fila de una configuración inicial

Nueva pregunta

Si uno requiere $k\leqslant 2$ ¿hay un $m$ de manera que el juego se pueda resolver para todos los $n$ ?

Nota: Para $k=1$ y $m=2$ el juego se puede resolver para todos $n$ .

Un contraejemplo mínimo sin la suposición

Afirmo que la siguiente configuración inicial ( $n = 12$ ) no se puede resolver :

$$\begin{pmatrix} A & A & B & B & C & C & D & D & E & E & F & F \\ G & G & H & H & I & I & J & J & K & K & L & L \\ L & L & K & K & J & J & I & I & H & H & G & G \\ F & F & E & E & D & D & C & C & B & B & A & A\end{pmatrix} $$

---

Esta sección está escrita por antkam. ¡¡Siento mucho editar tu respuesta así!! Pero no me cabe esto en los comentarios. Siéntete libre de borrar o editar más como quieras.

El ejemplo que propones tiene solución:

A A F F . .
G G L L . .
L L G G . .
F F A A . .

. . . . . .
G G L L . .
L L G G A F
F F A A A F

. . G L . .
. . G L . .
L L G G A F
F F A A A F

. . G L . .
. L G L . F
. L G G A F
. F A A A F

. . G L . F
. . G L . F
L . G G A F
L . A A A F

y el resto es obvio. Ahora que has resuelto cuatro colores, y te quedan dos columnas vacías, puedes resolver iterativamente cada conjunto de cuatro colores.