## Puzzle 6 - Grid Game

Have an interesting puzzle? Let's hear it!

### Puzzle 6 - Grid Game

Given a m*n grid (with m rows and n cases per row) and the beginner, we will try to determine who win. In the following solution, (i,j) is the jth square of the ith row.

There is a finite (but positive) number of cases that I haven't solved yet.

General Case
Spoiler! :
When m and n are both big (other cases will be treated or mentionned below ; the condition on m here is always $m \geq 3$), Randall always has a winning strategy. This strategy consist in the construction of a barrier of blocked squares that cannot be the greatest of the row. A square which have to be blocked is said protected. The strategy is always :
-when Mike write a number in a protected square, Randall blocks this case by writing a greater number in an unprottected square in the same row,
-when M write a number in an unprotected square, but in a row that contains unblocked protected squares, R blocks any protected square of the row by writing a smaller number
-esle, if he can, R writes any number in any square which is not in the same row that an unblocked protected square
-and if he can't, it's more complicated.
Of course there is never more protected squares than unprotected squares in one row.

When Mike begins
n even, $n \geq 4$
The protected squares are :
$(1,i)_{1\leq i \leq \frac{n}{2}}$, $(2,\frac{n}{2})$, $(2,\frac{n}{2}+1)$ and $(3,i)_{\frac{n}{2}+1 \leq i \leq n}$
For a 4*6 it is :
X X X _ _ _
_ _ X X _ _
_ _ _ X X X
_ _ _ _ _ _
This is the simplest case, just using the general strategy works.

n odd, $n \geq 7$
Let $n=2k-1$.
The protected squares are :
$(1,i)_{1\leq i \leq k}$, $(2,k-1)$, $(2,k)$, $(2,k+1)$ and $(3,i)_{k+1 \leq i \leq n}$.
For a 3*9 it is :
X X X X _ _ _ _ _
_ _ _ X X X _ _ _
_ _ _ _ _ X X X X
When R cannot play with the general strategy, there are three possibilities :
-if all the squares are writen, R do nothing and win,
-if there is one empty protected square and a full unprotected square in the same row, R blocks the PS by writing a smaller number,
-else there is an empty row, R write any number in an unprotected square of this row. As n is odd, there is still more US than PS in this row.

When Randall begins
n odd
The strategy is exacly the same as before. The fisrt turn, R plays as if M has just play in a "normal" square.

n even, $n \geq 10$
Let n=2k. The protected squares are :
$(1,i)_{1\leq i \leq k-1}$, $(2,i)_{k-1 \leq i \leq k+2$ and $(3,i)_{k+2 \leq i \leq n}$.
For a 3*12 it's :
X X X X X _ _ _ _ _ _ _
_ _ _ _ X X X X _ _ _ _
_ _ _ _ _ _ _ X X X X X
This way, there are always stricly more unprotected square than protected in the same row, so we can use the general strategy.

Particular general cases
Spoiler! :
Some cases aren't in the general case but can still be solved with the same strategy :

m*5, $m \geq 4$
The protected squares are :
X X _ _ _
_ X X _ _
_ _ X X _
_ _ _ X X

Randall begins, m*8, $m \geq 4$
The protected squares are :
X X X _ _ _ _ _
_ _ X X X _ _ _
_ _ _ X X X _ _
_ _ _ _ _ X X X

Randall begins, m*6, $m \geq 5$
The protected squares are :
X X _ _ _ _
_ X X _ _ _
_ _ X X _ _
_ _ _ X X _
_ _ _ _ X X

Randall begins, m*4
This time, M wins. All he has to do is to protect the first and last column. For a 3*4 it is :
X _ _ X
X _ _ X
X _ _ X

m*3
Idem, but M has only 1 column to protect, so he wins even if he begins.

Other cases
Spoiler! :
1*n, m*1 and m*2
M plays randomly and wins.

2*n, Randall begins
Whatever R plays, M write a number in the case just below or just above such that the order of the two rows are identicals. M wins.

2*n, Mike begins, $n \geq 4$
Let $\sigma$ such that $\sigma(n-1) = 1, \sigma(n) = 2, \sigma(i) = i+1$. When M plays in the square $(1,i)$, R plays in $(2,\sigma(i))$, and when M plays in the square $(2,i)$, R plays in $(1,\sigma^{-1}(i))$, using the same principle as M just above. R wins.

3*6, 4*6 and 3*8 when Randall begins, and 3*5
To be done.
de-mil
Kindergarten

Posts: 2
Joined: Sun Mar 04, 2012 5:58 am

### Re: Puzzle 6 - Grid Game

Wow that's very detailed!!

The blocking strategy seems to work for a lot of cases giving Randall the win! I wonder what the general theorem would be?

If Mike starts first then Randall wins if and only if .... ???

I didn't actually think about Problems 2 & 3 in detail before posting them!
Math - It's in you to give.

SpikedMath
Site Admin

Posts: 133
Joined: Mon Feb 07, 2011 1:31 am
Location: Canada

Return to Puzzles and Riddles

### Who is online

Users browsing this forum: No registered users and 1 guest