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
have already filled.
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
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
the non-m-multiple-adjacent cells first.
Leroy Quet

No comments: