The Parity-Constrained Four-Peg Tower of Hanoi Problem and Its Associated Graph
Abstract
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.