Skip to main content
3 of 8
Had sense of win/lose flipped in example!
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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.

Let $X \ge Y$. If $Y=0$, say that the game starts with just two points colored. Then the game could end in a forced draw, e.g., with $X=8$: $(4, 6, 5)$. Assume $Y > 0$. Will the game always end with a winner?

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. [Sorry if you read the first version of the preceding sentence, which was incorrectly stated.] 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!

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958