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

The description below comes from

  • József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (2009g:91038).

Given a finite set $S$ of points in the plane $\mathbb R^2$, consider the following game between two players Maker and Breaker. The players alternate, each time picking one (previously unselected) point in $\mathbb R^2$, with Maker moving first. Maker's goal is to build a congruent copy of $S$, while Breaker's goal is to prevent this from happening. If at any finite stage Maker's goal is achieved, the game ends, and Maker wins. Otherwise, Breaker wins.

For example, denote by $A(n)$ the set consisting of $n$ points in a row in arithmetic progression, with common difference one.

  • Maker has a winning strategy, in two moves, if $S=A(2)$.
  • Maker has a winning strategy, in three moves, if $S=A(3)$.
  • Maker has a winning strategy, in at most five moves, if $S=A(4)$ (begin by playing the vertices of an equilateral triangle $ABC$ with side length $1$, such that at least two of the lines it determines, say $AB$ and $AC$, have no points played so far by Breaker).

Beck proves a remarkable theorem in the book (Theorem 1.1): For any finite $S$, Maker has a winning strategy. The proof is an elegant generalization of a theorem of Erdős and Selfridge:

  1. First, one shows that (for any $n$) if $(V,\mathcal F)$ is an $n$-uniform hypergraph with $$ \frac{|\mathcal F|}{|V|}>2^{n-3}\Delta_2(\mathcal F), $$ where $$ \Delta_2(\mathcal F)=\max_{x\ne y\in V}|\{A\in\mathcal F\mid \{x,y\}\subseteq A\}| $$ then, in the game where Maker and Breaker alternate picking distinct elements of $V$, Maker can ensure to pick all the elements in some $A\in\mathcal F$.
  2. Second, one shows that for any $S$, there are finite sets $X$ in the plane that contain "many" congruent copies of $S$. "Many" is formalized so that the inequality above holds, where $V=X$ and $\mathcal F$ is the collection of congruent copies of $S$ among the points in $X$. The sets $X$ obtained this way tend to be very large.

The proof of the "Erdős-Selfridge result" goes by considering a "weighed" characteristic function that counts at each stage of the game the number of sets $A\in\mathcal F$ that have not been eliminated yet by the moves of Breaker, and having Maker play so that the value of this function is maximized at each stage. This ensures that, once all points of $X$ have been played, the function is still positive.

This elegant argument unfortunately produces ridiculously large bounds, due to its great generality. If $S=A(5)$, the number of moves needed to ensure Maker's victory following this approach is estimated to be about $309^{44}\approx 3.6\times 10^{109}$. For $|S|\ge10$, Beck tightens the argument somewhat, to show that $2^{2^{|S|^2}}$ moves suffice.

My question:

For $S=A(5)$, can we find a more decent bound on the number of moves?

My requirement on what counts as "decent" is very loose. I expect the bound above is much larger than needed. I would be happy to be proved wrong, of course, by obtaining large lower bounds. (Additional) references in the literature are also welcome. The following is from pg. 24 of Beck's book:

The wonderful thing about Theorem 1.1 is that it is strikingly general. Yet there is an obvious handicap: these upper bounds to the Move Number are all ridiculously large. We are convinced that Maker can build [the set $S=A(5)$] in (say) less than 1000 moves, but do not have the slightest idea how to prove it. The problem is that any kind of brute force case study becomes hopelessly complicated.

share|improve this question
1  
To clarify, congruent up to scaling and reflection, or must distances and handedness also be preserved? Gerhard "Ask Me About System Design" Paseman, 2012.12.17 –  Gerhard Paseman Dec 17 '12 at 19:39
1  
@Gerhard: If we allow scaling, then we get a much better bound from the fact that the five-in-a-row game (gomoku) is a first player win on a 15x15 board, so this A'(5)<=113 (in fact even less). –  domotorp Dec 21 '12 at 14:47
3  
Since the first player can choose the "orientation" of his second move, it amounts to play gomoku on an hexagonal board with the first player making two moves at the start, which seems easy to win. Each time the first player has achieved A(3) on some free row, the second player has only two possible moves, which quickly limits the number of cases to consider. –  François Brunault Jan 24 '13 at 13:34
2  
Moreover, the fact that the first player doesn't have to block the second one is a clear advantage. –  François Brunault Jan 24 '13 at 13:37
3  
According to Beck (see his abstract in numerik.uni-kiel.de/~discopt/conference/bertinoro0504) Theorem 1.1 remains true even if Breaker is allowed to pick 1000 points in each of her turns! –  Ramiro de la Vega Jan 29 '13 at 18:17
show 10 more comments

1 Answer

up vote 12 down vote accepted

Eleven moves suffice.

François Brunault commented that the maker can get two moves to start on some hexagonal lattice (a lattice generated by unit vectors with an angle of $60$ degrees). In fact, by the fourth move, the maker can get three moves to start in a hexagonal lattice, and can choose these to be the vertices of an equilateral triangle of side $1$ so that the breaker has not played in this lattice yet.

