Una generalización de un rompecabezas clásico de giro de mesa

Question

El problema es una generalización de este acertijo de la uyhip . A rompecabezas similar también se ha discutido en Puzzle Toad.

Un prisionero ha quedado atrapado en una habitación oscura, y sólo podrá escapar si consigue resolver con éxito el siguiente rompecabezas:

Frente al prisionero hay una gran mesa circular con $n$ cartas de póquer colocadas equidistantemente a lo largo del perímetro de la mesa. Puede palpar las cartas, pero no puede saber si cada una de ellas está boca arriba o boca abajo debido a la oscuridad. El prisionero puede dar la vuelta a cualquier subconjunto de cartas cada vez. Una vez que termine de hacerlo, se hará una comprobación y el prisionero será liberado si todas las cartas están boca arriba.

Lamentablemente, la mesa será rotada por un supervisor después de un número fijo de intentos. Después de cada rotación, el prisionero no podrá reconocer la posición anterior de ninguna de las cartas. Además, el supervisor conoce exactamente la estrategia del prisionero y siempre rotará la mesa de forma que dificulte el éxito del prisionero.

Ahora dejamos que $\varphi(n)$ sea el menor número tal que el prisionero pueda llegar a una estrategia ganadora en un número finito de veces cuando la mesa se gira después de cada $\varphi(n)$ intentos.

Ya se ha demostrado que $$\varphi(2^k)=1,\qquad \forall k\textrm{ non-negative integer}.$$

También es fácil mostrar $\varphi(3)\leq 3$ . Y creo que en realidad tenemos $\varphi(3)= 3$ . Aquí van las preguntas:

1. ¿Es cierto que $\varphi(5)\leq 5$ ? En general, ¿tenemos $\varphi(n)\leq n$ ?

2. ¿Es cierto que $\varphi(2^k m)=\varphi(m)$ , donde $m$ es impar?

3. ¿Tenemos una fórmula explícita para $\varphi(n)$ ?

Se agradecería cualquier ayuda.

Answer 1

Puedo proponer el siguiente modelo matemático de juego Para un determinado $n$ podemos codificar naturalmente cada elección de orientaciones de las caras de las cartas mediante una clase de equivalencia $c$ de secuencias de ceros y unos de longitud $n$ . En concreto, las secuencias $s$ y $s’$ son equivalentes siempre que $s’$ es un desplazamiento cíclico de $s$ . Por ejemplo, las secuencias $11101100$ y $10110011$ son equivalentes. Ahora dejemos que $C$ sea el conjunto de todas las clases de equivalencia. Por ejemplo, para $n=3$ el conjunto $C$ se compone de las clases $\{000\}$ , $\{100, 010, 001\}$ , $\{110, 101, 011\}$ y $\{111\}$ . El único conocimiento clave sobre el estado de un rompecabezas que tiene el prisionero es una familia $C’\subset C$ de clases de posibles elecciones de orientaciones de las caras de las cartas. Así, en una fase entre rotaciones, el prisionero intenta ganar o cambiar la familia $C’$ .

A continuación, su estrategia muestra que $\varphi(n)\le n+1$ para cada natural $n$ . Dejemos que $c_1,\dots, c_k$ sean las clases de la familia $C$ . En $k$ -en la primera fase $n$ intenta que el prisionero compruebe las orientaciones de las caras de las cartas codificadas por secuencias de la clase $c_k$ girando las caras de las cartas según cada una de esas secuencias (esto es posible, ya que $|c_k|\le n$ ) y en el último intento gira todas las caras de las cartas a la orientación que tenían al principio de la fase. Al hacerlo, gana (si la elección de las orientaciones de las caras de las cartas pertenecía a $c_k$ ) o asegurar que $c_k$ no pertenece a $C’$ . Claramente, el prisionero ganará como máximo $k$ -en una fase.

Answer 2

Escribí un programa para resolver esto modelándolo como un problema de grafos de la siguiente manera:

Los nodos son los posibles estados en los que pueden estar las cartas (sin contar aquel en el que todas las cartas están boca arriba) + cuántas rondas han pasado desde que se giró la mesa. Las aristas son subconjuntos de las cartas que podemos voltear. Empezamos en el nodo en el que todos los estados son posibles y atravesamos el gráfico hasta llegar a uno en el que el único estado posible es aquel en el que todas las cartas están boca arriba. El código fuente se puede encontrar aquí Hay una implementación en Python y otra en Rust.

Como se trata de un enfoque de fuerza bruta, no se adapta muy bien. He intentado algunas optimizaciones adicionales, pero no he sido capaz de calcular $\varphi(6)$ todavía. Sin embargo, lo que he descubierto es que:

$\varphi(3)=3$ , $\varphi(5)=6$ y $\varphi(6)>4$ .

Esto demuestra que las respuestas a su primera y segunda pregunta son ambas negativas.

Editar:

He descubierto que $\varphi(6)=5$ . Calcular esto me llevó 7 horas de cálculo, a pesar de que añadí varias optimizaciones, pequeñas y grandes (algunas especializadas para cuando $n < 7$ ).

Una cosa a tener en cuenta es que sólo hago un simple búsqueda en profundidad del gráfico. Encontrar el nodo en el que todas las cartas deben estar boca arriba podría ser mucho más rápido si se utilizara algún tipo de heurística (como disminuir el número de estados posibles). El problema es que esto no sería muy útil para encontrar límites inferiores, ya que eso te obliga a explorar todo el gráfico de todos modos.