I am running a workshop on puzzles and problem solving over the weekend and thought that it might be a good idea to get people engaged by phrasing some interesting mathematical results in terms of two-player games.

One result that I particularly like is the following - if you pick any five points in the integer plane, there must be some pair of points you can pick such that a line drawn through those points will pass through some integer point in-between those two points. The reason for this is that if you pick two points whose coordinates have the same parities, then the line drawn through them must pass through some integer point (specifically, $( \frac{x_0 + x_1}{2}, \frac{y_0 + y_1}{2} )$).

To phrase this as a game, I was planning on giving everyone a 2D grid of integer points and telling them to play the following game:

Players alternate turns choosing a point in the plane. If at the start of your turn you can draw a line between two points that passes through any of the other grid points, you win!

The idea here was that the second player should be able to win - after the first five points are chosen, there has to be a pair of points the second player can pick where the line between those points goes through another integer point.

However, I realized last night that the game is set up such that if the second player hasn't already lost by the start of turn 6, they win the game. This isn't the same as saying "the second player can always win." It might be possible for the following to happen:

  • Player one picks point A.
  • Player two picks point B.
  • Player one then chooses point C such that any point D picked by player two on their next term will force there to be a line passing through an integer point.

I can't find a general way for the first player to force a win, but I also can't prove that it's not possible to do so.

Did I inadvertently invent a game where the first player can always force a win? Or does the second player always have a forced win in this game?



Let me play second. Your first play might as well be $(0,0)$ as the game is translation invariant. I pick $(1,0)$. As you say, if you pick (even,even) or (odd,even) I win. But if you pick (odd,odd) I can pick (even,odd) that does not form a line and vice versa. Say you pick $(2m+1,2n+1)$. I can pick $(2p,2q+1)$ where $2p-1, 2p-2m-1,2q+1$ are all prime and win.

  • $\begingroup$ How do you know that it's possible to find a $(2p, 2q + 1)$ such that the three numbers you've chosen are all prime? Also, what happens if I pick (even, odd) as my second move? $\endgroup$ – templatetypedef Apr 19 '13 at 18:37
  • $\begingroup$ @templatetypedef: Yes, I can clearly find $2q+1$ as a prime and $2p-1, 2p-2m-1$ because there are primes in every arithmetic progression. The argument works exactly the same the other way. $\endgroup$ – Ross Millikan Apr 19 '13 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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