New Games Related to Old and New Sequences

Combinatorial game theory provides a rigorous framework for analyzing two-pile subtraction games, where the governing move constraints are defined by a function of the current pile sizes. The primary objective of this research is to establish a universal mathematical structure for identifying second-player winning positions, known as P-positions. By defining these positions through complementary sequences, the analysis identifies three critical criteria—positivity, monotonicity, and semi-additivity—that must be satisfied by the constraint function to ensure a predictable game state. This theoretical foundation allows for the classification of diverse integer sequences, including the Hofstadter and Prouhet-Thue-Morse sequences, within a unified strategic model.

The findings demonstrate that these games are not merely abstract puzzles but are deeply connected to established mathematical sequences that dictate optimal play. While specific instances of these games allow for winning strategies to be computed in polynomial time through the application of specialized numeration systems, the broader computational complexity of the entire class remains a subject of ongoing inquiry. The research highlights that the interplay between move constraints and sequence generation is essential for determining the viability of winning strategies in complex, multi-pile environments.

This analysis contributes to the broader field of combinatorial game theory by synthesizing foundational concepts such as Sprague-Grundy functions and the properties of Wythoff’s Nim. By formalizing the relationship between constraint functions and P-positions, the work provides a generalized methodology for game design and strategic evaluation. Future research is expected to expand these principles to games involving more than two piles and to further refine the algorithmic complexity associated with these mathematical structures, ultimately deepening the understanding of how simple move rules evolve into complex, predictable game dynamics.