Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Aperiodic Subtraction Games
Speaker: Nathan Fox, Rutgers University
Date: Thursday, May 1, 2014 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Subtraction games are a class of impartial combinatorial games whose positions correspond to nonnegative integers and whose moves correspond to subtracting one of a fixed set of numbers from the current position. Though they are easy to define, subtraction games have proven difficult to analyze. In particular, few general results about their Nim values are known. Nim values are one of the most fundamental numerical properties of games; in particular, a position's Nim value is zero if and only if it is a losing position. One question that can be asked is whether there exists a subtraction game whose sequence of Nim values is bounded and not eventually periodic. In this talk, we will construct an example of such a game where all of the Nim values are zero, one, or two.