No longer updated!

## Monday, July 28, 2008

### Tick-Tack-Toe

David and Angela play a game of tick-tack-toe. In this game, the players try to get three circles or three crosses in a row (horizontal, vertical, or diagonal).

* A player always tries to win: if a player can place his own symbol (X or O) in a row which already contains two of his own symbols, he will do so.
* A player always tries to avoid that his opponent wins: if a player can place his own symbol (X or O) in a row which already contains two of the symbols of his opponent, he will do so.

Of course, the first rule has precedence over the second rule, because the game can be won in this way.

In the game shown above, 6 moves have been done. David plays with crosses (X) and Angela plays with circles (0). However, we don't know who started the game.

The Question: Who will win this game?

Answer: It is clear that if we know who made the sixth move, we also know who can make the seventh move and wins.

If Angela (circles) has made the sixth move, there are three possibilities for the situation after five moves:

Based on the rules of the game only possibility 1 could have resulted in the situation after six moves. In that case, there are three possibilities for the situation after four moves:

Based on the rules of the game, David (crosses) would have made the winning move, which however didn't happen. From this we can conclude that David did not make the fifth move and Angela did not make the sixth move. So, it must have been David who made the sixth move and Angela can make the seventh, winning move!

To check that David could indeed have made the sixth move, we look at the the following three possibilities after five moves:

Based on the rules of the game, only possibility 3 can result in the situation after six moves. So, David could indeed have made the sixth move.