Experimenting with Permutation Wordle

Este artículo investiga la conjetura de optimidad de la estrategia de "desplazamiento cíclico" propuesta por Kutin y Smithline para el juego Permutation Wordle, mediante la formalización de las estrategias, el análisis experimental de estrategias construidas inductivamente y el estudio de los coeficientes de su función generadora.

Lo esencial

Imagina que estás jugando a un juego de adivinanza muy especial, una versión "matemática" del famoso juego Wordle, pero en lugar de adivinar una palabra secreta, tienes que adivinar un orden secreto de números.

Aquí tienes la explicación de este documento, traducida a un lenguaje sencillo y con analogías para que cualquiera pueda entenderlo:

🎲 El Juego: "Permutación Wordle"

Imagina que tienes una caja con $n$ objetos numerados del 1 al $n$. Alguien (el "maestro del juego") los ha puesto en un orden secreto y no te lo dice.

• Tu turno: Tienes que adivinar ese orden.
• La pista: Si adivinas mal, el maestro te dice: "De los números que pusiste, estos están en la posición correcta, pero el resto no".
• El objetivo: Adivinar el orden exacto en el menor número de intentos posible.

🔄 La Estrategia Propuesta: "El Giro Circular"

Dos investigadores anteriores (Kutin y Smithline) propusieron una forma muy inteligente de jugar cuando te equivocas. Imagina que tienes una fila de personas y algunas están en el lugar correcto, pero otras no.

La estrategia llamada "Desplazamiento Cíclico" (Cyclic Shift) funciona así:

1. Mantienes a las personas que ya están en su lugar correcto (no las tocas).
2. A las personas que están mal, las mueves todas un paso a la derecha en la fila.
3. Si alguien llega al final, se va al principio (como un círculo).

La gran pregunta: ¿Es esta estrategia la mejor de todas? ¿Es imposible encontrar una forma de ganar más rápido? Kutin y Smithline adivinaron que sí, que esta es la mejor estrategia posible.

🔍 ¿Qué hizo esta autora?

Aurora Hiveley (la autora del artículo) decidió poner a prueba esa idea. No solo confió en la intuición, sino que usó matemáticas avanzadas y computadoras para ver si la "estrategia del giro circular" era realmente la campeona.

1. El Laboratorio de Pruebas (Análisis Experimental)

Primero, usó un programa informático (Maple) para simular miles de juegos.

• La analogía: Imagina que eres un entrenador de fútbol probando tácticas. En lugar de jugar un partido, le haces jugar 100 partidos a tu equipo contra oponentes aleatorios.
• El resultado: Para grupos pequeños (hasta 7 u 8 objetos), la estrategia del giro circular siempre ganó en promedio. Esto le dio mucha confianza a la teoría.

2. La Construcción de Estrategias (Inducción)

Luego, se preguntó: "¿Qué pasa si cambiamos solo una parte de la estrategia?".

• La analogía: Imagina que tienes una receta de pastel. La receta original dice: "Mueve los ingredientes a la derecha". La autora probó recetas donde, por ejemplo, los primeros 5 ingredientes se mueven a la derecha, pero el 6º se mueve de otra forma.
• El hallazgo: Sorprendentemente, al principio, todas las estrategias parecían igual de buenas. Pero cuando se profundizó en el juego (cuando el juego dura exactamente 3 intentos), la estrategia original (la del giro circular) siempre fue superior.

3. El Contador de Éxitos (Funciones Generadoras)

Aquí es donde entra la magia matemática. La autora usó algo llamado "funciones generadoras".

• La analogía: Imagina que tienes una máquina expendedora de premios. En lugar de vender galletas, vende "número de intentos necesarios para ganar".
  • Si la máquina te da 1 galleta, significa que ganaste en 1 intento.
  • Si te da 3 galletas, significa que ganaste en 3 intentos.
• La autora analizó las "galletas" (los coeficientes matemáticos) para ver cuántas veces ganabas en 3 intentos con la estrategia original versus otras estrategias.
• El veredicto: La máquina de la estrategia "Giro Circular" daba más "galletas de victoria en 3 intentos" que cualquier otra máquina que ella construyó.

