Grundy Functions and Linear Games
Masahiko Sato · Publications of the Research Institute for Mathematical Sciences · 1971
As is well known, the idea of Grundy functions and Grundy's theorem are very important and useful when we consider the Cartesian product of games.Of course, there are several proofs for Grundy's theorem. 1) Yet, we think, these proofs do not answer well the question why the binary sum operation (bitwise addition without carry) must appear in the theorem.An answer for it will be given in this paper.Mathematically, a game is nothing but a binary relation on a set.Accordingly, its mathematical structure can not be so rich.In §3, we shall introduce the notion of linear games with richer structures.And we shall prove that any game G is embeddable into a linear game i(C), and that the Grundy function on L(G) is a linear map from L(G) to ]V. 2) This will easily lead us to a proof of Grundy's theorem.In §1, as a preparation for the following § §, we shall view basic properties of games.In §2, we shall introduce the notion of compatibility, and extend it to the notion of semicompatibility.Using the notion of semicompatibility, we shall give a characterization of Grundy functions.This, we think, will clarify the meaning of Grundy functions.In §4, we shall extend the results in §3, and show that the Grundy function on any linear game is a linear map.