La descripción que figura a continuación procede de
- József Beck. Juegos combinatorios. Teoría del tres en raya Enciclopedia de Matemáticas y sus Aplicaciones, 114 . Cambridge University Press, Cambridge, 2008, MR2402857 (2009g:91038) .
Dado un conjunto finito $S$ de puntos en el plano $\mathbb R^2$ Consideremos el siguiente juego entre dos jugadores Maker y Breaker. Los jugadores se alternan, eligiendo cada vez un punto (no seleccionado previamente) en $\mathbb R^2$ Con Maker moviéndose primero. El objetivo de Maker es construir una copia congruente de $S$ , mientras que el objetivo de Breaker es evitar que esto ocurra. Si en cualquier etapa finita se logra el objetivo de Maker, el juego termina, y Maker gana. En caso contrario, gana Breaker.
Por ejemplo, denotemos por $A(n)$ el conjunto formado por $n$ puntos seguidos en progresión aritmética, con diferencia común uno.
- Maker tiene una estrategia ganadora, en dos movimientos, si $S=A(2)$ .
- Maker tiene una estrategia ganadora, en tres movimientos, si $S=A(3)$ .
- Maker tiene una estrategia ganadora, en un máximo de cinco movimientos, si $S=A(4)$ (empezar tocando los vértices de un triángulo equilátero $ABC$ con longitud lateral $1$ , tal que al menos dos de las líneas que determina, digamos $AB$ y $AC$ , no tienen puntos jugados hasta ahora por Breaker).
Beck demuestra un teorema notable en el libro (Teorema 1.1): Para cualquier $S$ Maker tiene una estrategia ganadora. La prueba es una elegante generalización de un teorema de Erdos y Selfridge:
- En primer lugar, se demuestra que (para cualquier $n$ ) si $(V,\mathcal F)$ es un $n$ -hipergrafo uniforme con $$ \frac{|\mathcal F|}{|V|}>2^{n-3}\Delta_2(\mathcal F), $$ donde $$ \Delta_2(\mathcal F)=\max_{x\ne y\in V}|\{A\in\mathcal F\mid \{x,y\}\subseteq A\}| $$ entonces, en el juego donde Maker y Breaker se alternan escogiendo distintos elementos de $V$ Maker puede asegurarse de recoger todos los elementos en algún $A\in\mathcal F$ .
- En segundo lugar, se demuestra que para cualquier $S$ hay conjuntos finitos $X$ en el plano que contienen "muchas" copias congruentes de $S$ . "Muchos" se formaliza de manera que la desigualdad anterior se mantiene, donde $V=X$ y $\mathcal F$ es la colección de copias congruentes de $S$ entre los puntos de $X$ . Los conjuntos $X$ obtenidos de esta manera suelen ser muy grandes.
La demostración del "resultado Erdos-Selfridge" pasa por considerar una función característica "ponderada" que cuenta en cada etapa del juego el número de conjuntos $A\in\mathcal F$ que aún no han sido eliminados por las jugadas de Breaker, y haciendo que Maker juegue de manera que el valor de esta función se maximice en cada etapa. Esto asegura que, una vez que todos los puntos de $X$ se han jugado, la función sigue siendo positiva.
Este elegante argumento produce, por desgracia, límites ridículamente grandes, debido a su gran generalidad. Si $S=A(5)$ El número de movimientos necesarios para asegurar la victoria de Maker siguiendo este enfoque se estima en unos $309^{44}\approx 3.6\times 10^{109}$ . Para $|S|\ge10$ Beck refuerza un poco el argumento para demostrar que $2^{2^{|S|^2}}$ movimientos son suficientes.
Mi pregunta:
Para $S=A(5)$ ¿podemos encontrar un límite más decente en el número de movimientos?
Mi exigencia sobre lo que cuenta como "decente" es muy floja. Supongo que el límite anterior es mucho mayor de lo necesario. Me encantaría que se demostrara que estoy equivocado, por supuesto, si se obtuvieran límites más bajos. También son bienvenidas las referencias (adicionales) en la literatura. Lo siguiente es de la página 34 del libro de Beck:
Lo maravilloso del teorema 1.1 es que es sorprendentemente general. Sin embargo, hay hay una desventaja obvia: estos límites superiores al número de movimiento son todos ridículamente grandes. Estamos convencidos de que Maker puede construir [el conjunto $S=A(5)$ ] en (digamos) menos de 1000 movimientos, pero no tienen la menor idea de cómo demostrarlo. El problema es que cualquier tipo de estudio de caso de fuerza bruta se vuelve desesperadamente complicado.