Proof: Let the maker's first play be the origin $A$. Rotate the coordinates after the breaker's first move so that this play be ignored. Let the maker's second move be $B = (2x,0)$ where $x$ is a transcendental smaller than $1$. There are $4$ hexagonal lattices $H_{A,C}, H_{A,D}, H_{B,C}, H_{B,D}$ containing one element of $\lbrace (0,0), (2x,0)\rbrace$ and one element of $\lbrace C=(x,\sqrt{1-x^2}),D=(x,-\sqrt{1-x^2}) \rbrace$, the points of distance $1$ from the maker's first two moves. These hexagonal lattices have the property that the breaker hasn't played in any of them yet, and their pairwise intersections are empty or a point in $\lbrace A,B,C,D\rbrace.$ So, either the second play of the breaker misses both $H_{A,C}$ and $H_{B,C}$ or both $H_{A,D}$ and $H_{B,D}$. By symmetry, we can assume the second play of the breaker misses $H_{A,C}$ and $H_{B,C}$. Let the third play of the maker be $C$. This gives the maker an unopposed pair of points in both $H_{A,C}$ and $H_{B,C}$. The third play of the breaker can only be in one of these lattices. On the fourth move of the maker, the maker can play in the other to make an unopposed equilateral triangle of side length $1$. $\blacksquare$

Next, even if the maker is constrained to play in this lattice, the maker can force $5$ in a row by move $11$. Note that if the maker has an "open $3$" of $3$ points in row with two open spaces on either side, $- - \circ \circ \circ - -$, then the breaker has to respond immediately either just to one side or the other, or else the maker can make $5$ in a row in $2$ more moves. To avoid an explosion of cases, we'll let the breaker play both sides of an open $3$. Perhaps without this, the maker could force $5$ in a row in fewer moves.

We'll show that whatever the breaker's fourth move is, the maker can still force $5$ in a row by the eleventh move. By symmetry, we can assume the breaker's fourth move is in a sixth of the lattice between two of the perpendicular bisectors of the triangle's sides. We'll consider two possible moves within this sixth individually, and then all others.

o o x
 o


   5
o o x
 o

    x
   5
o o x
 o 
x

     x
6   5   
 o o x
  o
 x

x     x
 6   5
  o o x
   o
  x x

x     x
 6 7 5
  o o x
   o
  x x    

 x     x
x 6 7 5 x
   o o x
    o
   x x 

 x     x
x 6 7 5 x
   o o x
  8 o
   x x 

 x   x x
x 6 7 5 x
   o o x
  8 o
 x x x 

 x   x x
x 6 7 5 x
   o o x
  8 o 9
 x x x 

This last play makes two open $3$s, with $7$ and with $8$, so with this $4$th move by the breaker, the maker can construct $5$ in a row by move $11$.

In the next sequence, I'll show the breaker's response immediately, again letting the breaker block both sides of open $3$s.

o o
 o x

    x
 o o
  o x
 5
x

       x
x 6 o o x
     o x
    5
   x

 x     x
x 6 o o x
   7 o x
    5
   x x

 x x   x
x 6 o o x
   7 o x
    5 8
  x x x

 x x   x
x 6 o o x
   7 o x
  9 5 8
   x x x

Again, the maker's 9th move creates two open $3$s, through the $7$ and through the $5$ and $8$, so with that choice of $4$th move by the breaker, the maker can construct $5$ in a row by move $11$.

Next we let the breaker's $4$th move block every other possibility in that sixth of the lattice, which will cover all of those possibilities simultaneously.

     x x x x x
o o . x x x x x
 o . x x x x x
. . . x x x x x
 . . . . x x x

       x x x x x         
5 o o . x x x x x
   o . x x x x x
  . . . x x x x x
   . . . . x x x

This play technically does not make an open $3$ since only one space to the right is open. So, the breaker does not have to respond to either side immediately. The other possibility is $2$ to the left. We will let the breaker play in all $3$ positions simultaneously.

           x x x x x
x x 5 o o x x x x x x
       o . x x x x x
      . . . x x x x x
       . . . . x x x

         x x x x x x
x x 5 o o x x x x x x
       o . x x x x x
      6 . . x x x x x
     x . . . . x x x

   x     x x x x x x
x x 5 o o x x x x x x
     7 o . x x x x x
      6 . . x x x x x
     x x . . . x x x

   x   x x x x x x x
x x 5 o o x x x x x x
     7 o . x x x x x
    8 6 . . x x x x x
   x x x . . . x x x

   x   x x x x x x x
x x 5 o o x x x x x x
     7 o . x x x x x
    8 6 9 . x x x x x
   x x x . . . x x x

Again, the $9$th move creates two open $3$s, so the maker can construct $5$ in a row by move $11$.

share|improve this answer
    
Nice. And much better than I expected. Thanks! –  Andres Caicedo Mar 3 '13 at 6:20
    
That's excellent! and very nice opening :) –  François Brunault Mar 3 '13 at 9:55
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.