2025-11-12T21:19:10.850730

The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph

Mehiri
We introduce and study a new four-peg variant of the Tower of Hanoi problem under parity constraints. Two pegs are neutral and allow arbitrary disc placements, while the remaining two pegs are restricted to discs of a prescribed parity: one for even-labelled discs and the other for odd-labelled discs. Within this constrained setting, we investigate four canonical optimization objectives according to distinct target configurations and derive for each the exact number of moves required to optimally transfer the discs. We establish a coupled system of recursive relations governing the four optimal move functions and unfold them into higher-order recurrences and explicit closed forms. These formulas exhibit periodic growth patterns and reveal that all solutions grow exponentially, but at a significantly slower rate than the classical three-peg case. In particular, each optimal move sequence has an a half-exponential-like asymptotic order induced by the parity restriction. In addition, we define the associated parity-constrained Hanoi graph, whose vertices represent all feasible states and whose edges represent legal moves. We determine its order, degrees, connectivity, planarity, diameter, Hamiltonicity, clique number, and chromatic properties, and show that it lies strictly between the classical three- and four-peg Hanoi graphs via the inclusion relation.
academic

The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph

Basic Information

  • Paper ID: 2510.22361
  • Title: The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph
  • Author: El-Mehdi Mehiri
  • Classification: math.CO (Combinatorics), cs.DM (Discrete Mathematics)
  • Submission Date: October 25, 2025 to arXiv
  • Paper Link: https://arxiv.org/abs/2510.22361v1

Abstract

This paper introduces and investigates a novel variant of the four-peg Tower of Hanoi problem with parity constraints. Among the four pegs, two are neutral pegs (allowing arbitrary disk placement), while the other two are restricted: one permits only even-numbered disks, and the other permits only odd-numbered disks. Under these constraints, the author studies four canonical optimization objectives and derives exact formulas for the optimal number of moves for each objective. The research establishes a coupled system of recurrence relations and expands it into higher-order recurrences and explicit closed-form expressions. These formulas exhibit periodic growth patterns, revealing that all solutions exhibit exponential growth, but at rates significantly slower than the classical three-peg problem. Notably, each optimal move sequence possesses a "semi-exponential" asymptotic order induced by the parity constraints. Furthermore, the paper defines the associated parity-constrained Hanoi graph, whose vertices represent all feasible states and edges represent legal moves, and determines its properties including order, degree, connectivity, planarity, diameter, Hamiltonicity, clique number, and chromatic number.

Research Background and Motivation

Research Problem

The core research question is: How can different target configurations be optimally completed in the four-peg Tower of Hanoi problem with parity constraints?

