# Game: Avoid the Gaussian primes

Here is a 2-player game played on a region of the Gaussian integers, $\mathbb{Z}[i]$. Initially four points are colored, opposite corners of an $X$ by $Y$ rectangle: $0 + 0i$ and $X + Yi$ are colored red, and $0 + Yi$ and $X + 0i$ are colored blue. A move by a player of color $C$ consists of selecting a red point and a blue point, and coloring the previously uncolored "midpoint" color $C$, where the midpoint of $z+w$ is $\lfloor{ (z+w)/2 } \rfloor$. The game ends when a player loses by coloring a Gaussian prime, that is, a point $a + bi$, which, if either $a$ or $b$ is zero, is a prime of the form $4n+3$, or otherwise if its norm $a^2+b^2$ is a prime.

Example. $X=51$, $Y=34$. Red moves first and colors $25 + 0i$ red, the midpoint of the points on the real axis. Blue would not want to color the midpoint of $0 + 34i$ and $25 + 0i$, because that is $12 + 17i$ which is prime (433). So suppose Blue instead colors the midpoint of the points on the imaginary axis, $0 + 0i$ and $0 + 34i$, which is $0 +17i$. Red could now select the midpoint of this blue point and $25 + 0i$, which is $12 + 8i$. And so on.

Will the game always end with a loser?

If both $X$ and $Y$ are of the form $2p$ or $2p+1$ with $p$ a prime $4n+3$, then Red is forced to lose on the first move. Are there other values of $X$ and $Y$ for which the game can be fully analyzed?

Is there any hope analyzing who wins this game (under best play) for arbitrary $X$ and $Y$?

This is original and quite possibly worthless, so caveat lector!

Edit1. See the suggested simplification by Michael Albert in the Comments: dispense with colors, letting each move select any two points.

Edit2. Thanks for all the interesting comments. It now seems to me this game is hopelessly complicated to analyze, perhaps PSPACE-complete in terms of complexity. The monochromatic version is much simpler but removes the adversarial aspect that is the essence of a game. I don't think Milton-Bradley will be knocking on my door!

-
I don't understand how you are calculating your midpoints. How is 25 the midpoint of 0 and 51? –  Gerry Myerson Jul 12 '10 at 13:02
Sorry, I should say not the closest, but the closest Gaussian integer to the lower-left; i.e., take the floor of each component. –  Gabe Cunningham Jul 12 '10 at 13:12
@Gerry: I meant that ((0+0i)+(51+0i))/2=(51/2+0i)=25+0i. Add, divide by 2, take the floor of the real and imaginary parts. Yes, as Gabe explained. Sorry for not being so clear. –  Joseph O'Rourke Jul 12 '10 at 13:32
It seems to me that the colouring could be a bit of a distraction. That is, why not consider the impartial game (where we can choose any two distinct points whose "midpoint" is not yet marked, and add the midpoint). Since every point in the rectangle will now be accessible, the game will certainly end, and the issue becomes whether it is a first or second player win. –  Michael Albert Jul 12 '10 at 20:21
Perhaps even the monochromatic version, in 1D, with primes rather than Gaussian primes, should be analyzed before more complicated versions. So, starting with {0,8}, Player2 wins: Player1 must choose (0+8)/2=4, Player2 can choose (4+8)/2=6, and now Player1 is stuck: (0+4)/2=2, (0+6)/2=3, (4+6)/2=5, (6+8)/2=7 are all prime. –  Joseph O'Rourke Jul 12 '10 at 22:36

This is only a heuristics, but I would assume that the game either ends after a few steps, or the outcome is determined simply by the parity of $(X+1)(Y+1)$ minus the number of gaussian primes in the rectangle. This is certainly the case if at the end of the game all non-primes are taken. So the player for which this heuristics predicts a win should try to play in such a way that all points of the rectangle are midpoints of lines with endpoints of different colour. Since most gaussian integers are not prime one of the basic heuristics of additive combinatorics predicts that the only way to avoid this is to have some extremely large Fourier coefficient, that is, the board looks like having red and blue stripes. But by taking midpoints of red and blue points one of the player can prevent this from happening, provided he has a sufficient number of choices left. This means that either the game ends early, or it should continue until all non-primes are taken, in which case the winner is determined by the aforementioned parity.