Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For integers $n$ such that $\:3< n\:$,$\:$ what is known about the following 2-player game:

Player_1 and Player_2 take turn choosing points on $\mathbb{R}^2$ that were not previously chosen, with Player_1 going first. $\:$ If there is ever a segment with $n$ points chosen by Player_1 and zero points chosen by Player_2, then Player_1 wins. $\:$ If infinitely many turns go by without that happening, then Player_2 wins.


(That includes, if Player_1 has a win, how long the win should take.)

share|improve this question
    
Segment, or line? Gerhard "Ask Me About System Design" Paseman, 2013.05.01 –  Gerhard Paseman May 1 '13 at 19:32
    
segment $\:{}{}$ –  Ricky Demer May 1 '13 at 20:00
    
If segments are replaced with lines, than the plane should probably also be replaced by the projective plane. –  Yoav Kallus May 1 '13 at 20:34
    
For clarification purposes: what does 'that never happens' mean? Are you stopping the game after $\omega$ iterations, or are the two players allowed to make transfinitely many moves? –  Steven Stadnicki May 2 '13 at 0:37
    
now clarified $\:$ –  Ricky Demer May 2 '13 at 2:31

5 Answers 5

up vote 8 down vote accepted
The points on the lines and the lines through the points...
The lines should be many with numerous joints,
the points should be few and should sit at right places.
What else? We can use high-dimensional spaces,
if we do not mind doubling enemy's strength.
It would not be bad if we bound the length
of games, tell who wins, and what way he should play.
The questions are many, but short is the day.
One cannot resolve all the problems at once 
by being just smart. Better leave them to Chance!
The law of large numbers is our best friend.
Who is unpredictable beats every trend.
Of course, he can lose, but the God in the sky
does know enough to condition, not try,
thus weaving each random irrational state
into the unerring decisions of Fate.

The first player wins playing more or less randomly after he prepares the playing field in the right way.

As it has already been said, we can play this game in $\mathbb R^d$. Since, when projecting a high dimensional configuration to the plane, we can avoid extra triple intersections but not extra double intersections of lines, we should allow the opponent to make two moves for each our move to get a stronger version of the game.

Fix $n$ (the number of points on the line we want). Choose small $\delta>0$ and large integer $d>0$ in this order. Consider the cubic lattice in $\mathbb R^d$ with $n$ points along each side ($n^d$ points total). Make $\delta n^d$ moves choosing a random lattice point at each move. If this point is already occupied, just put a point somewhere far away and forget of it. However, mark the occupied point as "intended". Let the opponent move twice after each of your moves. At the end of the game, just look at what you got. Pay attention only to the fully filled (with either actual, or intended points) lattice lines in coordinate directions. You should see the following.

1) The probability to fill each particular line is about $\delta^{n}$, so you should expect $L=n^{d-1}d\delta^{n}$ filled lines. Moreover, the probability to fill less than half of this amount is extremely small because filling two disjoint lines are negatively correlated events and intersecting pairs are few, so the expectation of the square is pretty close to the square of the expectation if $n,\delta$ are fixed and $d\to\infty$.

2) The probability that a given grid point has $k$ filled lines passing through it is at most $\delta\cdot \frac{[d\delta^{n-1}]^k}{k!}$, which is exponentially small in $d$ if $k>2ed\delta^{n-1}$ in the same regime when $n,\delta$ are fixed and $d\to\infty$.

3) Each opponent's point that doesn't lie on the grid can interfere with at most one line.

4) Each opponent's point that lies on the grid can interfere with one of the filled lines only if it was intended during one of your moves. However, since during the whole game only $3\delta n^d$ points have been used, the chance to hit an already occupied point has never been higher than $3\delta$, so it is highly unlikely that the opponent could score much more than $6\delta^2 n^d$ such points.

Now it is time to count the blocked lines. First, $e^{-c(n,\delta)d}dn^d=e^{-c(n,\delta)d}\delta^{-n}nL$ come from "high efficiency" points (let the opponent grab them all, it is still nothing compared to $L$ if $d$ is large enough!). Second, the points put off the grid can block only $2\delta n^d=d^{-1}\delta^{-n+1}n L$ lines, which isn't much either. Last, the "efficient" but not "highly efficient" points on the grid block at most $6\delta^2 n^d\cdot 2ed\delta^{n-1}=2e\delta n L$ filled lines. Here we do not gain from $d$, but if we start with choosing $\delta$ so that $12e\delta n\ll 1$, we are still fine. Thus, normally at most $L/2$ lines will be blocked and, with high probability, the outcome is that we have won the game by this moment.

Since the game is now of fixed length, one of the players must have a deterministic winning strategy. But the second player loses against the random strategy with positive probability no matter what he does, so it isn't he. The deterministic winning strategy for the first player can be defined explicitly in terms of conditional probabilities to win the random game from the current position (just move to the point that gives you the best chance to win the random game in the maximin sense (max over locations, min over all possible opponent's strategies) but the computation of those conditional probabilities is well beyond the human abilities.

