Chomp, recurrences and chaos(?). In this article, dedicated with admiration and friendship to chaos and difference (and hence recurrence) equations guru Saber Elaydi, I give a new approach and a new algorithm for Chomp, David Gale’s celebrated combinatorial game. This work is inspired by Xinyu Sun’s “ultimate-periodicity” conjecture and by its brilliant proof by high-school student Steven Byrnes. The algorithm is implemented in a Maple package BYRNES accompanying this article. By looking at the output, and inspired by previous work of Andries Brouwer, I speculate that Chomp is chaotic, in a yet-to-be-made-precise sense, because the losing positions are given by “weird” recurrences.
Keywords for this software
References in zbMATH (referenced in 6 articles , 1 standard article )
Showing results 1 to 6 of 6.
- Garrabrant, Scott M.; Friedman, Eric J.; Landsberg, Adam Scott: Cofinite induced subgraphs of impartial combinatorial games: an analysis of CIS-Nim (2013)
- Fraenkel, Aviezri S.: Aperiodic subtraction games (2011)
- Friedman, Eric J.; Landsberg, Adam S.: On the geometry of combinatorial games: a renormalization approach (2009)
- Friedman, Eric J.; Landsberg, Adam Scott: Scaling, renormalization, and universality in combinatorial games: The geometry of Chomp (2007)
- Ito, Hiro; Nakamura, Gisaku; Takata, Satoshi: Winning ways of weighted poset games (2007)
- Zeilberger, Doron: Chomp, recurrences and chaos(?) (2004)