Geography Played on Products of Directed Cycles
Richard J. Nowakowski, David G. Poole · 1997
We consider the game of Geography played on G = C n x C m , the product of two directed cycles. The analysis is easy for n = 2 and in the case where both n and m are even. Most of the paper is devoted to solving the game on the graphs C n x C 3 . 1. Introduction The game called Kotzig's Nim in Winning Ways [Berlekamp et al. 1982] and Modular Nim in [Fraenkel et al. 1995] consists of a directed cycle of length n with the vertices labelled 0 through n — 1, a coin placed initially on vertex 0, and a set of integers called the move set. There are two players, who alternate moves; a move consists of moving the coin from the vertex i on which it currently resides to vertex i + m mod n, where m is a member of the move set. However, the coin can only land on a vertex once. Thus, the game is finite. The last player to move wins. Most of the known results concern themselves with move sets of small cardinality and consisting of small numbers (see p. 481 of Winning Ways, and [Fraenkel et al. 1995]). Obviously, this game can be extended to more general directed graphs, the move set being indicated by directed edges, for clarity. This has become known as Geography [Fraenkel et al. 1993; Fraenkel and Simonson 1993]. The Grundy value of a game G , denoted g(G), is either P for a previous-player win or N for a next-player win. Throughout, we call the first player Algois and the second Berol.