In the previous two blogs, we see that a nominal game (i.e. player who makes the last move wins) can be defined as G=(GL|GR) where GL (R resp.) is the set of possible configurations after L (R resp.) makes the first move.
Indeed, we can add two nominal games G=(GL|GR) and G'=(G'L|G'R) together and form a new nominal game. Symbolically, it is
G+G'=(GL+G', G+G'L | GR+G', G+G'R)
where the sum is defined recursively.
What does it mean exactly? Indeed, we simply put the two games side by side, and at each step, the player can make a move on either game.
What is the effect on the games?
Suppose both G and G' are games that the second player wins.
If the first player moves on G, then the second player moves on G; if the first player moves on G', then the second player also moves on G'. The second player is still the second winner on both G and G' and therefore he wins on both games. In other words, G+G' is still a second player's game.
Suppose both G and G' are games that L (R resp.) wins.
It is trivial that L (R resp.) is still the winner.
Suppose both G and G' are games that the first player wins.
It is a bit more complicated. Consider the following two games:
- G(n) consists of a board with n pieces on it. Two players in term takes a piece from the board. The player who takes the last piece wins.
- G'(n) consists of a board with n piece on it. Two players in term can take arbitrary number (possibly all) of pieces from the board. The player who takes the last piece wins.
G(1)+G(1)=G(2), so the sum of two first player's games can be a second player's game.
G(1)+G'(2) is, however, a first player's game. At the very first move, the first player will take away a piece from G'(2) and the new configuration is G(2) with himself as the second player. Therefore, he wins.
Can you figure out the remaining four cases?
No comments:
Post a Comment