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:
- 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$.
- 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. 34 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.
