To: aflb-all@polya.stanford.edu Subject: AFLB talk Date: Sat, 22 Oct 88 18:20:21 PDT From: Anil R. Gangolli <gangolli@wolvesden.stanford.edu>
Periodicity Results for Some Simple Octal Games Thane Plambeck Taking and breaking games are a class of impartial games played by removing beans from a pile and leaving the pile in zero or more parts. Following Conway, the rules for a taking and breaking game can specified as a numeric code which describes the number of beans one can take and the number of piles into which one can break a pile. The games which have Conway codes consisting only of the octal digits 0...7 are known as octal games. The theorem of Sprague and Grundy tells us that every instance of an impartial game is equivalent to an instance of the game Nim. The instances of a taking and breaking game thus specify a sequence of Nim values. It is conjectured [R. Guy] that all finitely-specified octal games have ultimately periodic Nim-value sequences, but the conjecture is not known to hold even for all octal games with 3 or fewer code digits. Slightly fewer than sixty of these now remain unsettled. We present techniques for giving computational proofs of the periodicity of some of these sequences and consequent periodicity results for three such games. No background in the theory of impartial games will be assumed. This is joint work with Anil Gangolli.