Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Brian Nakamura, Rutgers University, bnaka {at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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.

See: http://www.math.rutgers.edu/~bnaka/expmath/