Latin Squares Game
I just invented a two-player game. To start, you have an empty n by n board. When it’s your turn you must write an integer between 1 and n into an empty cell on the board. Your integer has to differ from the integers that are already present in the same row or column. If you finish filling up the board, you will get a Latin square and the game will be a tie. The person who doesn’t have a move loses. What is the best strategy?
Let’s see what happens if n is 2. The first player puts any number in one of the four corners of the 2 by 2 board. The second player wins by placing a different number in the opposite corner.
I played this game with my son Sergei Bernstein on a 3 by 3 board. We discovered that the first player can always win. Since this game is so much fun, I’ll leave it to the reader to play it and to find the winning strategy for the first player.
Can you analyze bigger boards? Remember that this game has many symmetries. You can permute rows and columns. Also, you can permute numbers.
While we were playing Sergei invented two theorems.
Sergei’s theorem 1. If n is odd the first player can guarantee a tie.
Proof. In the first move the first player writes (n+1)/2 in the center cell. If the second player puts number x in any cell the first player puts number n+1−x into the cell that is rotationally symmetric to the second player’s cell with respect to the center. With this strategy the first player will always have a legal move.
Sergei’s theorem 2. If n is even the second player can guarantee a tie.
Proof. If the first player puts number x in any cell the second player puts number n+1−x into the cell that is vertically symmetric to the first player’s cell with respect to the vertical line of symmetry of the board. With this strategy the second player will always have a legal move.
As you play the game, let me know if you develop any theorems of your own.
Share:
Jorge Nuno Silva:
Please check my G4G10 paper in the Gift Book.
1 April 2012, 9:06 am