Return to Question

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 http://cs.smith.edu/%7Eorourke/MathOverflow/ExampleGaussian.jpg

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!

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.

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!

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 http://cs.smith.edu/%7Eorourke/MathOverflow/ExampleGaussian.jpg

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!

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

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 http://cs.smith.edu/%7Eorourke/MathOverflow/ExampleGaussian.jpg

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!

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 http://cs.smith.edu/%7Eorourke/MathOverflow/ExampleGaussian.jpg

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!

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 http://cs.smith.edu/%7Eorourke/MathOverflow/ExampleGaussian.jpg

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!

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