Perturbed Nim

04/19/2011 - 12:15pm
04/19/2011 - 1:10pm
Scott Garrabrant (Pitzer College)

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.

Millikan 208 (Pomona College)