December 20, 2008

Tic Tac Toe

Two players are playing a game and take alternating turns. There are 9 cards on the table with numbers from 1 to 9. On each turn, a player picks one card from the table. The first player to have 3 cards that total a sum of 15 wins. If no one can after all cards are distributed, then it's a draw. Can you tell who wins, assume both players are highly and equally intelligent and what is the winning strategy ?
Source: Petr Mitrichev's Blog

Answer: Draw

Solution:
If player 1 picks any card except for 5 then there are three ways he can pick second card in order to total 15. Player 2 will block one way in his following turn. Leaving two options for player 1. For any way that player 1 chooses, he has just one way now to total 15. Player 2 will block that way. Player 2 has blocked all ways of player 1 so far. But in the two moves so far player 2 has one way to reach 15. Player 1's next turn can block that. But, This analysis is hard to follow and unclear to see for all the possible combination.

This problem can be modeled in form of tic-tac-toe by constructing a 3 x 3 magic square, as follows:
4  9  2
3  5  7
8  1  6
Now all rows, diagonals, columns sum to 15. So the problem is reducible to playing a tic-tac-toe. Its easy to see that if two players are highly and equally intelligent then the game would result in a draw.

1 comment:

  1. We will then go on to show that, in two dimensions, that the converse is also true. That is any combination of translation and rotation can be represented by a single rotation provided that we choose the correct point to rotate it around. help me with math

    ReplyDelete