Puzzle sobre una mesa giratoria con una moneda en cada esquina.

Question

[La primera parte de este rompecabezas está inspirada en un rompecabezas que encontré en fivethirtyeight.com, pero el resto es novedoso].

Parte 1
Hay una mesa cuadrada con una moneda en cada esquina. No puedes ver la mesa. La única forma en que puedes afectarla es diciéndole a la persona que controla la mesa qué monedas en qué esquinas debe lanzar. Pueden ser tantas monedas como quieras, pero todas se harán a la vez. Por ejemplo, una respuesta válida sería "lanzar la moneda inferior izquierda y la superior derecha". Después de ejecutar cada movimiento, u orden, la persona que controla la mesa la girará a una nueva orientación aleatoria que no se distingue de la original.
Tu objetivo: hacer que llegue al estado de todas las cabezas. Si, en algún momento, llega a este estado, se le comunicará inmediatamente y ganará.
¿Cómo hacerlo en un número finito de movimientos?

Parte 2
Encontrar una solución general para el caso en que en lugar de tener una mesa con 4 esquinas, las monedas se colocan en un $n\times n$ de la Junta, que sigue las mismas reglas. De nuevo, puedes especificar tu movimiento como antes, se girará como antes, y tu objetivo sigue siendo el mismo.
Para cualquier $n$ ¿se puede hacer en un número finito de movimientos? Si es así, ¿cómo? ¿Cómo aumenta el número de movimientos con $n$ ?

Parte 3
En lugar de una mesa cuadrada, la mesa tiene ahora la forma de un $n$ -gon. Para lo cual $n$ es posible, y de nuevo, cómo varía el número de movimientos con $n$ ?

He resuelto la primera parte, y tengo una solución para la segunda, pero está incompleta. La tercera parte está completamente en juego. A continuación publicaré mis respuestas, con una breve explicación de por qué funcionan y por qué creo que son óptimas. Te sugiero que pruebes tú mismo las dos primeras partes antes de ver mi solución. Preferiría que las respuestas a esto siguieran una notación consistente con mis respuestas, pero siéntase libre de introducir una nueva notación.

Answer 1

Parte 1

La primera observación clave es observar que las posiciones reales de las monedas no importan realmente, ya que haremos girar la mesa después de cada movimiento. Esto significa que todas las jugadas que son iguales en la rotación son de hecho la misma jugada, ya que sus resultados son indistintos. Esto significa que las jugadas que tenemos son voltear todo el tablero (W), voltear cualquier moneda individual (S), voltear dos monedas adyacentes (A) y voltear dos monedas diagonalmente opuestas (D).
Ahora, hay cuatro posibilidades para el estado inicial del tablero.
$\begin{matrix} T & T\\ T & T \end{matrix}$ (llamemos a este estado 1)
$\begin{matrix} T & H\\ H & T \end{matrix}$ (llamémosle estado 2)
$\begin{matrix} H & H\\ T & T \end{matrix}$ (llamémosle estado 3)
$\begin{matrix} H & H\\ H & T \end{matrix}$ (llamamos a este estado 4)
Ahora, primero resolvemos el estado 1, volteando todo (W). Si estaba inicialmente en el estado 1, ahora está resuelto, y si estaba en el estado 2,3 o 4, sigue estándolo (se puede verificar manualmente).
A continuación, resolvemos el estado 2. Esto se puede hacer volteando primero una diagonal (D). Este movimiento resuelve el estado 2, o lo lleva al estado 1, que resolvemos resolviendo de nuevo el estado 1, o volteando todo. Así, nuestra secuencia de movimientos hasta ahora ha sido W DW. Se puede comprobar fácilmente que esta secuencia de movimientos deja los estados 3 y 4 sin cambios.
A continuación, resolvemos el estado 3. Lo hacemos lanzando dos monedas a lo largo de monedas adyacentes (A). Esto lo resuelve o lo lleva al estado 1 o 2, lo que significa que repetimos toda la solución hasta el estado 2. Así, nuestra secuencia de movimientos es ahora W DW ADW
Para la cuarta parte, lanzamos una sola moneda (S). Esto lo lleva al estado 1, 2 o 3. Ahora, simplemente podemos repetir nuestra solución hasta el estado 3.
Así, la secuencia de movimientos final es
W DW ADW SWDWADW

