Una Variante del Juego de Wythoff Definida por la Secuencia G de Hofstadter

Información Básica

• ID del Artículo: 2510.11767
• Título: Una Variante del Juego de Wythoff Definida por la Secuencia G de Hofstadter
• Autores: Kahori Komaki, Ryohei Miyadera, Aoi Murakami
• Clasificación: math.CO (Matemática Combinatoria)
• Fecha de Publicación: 13 de octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.11767

Resumen

Este artículo investiga una variante del juego clásico de Wythoff. El juego clásico de Wythoff involucra dos pilas de piedras, donde dos jugadores se turnan para remover piedras de una o ambas pilas, y cuando se remueven de ambas pilas simultáneamente, debe removerse la misma cantidad. El jugador que remueve la última o las últimas piedras gana. Equivalentemente, puede considerarse como mover una reina de ajedrez en una cuadrícula grande, donde cada jugador puede moverla cualquier número de pasos en dirección vertical, horizontal o diagonal hacia la esquina superior izquierda (0,0).

En la variante de este artículo, el conjunto de posiciones terminales se expande a {(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)}. Las posiciones P de esta variante se describen mediante las posiciones P del juego de Wythoff y la secuencia G de Hofstadter. La variante posee dos propiedades notables: para posiciones (x,y) con x≥8 o y≥8, el número de Grundy de la posición (x,y) en esta variante es 1 si y solo si (x,y) es una posición P del juego de Wythoff; para posiciones (x,y) con x≥8 o y≥8, (x,y) es una posición P de la versión misère de esta variante si y solo si (x,y) es una posición P del juego de Wythoff.

Antecedentes de Investigación y Motivación

Definición del Problema

Esta investigación tiene como objetivo analizar y resolver una nueva variante del juego clásico de Wythoff, donde las condiciones terminales se expanden de una única posición (0,0) a un conjunto que contiene 6 posiciones. Esta expansión, aunque aparentemente simple, modifica significativamente la complejidad y la estructura estratégica del juego.

Importancia

1. Significado Teórico: El juego de Wythoff es un problema clásico en la teoría de juegos combinatorios, y sus posiciones P están estrechamente relacionadas con la razón áurea φ=(1+√5)/2. Investigar sus variantes contribuye a una comprensión más profunda de las propiedades estructurales de los juegos combinatorios.
2. Conexión Matemática: Esta investigación establece nuevas conexiones entre la secuencia G de Hofstadter y la teoría de juegos combinatorios, lo cual ha sido poco explorado en investigaciones anteriores.
3. Innovación Metodológica: Al introducir la función g(n) y la secuencia G de Hofstadter, proporciona nuevas herramientas matemáticas para analizar juegos combinatorios con condiciones terminales complejas.

Limitaciones de Métodos Existentes

Las posiciones P del juego clásico de Wythoff tienen una expresión de forma cerrada explícita, pero cuando las condiciones terminales se convierten en un conjunto de múltiples posiciones, los métodos de análisis tradicionales son difíciles de aplicar directamente. La teoría de juegos combinatorios existente carece de métodos sistemáticos para tratar estas condiciones terminales extendidas.

Contribuciones Principales

1. Definición de una nueva variante del juego: Expansión de las posiciones terminales del juego de Wythoff desde el punto único (0,0) al conjunto {(x,y): x+y≤2}
2. Establecimiento de una caracterización completa de posiciones P: Mediante la introducción de la función g(n) y la secuencia G de Hofstadter, se proporciona una fórmula precisa para las posiciones P de esta variante
3. Descubrimiento de dos propiedades importantes:
   • Para posiciones con x≥8 o y≥8, el número de Grundy de esta variante es 1 si y solo si la posición es una posición P del juego de Wythoff original
   • Para posiciones con x≥8 o y≥8, una posición es una posición P de la versión misère si y solo si es una posición P del juego de Wythoff original
4. Establecimiento de conexión con la secuencia G de Hofstadter: Se demuestra que la función g(n) puede definirse recursivamente mediante la secuencia G de Hofstadter

Explicación Detallada de Métodos

Definición de la Tarea

Entrada: Posición del juego (x,y), donde x,y∈ℤ≥0 Salida: Determinar si la posición es una posición P (posición ganadora del jugador anterior) o una posición N (posición ganadora del siguiente jugador) Restricciones: Las reglas de movimiento son idénticas al juego clásico de Wythoff, pero el conjunto terminal es {(x,y): x+y≤2}

Marco Matemático Central

1. Definición de la Función g(n)

