SIGMA-GAME, SIGMA(-GAME AND 2-DIMENSIONAL ADDITIVE CELLULAR-AUTOMATA())

The sigma-game, introduced by Sutner, is a combinatorial game played o n a graph G and is closely related to the sigma-automaton first studie d by Lindenmayer. A related game is the af-game. In this article, we s tudy the sigma-game (sigma(+)-game) played on the rectangular grid {1, 2,..., m}x{1, 2,..., n}. We analyse the sigma(+)-game by studying the divisibility properties of the polynomials p(n)(lambda) which we have introduced here. (Similar polynomials were earlier studied by Sutner). We give a simple algorithm for finding the number of solutions for th e sigma(+)-game and also give a necessary and sufficient condition for the existence of a unique solution for the sigma(+)-game, thus partia lly answering a question posed by Sutner. Further, we compute the numb er of solutions of the sigma(+)-game when one of n, m is of the form 2 (k)-1. Finally, we look at the sigma-game and the sigma(+)-game played on cylinders and tori and give necessary and sufficient conditions fo r the existence of unique solutions for these games.