8
$\begingroup$

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.


                alt text
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!

$\endgroup$
14
  • 1
    $\begingroup$ Sorry, I should say not the closest, but the closest Gaussian integer to the lower-left; i.e., take the floor of each component. $\endgroup$ Jul 12, 2010 at 13:12
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 12, 2010 at 13:32
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 12, 2010 at 20:21
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 12, 2010 at 22:36
  • 1
    $\begingroup$ Good point about the 1D impartial version. I might follow that up later today. One further thought (pertinent to the original version as well), in the case where (x+y)/2 is not in the lattice it might be interesting to allow the mover to choose which nearest lattice point gets marked. $\endgroup$ Jul 13, 2010 at 22:04

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.