Parte 2
El siguiente paso es resolverlo para un $n \times n$ de la rejilla. El truco que utilizaremos es dividir cada $n \times n$ cuadriculada, de la que ya conocemos la solución. Por ejemplo, podemos dividir lo siguiente Cuadrícula de 3 por 3 como los 3 objetos independientes $S1$ = ABCD, $S2$ = EFGH y el punto independiente $S3$ = I. Ahora, técnicamente podemos resolver cada uno de los cuadrados de forma independiente.
Sin embargo, el problema es que nuestra solución para una sola casilla depende de que la persona que controla nos detenga cada vez que damos con la condición de 4 caras, pero ahora sólo obtenemos una parada una vez que las 9 monedas son caras. Para evitar esto, anidamos las soluciones entre sí. Es decir, para resolver la cuadrícula de 3 por 3, primero hacemos el primer movimiento del $S1$ y luego ejecutar el todo solución de $S2$ y $S3$ juntos. La solución de $S2$ y $S3$ consiste en hacer $S3$ después de cada movimiento de $S2$ . Así, si en algún momento uno de $S1, S2$ o $S3$ está resuelto, el resto se comprobará también y se resolverá. De nuevo, esto sigue un principio recursivo que la primera solución necesaria. Para terminar la solución para un $n \times n$ podemos simplemente observar que cualquier cuadrícula de este tipo puede subdividirse en alguna combinación de cuadrículas de menor tamaño.
Así, el número de movimientos necesarios parece crecer exponencialmente.

Esto es todo lo que tengo por ahora, ¡y espero más ayuda para el hivemind!

Answer 2

¿Parte 3?

Digamos que consideramos el juego de la mesa giratoria en un $n$ -gon. ¿Qué soluciones existen?

Dejemos que $n = 2^k$ para algunos $k \in \mathbb{N}$ entonces existe una solución. La prueba es del mismo sabor que su respuesta. Como caso base, supongamos que existe una solución para $k = 2$ . Como la hipótesis de inducción supone que el $2n$ -gon tiene una solución.

Consideremos un $2 n$ -gon. En primer lugar, etiqueta los lados como una tupla $(v_1 , \ldots, v_{2 n})$ . Un lado puede ser "cabeza $1$ o "colas $0$ . Las rotaciones, también representadas como tuplas, intercambian los índices de forma cíclica. A continuación, observamos que cada solución puede darse como una secuencia de reorientaciones $C(n) = \lbrace c_i \rbrace$ cada uno de los cuales es un operador XOR. Como ejemplo,

$$c = (0, \ldots, 0)$$

será la reorientación nula.

La idea básica será dividir el $2n$ -gon en bloques de tamaño dos. Cada bloque es coincidente o no coincidente. El milagro es que esto significa que hay tanto $2^n$ formas de etiquetar los bloques y $2^n$ formas de etiquetar los internos (coincidentes/no coincidentes). Consideremos una reorientación arbitraria $c_i$ en un $n$ -gon y dos aumentos de la reorientación a un $2n$ -Reorientación de la góndola,

$$c_i = (f_1(i),f_2(i),\ldots,f_{n}(i)) \to_{\phi} (f_1(i),f_1(i),\ldots,f_{n}(i),f_{n}(i))$$

$$d_i = (f_1(i),f_2(i),\ldots,f_{n}(i)) \to_{\psi} (f_1(i), 0, f_2(i), 0, \ldots, f_{n}(i), 0)$$

El etiquetado interno no se ve afectado por las aplicaciones de $\phi(c_i)$ . Le animo a que lo compruebe. Por otro lado, el etiquetado interno puede ser cambiado por aplicaciones de $\psi(d_i)$ . En este punto, la solución natural es hacer coincidir primero el etiquetado interno de los bloques y luego alinear las etiquetas de los bloques. Como no podemos ver nada, tendremos que trabajar bajo el supuesto de que cualquier aplicación de $\psi(d_i)$ podría haber coincidido con las orientaciones internas, lo que significaría que se podrían empezar a alinear los bloques.

Por inducción, tenemos la secuencia de soluciones $C = \lbrace c_i \rbrace$ para el $n$ -gon. Como nuestras reorientaciones aumentadas respetan esta simetría también podemos llevar cada bloque a través de cada posibilidad de etiqueta aplicando $\phi(I)$ . A continuación, aplicamos $\psi(d_1)$ para cambiar las etiquetas internas, seguido de $\phi(C)$ de nuevo, y así sucesivamente. Como una secuencia de aplicaciones,

$$\phi(C) \to \psi(d_1) \to \phi(C) \to \psi(d_2) \to \ldots \to \psi(d_n) \to \phi(C)$$

Si la explicación anterior le confunde, recuerde la simetría. Una operación respeta la simetría de los bloques y hay $2^n$ de esos. La otra operación no respeta la simetría y también hay $2^n$ de esos. Así, el $2n$ -gon será llevado a través de $2^n \cdot 2^n = 2^{2n}$ estados.

Para $n = 1$ podemos abreviar, $$1$$

Para $n = 2$ , $$11 \to 10 \to 11$$

Para $n = 4$ , $$1111 \to 1010 \to 1111 \to 1010 \to 1111 \to 1010 \to 1111 \to 1000 \to 1111 \to 1010 \to 1111 \to 1100 \to 1111 \to 1010 \to 1111$$

La recursión para la longitud es,

$$l_{k+1} = (l_k+1) \cdot l_k + l_k = l_k^2 + l_k, \quad n_1 = 1$$

$$\Rightarrow l_k = 2^{2^{k-1}}-1$$

por lo que los problemas más grandes son completamente inviables.