Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Cofinite Induced Subgraph Nim
Speaker: Scott Garrabrant, UCLA
Date: Thursday, October 4, 2012 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Nim is a famous impartial combinatorial game played with 3 heaps of beans. Two players alternate taking any positive number of beans from any one heap. When all heaps are empty, the player whose turn it is to play has no move and is therefore declared the loser. The optimal strategy for Nim exhibits a fractal structure in that a player can win from the position (x,y,z) if and only if they can win from the position (2x,2y,2z). A natural way to modify the game of Nim is to forbid either player from moving to a given position. This modification destroys the original fractal structure of Nim, but replaces it with a new fractal structure. We will investigate properties of the optimal strategy in this modified Nim.