El Problema de la Torre de Hanoi de Cuatro Clavijas Restringido por Paridad y su Gráfico Asociado

Información Básica

• ID del Artículo: 2510.22361
• Título: El Problema de la Torre de Hanoi de Cuatro Clavijas Restringido por Paridad y su Gráfico Asociado
• Autor: El-Mehdi Mehiri
• Clasificación: math.CO (Matemática Combinatoria), cs.DM (Matemática Discreta)
• Fecha de Presentación: Enviado a arXiv el 25 de octubre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2510.22361v1

Resumen

Este artículo introduce e investiga una nueva variante del problema de la Torre de Hanoi de cuatro clavijas que impone restricciones de paridad. De las cuatro clavijas, dos son clavijas neutras (que permiten la colocación de cualquier disco), mientras que las otras dos son clavijas restringidas: una permite solo discos con etiqueta par, y la otra permite solo discos con etiqueta impar. Bajo estas restricciones, el autor investiga cuatro objetivos de optimización típicos y deriva fórmulas exactas para el número óptimo de movimientos para cada objetivo. El estudio establece un sistema de relaciones de recurrencia acopladas y lo expande en recurrencias de orden superior y expresiones de forma cerrada explícitas. Estas fórmulas exhiben patrones de crecimiento periódico, revelando que todas las soluciones muestran crecimiento exponencial, pero a una velocidad significativamente más lenta que el problema clásico de tres clavijas. En particular, cada secuencia de movimiento óptima posee un orden asintótico "semi-exponencial" inducido por las restricciones de paridad. Además, el artículo define el gráfico de Hanoi restringido por paridad asociado, cuyos vértices representan todos los estados viables y las aristas representan movimientos legales, y determina sus propiedades incluyendo orden, grado, conectividad, planaridad, diámetro, hamiltonianidad, número de clique y número cromático.

Antecedentes y Motivación de la Investigación

Problema de Investigación

El problema central investigado en este artículo es: ¿Cómo completar óptimamente diferentes configuraciones de objetivo en el problema de la Torre de Hanoi de cuatro clavijas con restricciones de paridad impuestas?

El problema clásico de la Torre de Hanoi tiene más de un siglo de historia de investigación:

• Problema de tres clavijas: Tiene una solución exponencial clara $h_3^n = 2^n - 1$, estructura simple
• Problema de cuatro clavijas (Rompecabezas de Reve): La solución óptima no fue confirmada hasta 2014 por Bousch, complejidad más alta
• Cinco clavijas y superiores: Se cree que el algoritmo Frame-Stewart es óptimo, pero carece de prueba formal hasta ahora

Importancia del Problema

1. Significado Teórico: El problema de la Torre de Hanoi es un ejemplo clásico de optimización combinatoria y algoritmos recursivos; el estudio de sus variantes puede profundizar la comprensión de estructuras recursivas y espacios de estado
2. Optimización Restringida: Las restricciones de paridad representan una clase importante de limitaciones estructurales que tienen universalidad en aplicaciones prácticas (como asignación de recursos, problemas de programación)
3. Valor en Teoría de Grafos: Los gráficos de estado asociados proporcionan una nueva perspectiva para estudiar las propiedades estructurales de grafos restringidos
4. Análisis de Complejidad: Investigar cómo las restricciones cambian la complejidad computacional del problema tiene valor orientador para el diseño de algoritmos

Limitaciones de Métodos Existentes

1. Torre de Hanoi Clásica: No considera atributos especiales o restricciones de clavijas
2. Variantes Existentes: Se enfoca principalmente en cambios en el número de clavijas, investigando menos restricciones estructurales
3. Investigación en Teoría de Grafos: Las propiedades de los gráficos clásicos de Hanoi han sido ampliamente estudiadas, pero las versiones restringidas aún no han sido exploradas sistemáticamente

Motivación de la Investigación

La innovación del autor radica en:

1. Introducir restricciones de paridad como una limitación natural y significativa
2. Investigar sistemáticamente cómo las restricciones cambian las estrategias óptimas y las tasas de crecimiento
3. Establecer un marco completo de teoría de grafos que conecte problemas de optimización con estructuras de grafos
4. Revelar la posición única del problema restringido entre los problemas clásicos de tres y cuatro clavijas

