## Wednesday, September 17, 2008

### Counting Games:Relative-Primality & Grids

There are m players, m = any positive integer.
Take an n-by-n grid, where n is such that m divides n^2.
Players take turns placing the integers 1 to n^2 (in order) into the
grid, if possible, such that player-k places those integers congruent
to k(mod m) into the grid, such that:
the integer, j, is placed into a cell where all adjacent (up, down,
left, right) cells (which already contains integers) contain only
integers which are relatively prime to j.
The last player who is able to place an integer somewhere into the
grid is the winner.
(If the grid is filled in completely, then player m wins.)
A sample game:
1 4 5
2 7 3
* 6 *
(The player placing the 7 has won.)

A little related strategy:
If you are player-m, then all of your integers will be divisible by m.
So you would be best off trying to keep yourself from getting into a
situation where all available cells are next to cells you yourself
Placing your integers (I would guess) if possible, into only cells
which are an even number of positions (left, right, up, down) from
other cells you have already filled, would seem like a good idea in
most cases.
(Example: If you are playing on a chess-board, place your integers
only on the black squares, if there is no better reason to do
otherwise.)
And, if you are not player-m, you might want to try to force player-m
to have no place to put an integer by placing your integers
nonadjacently, in general, to any integers divisible by m, filling up