The classical Tower of Hanoi problem has a research history spanning over a century:

  • Three-peg problem: Has a clear exponential solution h3n=2n−1h_3^n = 2^n - 1, with simple structure
  • Four-peg problem (Reve's puzzle): Optimal solution confirmed only in 2014 by Bousch, with higher complexity
  • Five or more pegs: Frame-Stewart algorithm is believed optimal, but lacks formal proof to date

Problem Significance

  1. Theoretical Significance: The Tower of Hanoi problem is a classical exemplar of combinatorial optimization and recursive algorithms; studying its variants deepens understanding of recursive structures and state spaces
  2. Constrained Optimization: Parity constraints represent an important class of structural limitations with universal applicability in practical applications (e.g., resource allocation, scheduling problems)
  3. Graph-Theoretic Value: The associated state graphs provide new perspectives for studying the structural properties of constrained graphs
  4. Complexity Analysis: Studying how constraints alter problem computational complexity provides guidance for algorithm design

Limitations of Existing Methods

  1. Classical Tower of Hanoi: Does not consider special attributes or constraints on pegs
  2. Existing Variants: Primarily focus on variations in the number of pegs, with limited study of structural constraints
  3. Graph-Theoretic Research: Properties of classical Hanoi graphs have been thoroughly studied, but constrained versions remain unexplored systematically

Research Motivation

The author's innovation lies in:

  1. Introducing parity constraints as a natural and meaningful restriction
  2. Systematically studying how constraints alter optimal strategies and growth rates
  3. Establishing a complete graph-theoretic framework connecting optimization problems with graph structure
  4. Revealing the unique position of constrained problems between classical three-peg and four-peg problems

Core Contributions

The main contributions of this paper include:

  1. New Problem Definition: First proposes and formalizes the parity-constrained four-peg Tower of Hanoi problem, defining four canonical optimization objectives:
    • (a) Full tower transfer: from N₁ to N₂
    • (b) Parity separation: odd disks to O, even disks to E
    • (c) Odd to O, even to N₂
    • (d) Odd to N₂, even to E
  2. Coupled Recurrence System: Establishes a coupled recurrence system describing the four optimal move sequences (an,bn,cn,dn)(a_n, b_n, c_n, d_n) (Theorem 1) and proves uniqueness of optimal solutions (Corollary 1)
  3. Explicit Formulas: Derives higher-order recurrence relations (Proposition 2) and closed-form expressions (Proposition 3), revealing periodic growth patterns
  4. Asymptotic Analysis: Proves that all four sequences exhibit "semi-exponential" growth Θ(2n)\Theta(\sqrt{2}^n) (Theorem 3), significantly slower than the 2n2^n growth rate of the three-peg problem
  5. Graph-Theoretic Characterization: Comprehensively analyzes the structural properties of the parity-constrained Hanoi graph PnP^n:
    • Number of vertices: ∣V(Pn)∣=3n|V(P^n)| = 3^n
    • Recursive and closed-form formulas for edge count
    • Connectivity: κ(Pn)=λ(Pn)=2\kappa(P^n) = \lambda(P^n) = 2
    • Planarity: planar only when n≤2n \leq 2
    • Hamiltonicity: all PnP^n are Hamiltonian graphs
    • Chromatic number: χ(Pn)=ω(Pn)=3\chi(P^n) = \omega(P^n) = 3 (perfect graph)
    • Chromatic index: χ′(Pn)=Δ(Pn)=5\chi'(P^n) = \Delta(P^n) = 5
  6. Hierarchical Relationships: Proves H⌈n/2⌉3⊆Pn⊆Hn4H_{\lceil n/2 \rceil}^3 \subseteq P^n \subseteq H_n^4, establishing the position of the parity-constrained graph in the spectrum of classical Hanoi graphs

Methodology Details

Task Definition

Problem Setup:

  • Peg Set: P={N1,N2,O,E}P = \{N_1, N_2, O, E\}
    • N1,N2N_1, N_2: neutral pegs, permitting arbitrary disk placement
    • OO: odd peg, permitting only odd-numbered disks
    • EE: even peg, permitting only even-numbered disks
  • Disks: [n]={1,2,…,n}[n] = \{1, 2, \ldots, n\}, with disk 1 being the smallest
  • State: Quadruple S=(N1,E,O,N2)S = (N_1, E, O, N_2) representing disk sets on each peg, satisfying:
    • Disks on each peg are strictly increasing from top to bottom
    • Each disk is on a peg compatible with its parity
  • Legal Move: Disk dd moves from peg pp to peg qq legally if and only if:
    • dd is the topmost disk on pp
    • qq is empty or its topmost disk is larger than dd
    • Both pp and qq permit dd's parity

Initial State: S0=([n],∅,∅,∅)S_0 = ([n], \emptyset, \emptyset, \emptyset) (all disks on N₁)

Four Optimization Objectives:

  • ana_n: transfer to (∅,∅,∅,[n])(\emptyset, \emptyset, \emptyset, [n])
  • bnb_n: transfer to (∅,[n]0,[n]1,∅)(\emptyset, [n]_0, [n]_1, \emptyset) (parity separation)
  • cnc_n: transfer to (∅,∅,[n]1,[n]0)(\emptyset, \emptyset, [n]_1, [n]_0)
  • dnd_n: transfer to (∅,[n]0,∅,[n]1)(\emptyset, [n]_0, \emptyset, [n]_1)

Recurrence Relation Derivation

Theorem 1 (Coupled Recurrence System):

Core recurrence relations: an=2bn−1+1a_n = 2b_{n-1} + 1

c_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ even} \\ d_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ odd} \end{cases}$$ $$c_n = \begin{cases} b_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ even} \\ b_{n-2} + 2h_{\lfloor(n-1)/2\rfloor}^3 + h_{\lfloor(n-2)/2\rfloor}^3 + 2, & n \text{ odd} \end{cases}$$ $$d_n = \begin{cases} b_{n-2} + 3h_{\lfloor(n-2)/2\rfloor}^3 + 2, & n \text{ even} \\ b_{n-1} + h_{\lfloor(n-1)/2\rfloor}^3 + 1, & n \text{ odd} \end{cases}$$ where $h_m^3 = 2^m - 1$ is the solution to the classical three-peg problem. **Derivation Strategy** (using $a_n$ as example): 1. To move disk $n$ from $N_1$ to $N_2$, two pegs must first be cleared 2. The optimal strategy is to separate the $n-1$ smaller disks by parity to $E$ and $O$ (requiring $b_{n-1}$ steps) 3. Move disk $n$ (1 step) 4. Transfer small disks from $E$ and $O$ to $N_2$ (symmetrically, requiring another $b_{n-1}$ steps) 5. Total: $a_n = 2b_{n-1} + 1$ ### Higher-Order Recurrences and Closed-Form Formulas **Proposition 2 (Higher-Order Recurrence)**: Through elimination, single-variable recurrences are obtained: $$a_n = \begin{cases} a_{n-3} + 5 \cdot 2^{(n-2)/2} - 2, & n \text{ even} \\ a_{n-3} + 7 \cdot 2^{(n-3)/2} - 2, & n \text{ odd} \end{cases}$$ $$b_n = \begin{cases} b_{n-3} + 7 \cdot 2^{(n-4)/2} - 1, & n \text{ even} \\ b_{n-3} + 5 \cdot 2^{(n-3)/2} - 1, & n \text{ odd} \end{cases}$$ Similarly, $c_n$ and $d_n$ satisfy recurrences with periods 5 and 6, respectively. **Proposition 3 (Closed-Form Expressions)**: Defining $\rho(n) = n \bmod 3$ and $\theta(n) = (n - \rho(n))/3$, explicit formulas exist (complex form involving $\rho(n)$, $\theta(n)$, and geometric series). ### Technical Innovations 1. **Coupled System Analysis**: The four objectives are interdependent, requiring simultaneous solution, which is more complex than independent recurrences 2. **Parity Separation Strategy**: Cleverly exploits parity constraints by separating disks of different parities to create movement space 3. **Periodic Pattern Recognition**: Discovers periodicity in recurrences (modulo 3, 5, 6), a direct consequence of parity constraints 4. **Semi-Exponential Growth**: Proves growth rate is $\Theta(\sqrt{2}^n)$, intermediate between polynomial and full exponential, quantifying the constraint effect ## Experimental Setup This paper is purely theoretical research without traditional experiments, but includes: ### Numerical Verification - **Computing First 15 Terms**: Table 1 lists the first 15 values of $h_3^n$, $h_4^n$, $a_n$, $b_n$, $c_n$, $d_n$ - **Verifying Recurrence Relations**: Confirms theoretical formulas match direct calculations ### Visualization Analysis - **Graph Structure Display**: Figure 3 shows complete structures of $P^1$, $P^2$, $P^3$ - **Growth Curves**: Figure 2 displays growth comparison of six sequences on logarithmic scale, verifying semi-exponential growth ### Graph-Theoretic Property Verification - **Small-Scale Verification**: For $n \leq 3$ graphs, directly verifies planarity, Hamiltonicity, and other properties - **Subgraph Relationships**: Figure 5 displays the largest three-peg Hanoi subgraph in $P^3$ ## Experimental Results ### Main Numerical Results **Table 1 Data Analysis**: - $a_{14} = 481$, while $h_3^{14} = 16383$, $h_4^{14} = 113$ - Verifies $h_4^n \leq a_n \leq h_3^n$ - Values of $b_n$, $c_n$, $d_n$ are close but have no fixed size relationship **Growth Rate Verification** (Theorem 2): - $\lim_{k \to \infty} a_{2k}/a_{2k-1} = 27/19 \approx 1.421$ - $\lim_{k \to \infty} a_{2k+1}/a_{2k} = 38/27 \approx 1.407$ - Two-step growth: $\lim_{n \to \infty} a_n/a_{n-2} = 2$ ### Graph-Theoretic Property Results **Vertices and Edges**: - $|V(P^{10})| = 3^{10} = 59049$ - $|E(P^{10})| = 113834$ (Table 2) - Satisfies $|E(H_{10}^3)| = 88572 < |E(P^{10})| < |E(H_{10}^4)| = 3142656$ **Degree**: - Minimum degree: $\delta(P^n) = 2$ (perfect states) - Maximum degree: $\Delta(P^n) = 5$ ($n \geq 3$) - Average degree: $\lim_{n \to \infty} \bar{d}(P^n) = 27/7 \approx 3.857$ **Connectivity**: - Vertex connectivity: $\kappa(P^n) = 2$ - Edge connectivity: $\lambda(P^n) = 2$ - Maximally connected ($\kappa = \lambda = \delta$) **Diameter Bounds**: - $4n - 7 \leq \text{diam}(P^n) \leq 2^{\lceil n/2 \rceil} - 1$ **Coloring**: - Clique number: $\omega(P^n) = 3$ (produced only by moves of disks 1 or 2) - Chromatic number: $\chi(P^n) = 3$ (perfect graph) - Chromatic index: $\chi'(P^n) = 5 = \Delta(P^n)$ (Class 1 graph) ### Key Findings 1. **Precise Characterization of Semi-Exponential Growth**: All four sequences are $\Theta(\sqrt{2}^n)$, a direct consequence of parity constraints 2. **Periodic Behavior**: Recurrence relations exhibit periodicity modulo 3, 5, and 6, reflecting the interaction between parity and the number of pegs 3. **Intermediate Position of Graph**: $P^n$ is structurally strictly between $H_{\lceil n/2 \rceil}^3$ and $H_n^4$ 4. **Perfect Graph Property**: $\omega(P^n) = \chi(P^n) = 3$ indicates $P^n$ is a perfect graph, an interesting property in the Hanoi graph family 5. **Hamiltonicity**: Despite constraints, $P^n$ remains Hamiltonian, with Hamiltonian paths constructible between perfect states ## Related Work ### Classical Tower of Hanoi Research 1. **Three-Peg Problem**: - Optimal solution $h_3^n = 2^n - 1$ known for over a century - Properties of graph $H_n^3$ thoroughly studied (Hinz et al., 2018) 2. **Four-Peg Problem**: - Bousch (2014) confirmed optimal solution recurrence - Frame-Stewart algorithm (1941) 3. **Multi-Peg Problem**: - Optimality for five or more pegs remains open ### Hanoi Graph Research 1. **Structural Properties** (Hinz & Parisse, 2002, 2012): - Planarity: $H_n^4$ planar only when $n \leq 2$ - Hamiltonicity: All $H_n^m$ ($m \geq 3$) are Hamiltonian graphs 2. **Coloring Properties** (Arett & Dorée, 2010; Hinz & Parisse, 2012): - $\chi(H_n^3) = 3$, $\chi(H_n^4) = 4$ - Clique number $\omega(H_n^m) = m$ 3. **Metric Properties** (Klavžar et al., 2001): - Exact formulas for edge count, diameter, etc. ### Constrained Variants 1. **Sierpiński Graphs** (Hinz et al., 2013): - As generating subgraphs of Hanoi graphs 2. **Restricted Hanoi Graphs** (Mehiri, 2024): - Other types of movement restrictions ### Positioning of This Paper This paper is the first to systematically study the impact of **structural constraints** (parity) on the Tower of Hanoi problem, filling the following gaps: 1. How constraints alter optimal strategies and complexity 2. Complete structural characterization of constrained graphs 3. Precise analysis of semi-exponential growth ## Conclusions and Discussion ### Main Conclusions 1. **Optimization Conclusions**: - Optimal solutions for all four objectives can be precisely computed via coupled recurrence systems - Optimal strategies are unique - All solutions have growth rate $\Theta(\sqrt{2}^n)$, significantly slower than three-peg's $\Theta(2^n)$ 2. **Graph-Theoretic Conclusions**: - $P^n$ has $3^n$ vertices with edge count $\Theta(3^n)$ - Maximally connected but not highly connected ($\kappa = 2$) - Planar only at small scales ($n \leq 2$) - Always Hamiltonian and perfect graphs - Strictly between $H_{\lceil n/2 \rceil}^3$ and $H_n^4$ 3. **Theoretical Significance**: - Parity constraints create a new complexity hierarchy - Constraints reduce available moves but increase strategy complexity - Semi-exponential growth is an interesting case of constrained optimization ### Limitations 1. **Single Constraint Type**: Only considers binary parity constraints, not exploring other modular arithmetic constraints 2. **Fixed Peg Count**: Only studies four-peg case, not generalizing to arbitrary peg numbers 3. **Exact Diameter**: Only provides bounds, not exact values 4. **Computational Complexity**: Does not analyze algorithm complexity for computing optimal solutions 5. **Practical Applications**: Does not discuss practical application scenarios ### Future Directions Research directions proposed by the author: 1. **Graph-Theoretic Extensions**: - Spectral parameters (eigenvalues, eigenvectors) - Distance metrics (Wiener index, Hosoya index) - Domination number, metric dimension 2. **Constraint Generalizations**: - Modulo $k$ constraints ($k > 2$) - Multi-group constraints - Mixed constraint types 3. **General Framework**: - $p$ pegs with $k$ restricted clusters - How constraint configurations affect topology 4. **Algorithm Research**: - Efficient computation algorithms - Approximation algorithms - Online algorithms 5. **Application Exploration**: - Resource scheduling - Constraint satisfaction problems - Parallel computing ## In-Depth Evaluation ### Strengths 1. **Strong Problem Innovation**: - First systematic study of parity-constrained Tower of Hanoi - Constraint design is natural and meaningful - Four objectives cover major optimization scenarios 2. **Complete Theoretical Analysis**: - Rigorous derivations from recurrence relations to closed-form formulas - Deep asymptotic analysis revealing essence of semi-exponential growth - Diverse proof techniques (induction, algebraic elimination, asymptotic analysis) 3. **Comprehensive Graph Characterization**: - Systematic study of over a dozen graph-theoretic properties - Rich proof techniques (subgraph embedding, coloring arguments, Hamiltonian path construction) - Clear relationships with classical Hanoi graphs 4. **Clear and Rigorous Writing**: - Well-structured with clear logic - Precise definitions and systematic notation - Figures and tables enhance readability 5. **Deep Results**: - Semi-exponential growth is a new example of constrained optimization - Perfect graph property is surprising - Hierarchical relationship $H_{\lceil n/2 \rceil}^3 \subseteq P^n \subseteq H_n^4$ is elegant ### Weaknesses 1. **Diameter Not Precisely Determined**: - Only provides bounds $4n - 7 \leq \text{diam}(P^n) \leq 2^{\lceil n/2 \rceil} - 1$ - Gap is large, especially for large $n$ 2. **Lacking Algorithm Analysis**: - Does not discuss algorithm complexity for computing optimal solutions - No implementation or pseudocode provided - Closed-form formulas exist but are computationally complex 3. **Limited Generalization**: - Only studies four pegs and binary parity constraints - Does not explore other constraint types or peg numbers systematically 4. **Missing Practical Applications**: - Pure theoretical research without practical application discussion - Does not connect to real problems (scheduling, resource allocation) 5. **Some Proofs Sketchy**: - Some theorems (e.g., Theorem 10) have abbreviated proofs - Derivation of closed-form formulas not fully expanded 6. **Limited Numerical Experiments**: - Only computes up to $n = 14$ - No large-scale numerical verification - Lacks runtime comparison with other methods ### Impact **Contribution to the Field**: 1. Opens new research direction for constrained Tower of Hanoi problems 2. Provides new theoretical case for constrained optimization 3. Enriches theoretical framework of Hanoi graph family **Practical Value**: 1. Theoretical value exceeds practical value 2. May inspire research in constrained scheduling and resource allocation 3. Semi-exponential growth analysis methods may apply to other constrained problems **Reproducibility**: 1. Theoretical derivations are verifiable 2. Recurrence relations easily programmable 3. Graph construction algorithms are clear 4. Lacks code implementation, but principles are explicit ### Applicable Scenarios 1. **Theoretical Research**: - Combinatorial optimization theory - Recursive algorithm analysis - Constraint satisfaction problems 2. **Teaching Applications**: - Teaching case for recurrence relations - Comprehensive example of graph-theoretic properties - Introductory material for constrained optimization 3. **Potential Applications**: - Task scheduling with resource constraints - Storage management with type restrictions - Load balancing in parallel computing 4. **Extension Research**: - Tower of Hanoi with other constraint types - Multi-peg constrained problems - Spectral theory of constrained graphs ## References The paper cites 23 important references, key ones including: 1. **Bousch (2014)**: Confirms optimal solution for four-peg Tower of Hanoi 2. **Hinz, Klavžar & Petr (2018)**: *The Tower of Hanoi - Myths and Maths*, authoritative monograph on Tower of Hanoi 3. **Frame (1941) & Stewart (1941)**: Original Frame-Stewart algorithm papers 4. **Hinz & Parisse (2002, 2012)**: Planarity and coloring properties of Hanoi graphs 5. **Arett & Dorée (2010)**: Coloring and counting of Hanoi graphs 6. **Klavžar et al. (2001, 2013)**: Combinatorial properties of Hanoi graphs and Sierpiński graphs 7. **Mehiri (2024)**: Author's prior work on restricted Hanoi graphs --- **Overall Assessment**: This is a high-quality theoretical paper that systematically studies a novel and meaningful Tower of Hanoi variant. The theoretical analysis is deep and complete, the graph-theoretic characterization is comprehensive, and the results possess certain depth and elegance. Main weaknesses lie in limited generalizability and practical applicability, with some technical details that could be more thorough. The paper makes clear contributions to combinatorial optimization and graph theory, providing new theoretical perspectives on constrained optimization problems.