Contribuciones Principales

Las contribuciones principales del artículo incluyen:

1. Definición de Nuevo Problema: Primera propuesta y formalización del problema de la Torre de Hanoi de cuatro clavijas con restricciones de paridad, definiendo cuatro objetivos de optimización típicos:
   • (a) Transferencia de torre completa: de N₁ a N₂
   • (b) Separación de paridad: discos impares a O, discos pares a E
   • (c) Impares a O, pares a N₂
   • (d) Impares a N₂, pares a E
2. Sistema de Relaciones de Recurrencia: Establece un sistema de recurrencia acoplada que describe las cuatro secuencias de movimiento óptimas $(a_n, b_n, c_n, d_n)$ (Teorema 1), y prueba la unicidad de la solución óptima (Corolario 1)
3. Fórmulas Explícitas: Deriva relaciones de recurrencia de orden superior (Proposición 2) y expresiones de forma cerrada (Proposición 3), revelando patrones de crecimiento periódico
4. Análisis Asintótico: Prueba que todas las cuatro secuencias tienen crecimiento "semi-exponencial" $\Theta(\sqrt{2}^n)$ (Teorema 3), significativamente más lento que la tasa de crecimiento $2^n$ del problema de tres clavijas
5. Caracterización en Teoría de Grafos: Análisis completo de las propiedades estructurales del gráfico de Hanoi restringido por paridad $P^n$:
   • Número de vértices: $|V(P^n)| = 3^n$
   • Fórmulas recursivas y de forma cerrada para el número de aristas
   • Conectividad: $\kappa(P^n) = \lambda(P^n) = 2$
   • Planaridad: solo planar cuando $n \leq 2$
   • Hamiltonianidad: todos los $P^n$ son grafos hamiltonianos
   • Número cromático: $\chi(P^n) = \omega(P^n) = 3$ (grafo perfecto)
   • Índice cromático: $\chi'(P^n) = \Delta(P^n) = 5$
6. Relaciones Jerárquicas: Prueba que $H_{\lceil n/2 \rceil}^3 \subseteq P^n \subseteq H_n^4$, estableciendo la posición del gráfico restringido por paridad en el espectro de gráficos clásicos de Hanoi

Explicación Detallada de Métodos

Definición de Tareas

Configuración del Problema:

• Conjunto de Clavijas: $P = \{N_1, N_2, O, E\}$
  • $N_1, N_2$: Clavijas neutras, pueden contener cualquier disco
  • $O$: Clavija impar, solo puede contener discos con etiqueta impar
  • $E$: Clavija par, solo puede contener discos con etiqueta par
• Discos: $[n] = \{1, 2, \ldots, n\}$, etiqueta 1 es la más pequeña
• Estado: Cuádrupla $S = (N_1, E, O, N_2)$, representando el conjunto de discos en cada clavija, debe satisfacer:
  • Los discos en cada clavija son estrictamente crecientes de arriba a abajo
  • Cada disco está en una clavija compatible con su paridad
• Movimiento Legal: El disco $d$ se puede mover de la clavija $p$ a la clavija $q$ legalmente si y solo si:
  • $d$ es el disco superior en $p$
  • $q$ está vacía o su disco superior es mayor que $d$
  • Tanto $p$ como $q$ permiten la paridad de $d$

Estado Inicial: $S_0 = ([n], \emptyset, \emptyset, \emptyset)$ (todos los discos en N₁)

Cuatro Objetivos de Optimización:

• $a_n$: Transferencia a $(\emptyset, \emptyset, \emptyset, [n])$
• $b_n$: Transferencia a $(\emptyset, [n]_0, [n]_1, \emptyset)$ (separación de paridad)
• $c_n$: Transferencia a $(\emptyset, \emptyset, [n]_1, [n]_0)$
• $d_n$: Transferencia a $(\emptyset, [n]_0, \emptyset, [n]_1)$

Derivación de Relaciones de Recurrencia

Teorema 1 (Sistema de Recurrencia Acoplada):

Relaciones de recurrencia central: $a_n = 2b_{n-1} + 1$