share|improve this answer

I'll start things off by observing that this is what is known as an open game, since if player 1 wins, then the winning condition is satisfied after finitely many moves. It follows by the Gale-Stewart theorem that this game is determined: one of the players must have a winning strategy. In particular, the theory of transfinite ordinal game values is applicable, and so player 1's winning strategy, if it exists, will be the value-reducing strategy; and player 2's strategy, if it exists, will be the value-maintaining strategy.

But in truth, I expect that we'll be able to describe the strategy directly in detail...

Although you insisted that $n\gt 3$, the game of course makes sense for smaller values of $n$. When $n=1$, the first player wins on the first move. When $n=2$, the first player clearly can win on the second move. When $n=3$, the first player wins on or before his fourth move, as follows: player 1 plays his second move at the midpoint of the first two points, so that we have $A_1$ $A_2$ $B_1$ collinear. Player 2 must block by playing in between, to give $A_1$ $B_2$ $A_2$ $B_1$ on a line, and now player 1 plays off this line to make a triangle of possibilities, with two ways to win, but player 2 can only block one of them.

See ARupinski's comment for a solution in the case $n=4$.

share|improve this answer
1  
For $n=4$ a similar approach should work. P1 can always play his 2nd and 3rd points into a triangle with at most one of its edges containing one of P2s first two points. Now no matter how P2 chooses to block one of these edges, P1 can find a point such that none of the lines connecting that point to his previous 3 points contain any of P2s points thusfar and which is not collinear with any pair of his previously placed points. Note that P1s points now form the 3 vertices and center point of the Failed Fano configuration. –  ARupinski May 2 '13 at 1:57
1  
So no matter how P2 responds now, at least one of the edge points of this Failed Fano configuration is open, so P1 forms two 3-in-a-rows simultaneously, thereby foiling any further attempt by P2 to win. I don't see any good way to extend this approach to $n>4$ (on account of the rather special nature of the Failed Fano configuration), but maybe this sparks an insight by someone else for the general case... –  ARupinski May 2 '13 at 2:03
    
Ah, I was thinking initially that P2 wins if P2 gets $n$-in-a-row, but this isn't actually what the rules say. So there is no need for player 1 ever to block player 2, and player 2 can actually make no threats to win. –  Joel David Hamkins May 2 '13 at 2:42
    
@ARupinski: Even though the edge points of the Fano configuration may be open, P2 can still have all of the triangle's edges blocked, so I don't see how P1 forms two 3-in-a-rows simultaneously. –  Ricky Demer May 2 '13 at 4:29
2  
Also by playing his points so that intersections of any of the lines he forms do not coincide with any of P2s already played points, it is obvious that by move 5 P1 has too many double 3-in-a-rows lined up for P2 to stop them all with just one point. –  ARupinski May 2 '13 at 22:06

So now Im thinking about the following approach. Let $H$ be the discrete hypercube $[1,...,kn]^d$ with $k,d>> n$ (im not sure how big I need them yet, it just seems that I need them to be sufficiently large compared to $n$ for this to work). I can project $H$ onto $\mathbb{R}^2$ via a linear transformation which sends the unit basis vectors of $\mathbb{R}^d$ to $\mathbb{Q}$-linearly independent vectors in $\mathbb{R}^2$. The point of this is that the only straight lines of points in the projection come from straight lines in $H$. Now P1 plays all his moves on these projected points and I want to argue that the total number of lines of $n$ points in a row contained in $H$ is orders of magnitude greater than the number of lines P2 could have blocked (even accounting for the fact that if P2 played on grid points it would block several potential $n$-in-a-rows simultaneously). The approach then boils down to a slightly stronger version of Van der Waerden's theorem for a bichromatic coloring of $H$. I just cannot figure out the estimates necessary to show for sure that once all of $H$ has been colored (with only the assumption that P1 only colors points of $H$ on each of his plays) there must be enough monochromatic $n$-in-a-rows for sufficiently large $d,k$ that P2 could not possibly have blocked them all. (I assume $k>>n$ to give the possibility of $n$-in-a-rows running at slanted angles through $H$ so that P2 cannot simply block by playing on lines parallel to the coordinate axes). Anyone have ideas on how to rigorously complete this argument or see any fatal flaws I overlooked?

share|improve this answer

Let's consider a version which is harder on the first player, when s/he needs the whole straight line, not just a segment, to win. S/he can still win in $7$ moves. I'll present a brute force solution (strategy).