g(0) = 1, g(1) = 0
g(n) = {
  1 - g(m)  si ⌊nφ⌋ = ⌊m(φ+1)⌋ + 1 para algún m∈ℤ≥0
  1         en otros casos
}

2. Caracterización del Conjunto de Posiciones P

P₁ = P₁,₁ ∪ P₁,₂ ∪ {(0,0)}, donde:

• P₁,₁ = {(⌊nφ⌋ + g(n) - 1, ⌊n(φ+1)⌋ + g(n)) : n ∈ ℤ≥0}
• P₁,₂ = {(⌊n(φ+1)⌋ + g(n), ⌊nφ⌋ + g(n) - 1) : n ∈ ℤ≥0}

3. Conexión con la Secuencia G de Hofstadter

Para n≥2:

g(n) = {
  1 - g(h(n-1))  si h(n-2) < h(n-1)
  1              en otros casos
}

donde h es la secuencia G de Hofstadter: h(0)=0, h(n)=n-h(h(n-1))

Puntos de Innovación Técnica

1. Técnica de Descomposición de Secuencias: Mediante la descomposición de números naturales en la secuencia de Wythoff inferior A₁={⌊nφ⌋} y la secuencia de Wythoff superior A₂={⌊n(φ+1)⌋}, se establece un marco de análisis sistemático.
2. Diseño de Función Recursiva: El diseño de la función g(n) captura ingeniosamente cómo la expansión del conjunto terminal afecta la distribución de posiciones P.
3. Análisis del Número de Grundy: Mediante el cálculo de números de Grundy, se establece una conexión profunda entre esta variante y el juego original.

Configuración Experimental

Método de Verificación Teórica

Este artículo emplea un método de demostración puramente teórica, verificando resultados mediante los siguientes pasos:

1. Demostración de Completitud: Demostración de que desde cualquier posición no-P se puede mover a una posición P
2. Demostración de Consistencia: Demostración de que desde una posición P no se puede mover a otra posición P
3. Verificación Computacional: Verificación exhaustiva para casos de pequeña escala

Rango Específico de Verificación

• Análisis exhaustivo completo para todos los casos con coordenadas x,y≤7
• Para casos con x≥8 o y≥8, se establece la relación de equivalencia con el juego de Wythoff original mediante demostración teórica

Resultados Experimentales

Resultados Teóricos Principales

Teorema 1: Caracterización Completa de Posiciones P

El conjunto P₁ es el conjunto de posiciones P de esta variante del juego, demostrado mediante Lema 8 y Lema 12:

• Lema 8: Desde una posición en P₁ no se puede mover a otra posición en P₁
• Lema 12: Desde cualquier posición que no esté en P₁ se puede mover a alguna posición en P₁

Teorema 2: Relación con el Juego de Wythoff Original

Para posiciones (x,y) con x≥8 o y≥8:

• G₂(x,y,1)=0 en esta variante si y solo si G₀(x,y)=0 en el juego original
• Esto establece la equivalencia de los dos juegos en posiciones "grandes"

Teorema 3: Propiedades de la Versión Misère

Las posiciones P de la versión misère (donde el jugador que entra en el conjunto terminal pierde) son idénticas a las posiciones P del juego original más la suma de un juego de una sola pila.

Resultados de Verificación a Pequeña Escala

Mediante verificación exhaustiva, se determinaron los siguientes conjuntos de posiciones P a pequeña escala:

• Conjunto A: {(0,0,1), (0,1,1), (0,2,1), (1,0,1), (1,1,1), (2,0,1), (3,6,1), (6,3,1), (4,8,1), (8,4,1)}
• Conjunto B: {(0,3,1), (1,2,1), (2,1,1), (3,0,1), (4,4,1), (5,7,1), (7,5,1)}
• Conjunto C: {(0,0), (1,2), (2,1), (3,5), (5,3), (4,7), (7,4)}

Hallazgos Clave

1. Efectos de Frontera: En el rango x,y≤7, la distribución de posiciones P difiere significativamente del juego de Wythoff original
2. Comportamiento Asintótico: Cuando las coordenadas son suficientemente grandes, el comportamiento de esta variante converge al juego de Wythoff original
3. Propiedades de Secuencias: El patrón de valores de la función g(n) está estrechamente relacionado con las propiedades de crecimiento de la secuencia G de Hofstadter

Trabajo Relacionado

Teoría del Juego de Wythoff

El juego clásico de Wythoff fue propuesto por W.A. Wythoff en 1907, y la relación entre sus posiciones P y la razón áurea es un resultado clásico de las matemáticas combinatorias. La investigación relacionada incluye:

