symmetric strategy in game theory

I will try two new things in this post:

1. I will write seriously about math.

2. Since this post is interesting enough, I will write it in English

Throughout my academic experience, I've managed to meet several

"mathematical games" that have in common the same winning strategy

argument. I will present them blow:

1. Name of game: Pennies on Table

Game laws: your opponent and you put a penny on a round table,

each one in his turn. The pennies must not intersect nor

get out of the boundary of the table.

the one that can't put any more pennies loses the game.

2. Name of game: Determinant Tic-Tac-Toe.

Game laws: your opponent and you have an empty NxN matrix,

your opponent writes 1 on some entry and you write 0 in your

turn. (it does not matter who begins). In the end of the game

you check what the determinant of the matrix is. If it is 0 you

win, else your opponent wins.

3. Name of game: one-dimensional  Tic-Tac-Toe

Game laws: you have a one dimensional array, that is a 1xN matrix.

your opponent and you write 'X' on an entry each in his turn.

whoever write three 'X's in a row win.

I read the third problem in a lovely book by Martin Gardner who was wondering how the games of the two-dimensional 'flatlander' should look like.

(they obviously have to be one-dimensional…)

I will now present the solutions of the problems, so if you want to think about them you should not read the last part.

Pennies on Table:

At first I thought that the radius of the penny and the table is need in order to solve it, but actually you only need to know that the table is larger than the penny….!

The key here is who begin, for the one who begins has the upper hand:

you begin by putting a penny in the exact center. Now, you goal is to make the game radial symmetric: whenever your opponent puts a coin, you put a coin in the exact opposite place related to the center, it is not hard to understand the if the opponent can put his coin then so are you! The game will end in his defeat.

Determinant Tic-Tac-Toe:

I want to leave for you the special cases on N=2,3

The case N=3 is very interesting and was presented to me originally, but is quite simple.

We will call the players 1 and 0.

It is quite surprising but 0 always have a winning strategy, I was surprise because anyone who know enough linear algebra or measure theory know that 'most' of the binary (with 1and 0 entries) matrices are invertible! [1]

For general N you have to split to two cases:

N>3 is even.

if 1 begins then 0 has a winning strategy , all he have to do is to divide the matrix into upper half and lower half. When 1 writes on an entry then 0 write on the mirror entry. For example if N=4 and one writes on the (1,1) then 0 writes 0 on the (1,4) entry…

through this way, when the game is finished:

the sum of row 1+row N=(1,1,…1)

and the sum of row 2+row N-1= (1,1,…,1)

which imply that the rows are linearly dependent and therefore the determinant is 0.

N is even and 0 begins

Amazingly the symmetry strategy is not ruin! Because the opponent is enforced to write 1!

You begin with a 0, even if 1 know about your vicious symmetric plan, he cannot do any thing because he cannot touch the mirror entry with his 1,

So he will have to write 1 in other entry and you carry on by your same strategy…

Again I want to leave for you the interesting case where N is odd, which have a slight twist. (but still a winning strategy for 0!)

One-dimensional  Tic-Tac-Toe:

Again like many similar games the parity of N is important, if N is odd the one who begins  has a strategy  for the win: He first but he's X in the middle of the board whenever the opponent writes X on an entry you put X on the mirror part of the array. It is easy to see that he
will ll reach three row of 'X' s first.

I will leave with the amazing fact ( that was written in the book) :

The one dimensional tic-tac-toe the case when N is even is quite complicated and

there is no obvious winning strategy when N is large enough (such that is promised by Zermelo Theorem) despite the simplicity of the game.

Life is tough for flatlanders!

[1] J. Komlos, On the Determinant of (0,1) Matrices, Studia Scientiarum Mathematicarum Hungarica 2 (1967)