A and B get an unlimited number of identical circular coins. A and B take turns placing the coins on a finite square table, in such
a way that no two coins overlap and each coin is completely on
the table (that is, it doesn’t stick out). The person who cannot
legally place a coin loses. Assuming at least one coin can fit on the
table, prove that A has a winning strategy.
Like in the previous problem the winning strategy can be defined if there is an advantage for the final move that can be determined before hand. We can do this by assuming pairs of moves to be copies of each other bit the beginning and last moves to be different. By copies, we mean that if one player puts a coin on the table, then the other player puts the coin on the symmetrically opposite side of the table. The one place that is unique is the center and that should be the first move.
Tic Tac Toe for mathematicians:
On a 5 x 5 board, A and B take turns marking squares. A always writes an X in a square and B always writes O. No square can be marked twice. A wins if she can make one full row, column or diagonal containing only Xs. Can B prevent A from winning ?
The answer to this question is yes. We will see how if we use the cheatsheet in Pranav Sriram's explanation. The board is marked as follows:
5 9 11 9 6
8 1 1 2 7
12 4 2 12
8 4 3 3 7
6 10 11 10 5
Since each number from 1 to 12 appears in 2 squares, B can ensure that he always marks at least one square of each number ( if A marks an X in a square with number i, B puts an O in the other square marked i). Each row, column and diagonal contains a pair of squares having equal numbers. This equal number guarantees that B will make a mark in every row, column and diagonal thus preventing A from winning.
The numbering may strike one as having come out of a wild permutation guess but in fact, this is one of those solutions that has a very intuitive explanation. There are 5 rows, 5 columns and two diagonals for a total of 12 winning lines. We can only make 12 pairs of numbers. since there are twenty five squares. With a pairing strategy that keeps one pair in each row, column and diagonal, we can use a similar number as shown above. We can start with the inner 3 x 3 square, covering its border and then fill the outer perimeter Furthermore, the game of Tic Tac Toe can be generalized to getting k squares in a row on a m x n board In all these cases, the player B can have a similar winning strategy. However whether the player making an opening move has a winning strategy is an open problem.
There are other games also possible with the same 5 x 5 board and two players. For example, take the problem that appears in IMO shortlist 1994
A and B play alternatively on a 5 x 5 board. A always enters a 1 into an empty square, and B always enters a 0 into an empty square. When the board is full, the sum of each of the nine 3 x 3 sub board is calculated and A's score is chosen as the highest among them all. What is the largest score A can make, regardless of the responses of B
The intuitive answer here is the score of 6. How do we say so ? Because for every move that A makes in a sub board, B can pair a 0. This takes up two sets of rows leaving the fifth row untouched in the board. Since any three by three sub board contains at least two of the row pairs, B can force at least three zeros leaving the maximum score for A to be 6.
a way that no two coins overlap and each coin is completely on
the table (that is, it doesn’t stick out). The person who cannot
legally place a coin loses. Assuming at least one coin can fit on the
table, prove that A has a winning strategy.
Like in the previous problem the winning strategy can be defined if there is an advantage for the final move that can be determined before hand. We can do this by assuming pairs of moves to be copies of each other bit the beginning and last moves to be different. By copies, we mean that if one player puts a coin on the table, then the other player puts the coin on the symmetrically opposite side of the table. The one place that is unique is the center and that should be the first move.
Tic Tac Toe for mathematicians:
On a 5 x 5 board, A and B take turns marking squares. A always writes an X in a square and B always writes O. No square can be marked twice. A wins if she can make one full row, column or diagonal containing only Xs. Can B prevent A from winning ?
The answer to this question is yes. We will see how if we use the cheatsheet in Pranav Sriram's explanation. The board is marked as follows:
5 9 11 9 6
8 1 1 2 7
12 4 2 12
8 4 3 3 7
6 10 11 10 5
Since each number from 1 to 12 appears in 2 squares, B can ensure that he always marks at least one square of each number ( if A marks an X in a square with number i, B puts an O in the other square marked i). Each row, column and diagonal contains a pair of squares having equal numbers. This equal number guarantees that B will make a mark in every row, column and diagonal thus preventing A from winning.
The numbering may strike one as having come out of a wild permutation guess but in fact, this is one of those solutions that has a very intuitive explanation. There are 5 rows, 5 columns and two diagonals for a total of 12 winning lines. We can only make 12 pairs of numbers. since there are twenty five squares. With a pairing strategy that keeps one pair in each row, column and diagonal, we can use a similar number as shown above. We can start with the inner 3 x 3 square, covering its border and then fill the outer perimeter Furthermore, the game of Tic Tac Toe can be generalized to getting k squares in a row on a m x n board In all these cases, the player B can have a similar winning strategy. However whether the player making an opening move has a winning strategy is an open problem.
There are other games also possible with the same 5 x 5 board and two players. For example, take the problem that appears in IMO shortlist 1994
A and B play alternatively on a 5 x 5 board. A always enters a 1 into an empty square, and B always enters a 0 into an empty square. When the board is full, the sum of each of the nine 3 x 3 sub board is calculated and A's score is chosen as the highest among them all. What is the largest score A can make, regardless of the responses of B
The intuitive answer here is the score of 6. How do we say so ? Because for every move that A makes in a sub board, B can pair a 0. This takes up two sets of rows leaving the fifth row untouched in the board. Since any three by three sub board contains at least two of the row pairs, B can force at least three zeros leaving the maximum score for A to be 6.
No comments:
Post a Comment