Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks!

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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? –  templatetypedef Apr 19 '13 at 18:37
    
@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. –  Ross Millikan Apr 19 '13 at 20:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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