• Teorema de Rayleigh: Establece las propiedades de partición de las secuencias de Wythoff inferior y superior
• Investigación de diversas variantes del juego de Wythoff

Teoría de Secuencias de Hofstadter

Hofstadter definió múltiples secuencias recursivas en Gödel, Escher, Bach, donde la secuencia G posee propiedades especiales de teoría de números:

• Investigación de funciones recursivas por Gault y Clint (1988)
• Análisis de relaciones recursivas singulares por Granville y Rasson (1988)

Teoría de Juegos Combinatorios

Este artículo pertenece al ámbito de la teoría de juegos combinatorios justos:

• Teorema de Sprague-Grundy y sus aplicaciones
• Métodos de determinación de posiciones P y N
• Marco teórico de juegos misère

Conclusiones y Discusión

Conclusiones Principales

1. Solución Completa: Se proporciona una caracterización completa de posiciones P para la variante del juego de Wythoff con condiciones terminales extendidas
2. Conexiones Profundas: Se revelan las conexiones esenciales entre esta variante y la secuencia G de Hofstadter
3. Equivalencia Asintótica: Se demuestra la relación de equivalencia entre esta variante y el juego original en casos de coordenadas grandes

Limitaciones

1. Complejidad: La definición de la función g(n) es relativamente compleja, no tan elegante como la solución de forma cerrada del juego de Wythoff original
2. Eficiencia Computacional: La determinación de posiciones P requiere calcular la secuencia de Hofstadter, lo que puede presentar problemas de complejidad computacional
3. Generalización: Permanece incierto si el método puede generalizarse a otros conjuntos terminales

Direcciones Futuras

1. Conjuntos Terminales Más Generales: Investigación de variantes del juego de Wythoff con conjuntos terminales arbitrarios
2. Optimización de Algoritmos: Desarrollo de algoritmos más eficientes para la determinación de posiciones P
3. Otras Secuencias Recursivas: Exploración de aplicaciones de otras secuencias recursivas famosas en juegos combinatorios

Evaluación Profunda

Fortalezas

1. Profundidad Teórica: Establece nuevas conexiones entre la teoría de juegos combinatorios y la teoría de secuencias recursivas, con importante valor teórico
2. Innovación Metodológica: El diseño de la función g(n) es ingenioso, capturando mediante definición recursiva la estructura compleja del juego
3. Demostraciones Completas: Proporciona demostraciones matemáticas completas, incluyendo argumentación detallada de numerosos lemas técnicos
4. Resultados Profundos: Las propiedades de equivalencia asintótica descubiertas proporcionan nuevas perspectivas para comprender juegos combinatorios complejos

Deficiencias

1. Expresión Compleja: La definición de la función g(n) es relativamente abstracta, lo que puede afectar la comprensión intuitiva de los resultados
2. Utilidad Práctica Limitada: Aunque teóricamente completo, el valor en aplicaciones prácticas aún no está claro
3. Dificultad de Generalización: La especificidad del método puede limitar su aplicación a otros problemas

Impacto

1. Valor Académico: Abre nuevas direcciones para la investigación interdisciplinaria entre teoría de juegos combinatorios y secuencias recursivas
2. Contribución Metodológica: Proporciona nuevas herramientas para analizar juegos combinatorios con condiciones terminales complejas
3. Completitud Teórica: Enriquece el sistema teórico de variantes del juego de Wythoff

Escenarios Aplicables

1. Investigación Teórica: Adecuado para investigación teórica en matemática combinatoria y teoría de juegos
2. Diseño de Algoritmos: Proporciona base teórica para diseñar algoritmos de estrategia óptima para juegos relacionados
3. Aplicación Educativa: Puede servir como excelente caso de estudio para demostrar conexiones entre secuencias recursivas y problemas combinatorios

Referencias

1. M.H. Albert, R.J. Nowakowski, and D. Wolfe: Lessons In Play, A K Peters/CRC Press, 2007
2. D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, 1980
3. W.A. Wythoff: A modification of the game of Nim, Nieuw Arch. Wiskd, 7 (1907), 199-202
4. V. Granville and J.-P. Rasson, A strange recursive relation, J. Number Theory 30 (1988), 238–241

Este artículo realiza contribuciones teóricas importantes en el campo de la teoría de juegos combinatorios. Al combinar ingeniosamente la secuencia G de Hofstadter, proporciona un marco matemático completo para analizar variantes del juego de Wythoff con condiciones terminales complejas. Aunque presenta ciertas limitaciones en términos de aplicabilidad práctica, su profundidad teórica e innovación metodológica lo convierten en un resultado de investigación importante en este campo.