Thursday, December 20, 2012

Sum of games (2)

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

Suppose G is a first player's game and G' is a second player's game, what is G+G'?
It is still a first player's game. The first player moves on G at the first step. Note that the first player can force the opponent to be the first player on G'. Why? Because G is a first player's game, and so sooner or later the second player cannot make a move on G and have to move on G'.

Suppose G is L's game and G' is a first player's game.
Consider the following game:
  • L(n) consists of a board with n pieces. L can take away any number of pieces at his turn but R can only take away a piece. Obviously, L(1) is a first player's game but L(n) is always L's game.
L(2)+L(1) is a first player's game. No matter L or R makes the first move, he will take away a single piece from L(2) and win the game.
L(3)+L(1) is L's game. If L makes the first move, he will take away two pieces from L(3) and win; if R makes the first move, the new configuration is either L(3) or L(2)+L(1) with L being the first player, so L wins.

Suppose G is L's game and G' is a second player's game.
Suppose R is the first player. If R takes G' then he will lose on both G and G'. However if R takes G which is L's game, then sooner or later he will be forced to make a first move on G' and he will also lose. Suppose L is the first player, then obvious he will make his first move on G and force R to be the first player on G', and then he can win. G+G' is L's game.

In the last two cases, if G is R's game, the argument is similar.

Suppose G is L's game and G' is R's game.
Consider L(n) and R(n), i.e., the game identical to L(n) but the roles of L and R interchanged.
L(2)+R(2) is the second player's game.
L(3)+R(2) and L(2)+R(3) are both first player's games. No matter who moves first, he can change it to L(2)+R(2) with himself being the second player.
L(4)+R(2) is surely L's game. If L moves first, he will make it L(2)+R(2).
L(2)+R(4) is surely R's game.

We can see that L(n)+R(n) is always a second player's game. It is because the second player can make a mirror copy of the first player's move, and therefore he will never be the one who cannot make a legitimate move.
Indeed, if G=(GL|GR) is a game, then we define a new game -G=(-GR|-GL), i.e. the game with the role of L and G interchanged, then G + (-G) is always a second player's game.

Suppose G1=G+(second player's game). We have
  1. If G is a first player's/second player's/L's/R's game then G1 retains the same property.
  2. G1+(-G)=(second player's game).
Technically speaking, the set of second player's games forms an identity element under the addition operations.