Thursday, December 20, 2012

Sum of games (1)

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

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.
Obviously, G(n) is a first player's game if n is odd but a second player's game if n is even, and G'(n) is always a first player's game-the first player can take everything at the first move.

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?