We may assume that the first player chooses moves $A_1\ A_2\ldots$ without any two pairs belonging to two different parallel lines, and still will follow the strategy described below (it'd be simpler to consider the projective plane :-). Furthermore, we may also assume that no three different points of the first $5$ moves,   $A_1\ \ldots\ A_5$,   are collinear.

Strategy:

  • $A_2$   does not belong to the straight line $L(A_1\ B_1)$;   thus   $B_1\notin L(A_1\ A_2)$;
  • none of the points   $B_1\ B_2$   belongs to   $L(A_1\ A_3)\cup L(A_2\ A_3)$;
  • none of the points   $B_1\ B_2\ B_3$   belongs to   $L(A_i\ A_3)\cup L(A_i\ A_4)\cup L(A_3\ A_4)$,   for at least one value   $i \in \{1\ 2\}$;
  • none of the points   $B_1\ B_2\ B_3\ B_4$   belongs to   $L(A_i\ A_5)\cup L(A_3\ A_5)\cup L(A_4\ A_5)$,   for the same $i$ as before;
  • there are $3$ partitions of   $\{A_i\ A_3\ A_4\ A_5\}$   into disjoint pairs of points; each pair of pairs produces an intersection point of the lines which pass through each pair; of points   $B_1\ \ldots\ B_5$   only points   $B_4\ B_5$   can belong to the union of lines which pass through any two points   $A_i\ A_3\ A_4\ A_5$   (and   $B_4$   belongs to at the most one of these lines); moreover--point   $B_5$   does not belong to any two lines from different partitions (only points of the first player do); thus the lines of one of the mentioned partitions into disjoint pairs are free from all points   $B_1\ \ldots\ B_5$; let the first player choose the intersection point of this pair of lines as   $A_6$;
  • point   $B_6$   can belong to at the most one line just mentioned above; thus the first player can choose a point   $A_7$   on the other line, and will obtain $4$ points on this line, while the second player has none.

CONCLUSION:   for   $n=4$   the first player can win in $7$ moves.

REMARK   We considered a total of $13$ points   $A_1\ B_1\ \ldots\ B_6\ A_7$,   which is the number of points of the projective plane over field $\mathit {GF}(3)$.   It must be simple to decide if the above argument carries over to the finite $13$-point projective plane but I am too tired of mathoverflow $\LaTeX$ to see anything anymore.

share|improve this answer
    
While I was editing and editing patiently all the details in $\LaTeX$, @ARupinski posted his comment which perhaps contains a similar solution for $n=4$. –  Wlodzimierz Holsztynski May 2 '13 at 3:41
    
I now see how to show that your strategy is optimal. $\:$ $B_2$ goes between $A_1$ and $A_2$, $B_3$ $\hspace{.75 in}$ goes between $A_1$ and $A_3$, $B_4$ goes between $A_2$ and $A_3$, and $B_5$ goes between $A_4$ and $A_5$. –  Ricky Demer May 5 '13 at 4:13

Okay, I'm rewriting my old answer - I thought I could extract the necessary estimates from Polymath's paper, but it looks like such an effort would take more time than I have in the near future.

I'd like to modify the game as follows: Suppose we fix a positive integer $r$, and specify that player 2 is allowed to make $r$ moves for each move by player 1. The original game corresponds to the case $r=1$.

As ARupinski proposed, a possible winning strategy for player 1 is to play on a high-dimensional cubic lattice $[1,\ldots,n]^d$ embedded in $\mathbb{R}^2$. To prove this works, it suffices to show that any arrangement of $\frac{n^d}{r+1}$ points in the lattice contains enough "lines" that player 2 cannot block all of them.

The Furstenburg-Katznelson theorem (also known as Density Hales-Jewett) gives a way to solve this. The literal result only produces the existence of a single line of a special form, with $d$ bounded by $A_{n+1}(r+1)$ (where $A_n$ denotes a modified Ackerman function defined by $A_1(r) = 2r$, $A_n(1) = 2$, and $A_{n+1}(r+1) = A_n(A_{n+1}(r))$). Since a single line can be blocked by a single intervening point, we really need a result that gives lots of lines. There is a multidimensional DHJ result in Polymath's paper, producing subspaces instead of lines, but the asymptotics are to be much too weak for this purpose.

A straightforward-sounding method is to show that if the dimension $d$ is large enough, then there are lots of subspaces $V$ of dimension close to $d'$ for which our set has density that isn't much less than $1/(r+1)$ on $V$, where $d'$ is large enough that we are guaranteed a line on each $V$. I suspect we could bound it by an Ackerman function with slightly larger parameters, but since I haven't worked out any details, we know how much that's worth.

share|improve this answer
    
Player 2 does not need to restrict its plays to range of an embedding of that cube. $\hspace{1 in}$ –  Ricky Demer May 4 '13 at 4:05
1  
Oops, I forgot to make estimates concerning player 2's blocking ability. Please ignore this answer for now. –  S. Carnahan May 4 '13 at 4:09
    
(Presumably your comment means you realize this, but anyway.) $\;\;$ By a generic embedding of the cube, it would be enough to show that every subset of the cube with density at least $\frac1{r+1}$ has more than $\: 2\cdot r\cdot \left(\left\lceil \frac{n^{\hspace{.01 in}d}}{r+1}\right\rceil-1\right) \:$ lines. $\;\;\;\;$ –  Ricky Demer May 4 '13 at 4:21

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.