🏆 La Conclusión

El artículo demuestra matemáticamente que, para juegos que se resuelven en 1, 2 o 3 intentos, la estrategia de "mover todo un paso a la derecha" es, de hecho, la mejor estrategia posible.

Es como si hubieras encontrado la llave maestra perfecta para abrir una caja fuerte en 3 intentos o menos. Si intentas usar otra llave (otra estrategia), tardarás más o fallarás más a menudo.

🔮 ¿Qué sigue?

La autora es honesta y dice: "Esto es genial para juegos cortos (3 intentos), pero no hemos probado qué pasa si el juego dura 4, 5 o más intentos". Es como si hubieras ganado el campeonato de fútbol de 15 minutos, pero aún no sabemos si ganarás el partido completo de 90 minutos. ¡Ese es el próximo desafío!

En resumen: Este papel es un viaje de descubrimiento que confirma, con matemáticas y experimentos, que la forma más inteligente de jugar a este rompecabezas de orden es simplemente mover todo un paso a la derecha cada vez que fallas.

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "Experimenting with Permutation Wordle" de Aurora Hiveley, traducido y estructurado en español.

1. Planteamiento del Problema

El artículo aborda el juego de "Permutation Wordle", una variante del popular juego Wordle desarrollada por Samuel Kutin y Lawren Smithline.

• Mecánica: Un "maestro del juego" selecciona una permutación secreta $\pi$ de $n$ objetos (etiquetados del 1 al $n$). El jugador debe adivinar esta permutación.
• Feedback: En cada ronda, tras lanzar una suposición (una permutación $\gamma_r$), el jugador recibe información sobre qué índices están en la posición correcta (coinciden con el secreto).
• Objetivo: Minimizar el número promedio de intentos necesarios para adivinar la permutación secreta.
• La Conjetura: Kutin y Smithline propusieron una estrategia llamada "cambio cíclico" (cyclic shift). En esta estrategia, si una suposición tiene posiciones incorrectas, todos los elementos en esas posiciones se desplazan un índice a la derecha en la siguiente suposición, manteniendo fijos los elementos correctos. Conjeturan que esta estrategia es óptima (minimiza el número promedio de intentos).

2. Metodología

El autor formaliza el concepto de "estrategia" y utiliza un enfoque mixto que combina análisis computacional y demostración matemática inductiva.

• Formalización de la Estrategia:

  • Una estrategia $S$ se define como una secuencia $[s_1, s_2, \dots, s_n]$, donde cada $s_i$ es una permutación de longitud $i$.
  • Para generar la siguiente suposición $\gamma_{r+1}$ a partir de $\gamma_r$, se bloquean las posiciones correctas ($J_r$) y se permutan las incorrectas ($I_r$) utilizando el componente de estrategia $S[|I_r|]$.
  • Se asume que los componentes de la estrategia deben ser derangements (permutaciones sin puntos fijos) para evitar bucles infinitos o ineficiencias.
  • La estrategia de "cambio cíclico" (CS) se define como $CS[n] = [2, 3, \dots, n, 1]$.

• Análisis Experimental:

  • Se utilizó el paquete de software Maple para simular juegos con todas las $n!$ permutaciones secretas posibles.
  • Se calcularon los promedios de intentos para estrategias "deranged" (componentes son derangements) y "cyclic" (componentes son permutaciones cíclicas) hasta $n=7$ y $n=8$ respectivamente.
  • Los datos experimentales validaron la conjetura para valores pequeños de $n$.

• Análisis Teórico (Funciones Generadoras):

  • Se define una función generadora $f_S(x) = \sum a_r x^r$, donde el coeficiente $a_r$ representa el número de permutaciones de longitud $n$ que la estrategia $S$ puede adivinar en exactamente $r$ intentos.
  • El objetivo es demostrar que para la estrategia CS, los coeficientes $a_1, a_2, a_3$ son óptimos en comparación con otras estrategias inductivas.

3. Contribuciones Clave y Resultados

A. Análisis de Coeficientes Lineales y Cuadráticos ($r=1, 2$)

• Coeficiente $x^1$: Para cualquier estrategia, solo la permutación trivial se adivina en 1 intento. Por tanto, $[x^1]f_S(x) = 1$.
• Coeficiente $x^2$: Se demuestra que el número de permutaciones adivinables en 2 intentos es $A(n, 1)$ (números de Eulerianos), independientemente de la estrategia utilizada, siempre que sea inductiva. Esto se debe a que cualquier permutación con al menos un acierto en la primera ronda cae bajo una estrategia de nivel inferior idéntica para todas las estrategias inductivas.

B. Análisis de Coeficientes Cúbicos ($r=3$) - El Núcleo del Resultado

El artículo se centra en demostrar que la estrategia de cambio cíclico (CS) maximiza el número de permutaciones adivinables en exactamente 3 intentos, lo que implica su optimidad para juegos que terminan en 3 rondas.

• Descomposición del problema: Se analiza cuándo aparece el primer acierto correcto ($\rho_S(\pi) = i$).

  • Si $\rho_S(\pi) = 1$: El número de permutaciones es constante para todas las estrategias inductivas.
  • Si $\rho_S(\pi) = 3$: El número de permutaciones es 1 para cualquier estrategia cíclica (caso trivial donde no hay aciertos en las dos primeras rondas).
  • El factor decisivo: La diferencia radica en el caso $\rho_S(\pi) = 2$ (primer acierto en la segunda ronda).

• Teorema Principal (Optimalidad de CS):

  • Se demuestra que para cualquier estrategia inductiva $S$ (donde $S[n]$ es una permutación cíclica pero no necesariamente el cambio cíclico estándar), el número de permutaciones adivinables en 3 intentos es estrictamente menor que el de la estrategia CS.
  • Lógica de la prueba: La estrategia CS permite un conjunto más grande de subconjuntos de posiciones incorrectas ($I_2$) que no generan contradicciones (bucles o imposibilidad de terminar en 3 rondas). Otras estrategias cíclicas introducen restricciones adicionales que eliminan permutaciones válidas del conjunto de soluciones en 3 rondas.
  • Resultado: $[x^3]f_{CS}(x) > [x^3]f_S(x)$ para cualquier estrategia inductiva $S$.

C. Peor Caso (Estrategia de Desplazamiento a la Izquierda)

• Se identifica la estrategia CSL (cambio cíclico a la izquierda en el primer nivel, pero a la derecha en niveles inferiores) como la menos eficiente.
• Se demuestra que el coeficiente cúbico para CSL es $L_n - n - 1$ (donde $L_n$ es el $n$-ésimo número de Lucas), que es estrictamente menor que el de cualquier otra estrategia inductiva.

4. Significado y Conclusiones

• Validación Parcial de la Conjetura: El artículo proporciona una demostración matemática rigurosa de que la estrategia de "cambio cíclico" propuesta por Kutin y Smithline es óptima para juegos que terminan en exactamente 1, 2 o 3 intentos.
• Limitaciones y Futuro:
  • La demostración se basa en estrategias inductivas con componentes cíclicos. No cubre estrategias generales con derangements arbitrarios ni juegos que requieran 4 o más intentos.
  • Los coeficientes de orden superior ($r \ge 4$) en las funciones generadoras no siguen patrones tan limpios, lo que sugiere que se necesitarán enfoques más matizados para probar la optimalidad global (promedio total de intentos).
  • El trabajo sienta las bases para futuras investigaciones sobre la estructura de las funciones generadoras en juegos de adivinanza de permutaciones y la generalización de la optimalidad de estrategias cíclicas.

En resumen, el artículo transforma una conjetura empírica en un resultado teorema para un subconjunto significativo del espacio de soluciones, utilizando herramientas combinatorias (números de Euler, números de Lucas, funciones generadoras) y análisis computacional.