Para $n=4$ es posible un empate. Golomb y Hales ofrecen una construcción en el artículo Hypercube Tic-Tac-Toe:
![enter image description here]()
Este diagrama parece misterioso, así que permítanme desempacar.
Pensamos en un $4$ -de coordenadas $(a,b,c,d)$ como dar una coordenada $(a,b)$ en la primera $4\times 4$ tablero de arriba y una coordenada $(c,d)$ en el segundo $4 \times 4$ tablero. Etiquetamos $(a,b,c,d)$ con un $+$ si el producto de los signos de las dos tablas es positivo: ambas son $+$ o ambos son $-$ . En caso contrario, etiquetamos $(a,b,c,d)$ con un $-$ . La afirmación es que si $+$ y $-$ son los movimientos de los dos jugadores, la posición es un empate.
Para ver esto, observe que una línea en el $4$ -es el producto de:
- Una línea en el primer tablero y una línea en el segundo, o
- Una línea en una tabla y un punto en la otra.
El primer tipo de línea no causa ningún problema debido a la propiedad clave: todas las líneas del primer tablero tienen un número par de $+$ y todas las líneas del segundo tablero tienen un Número impar de $+$ 's. Cuando se multiplican dos líneas de este tipo, el resultado tendrá un número impar de $+$ y por lo tanto no puede ser $+,+,+,+$ o $-,-,-,-$ .
El segundo tipo de línea no causa ningún problema simplemente porque ni $4\times 4$ tiene una línea ganadora, y esto no cambia si se multiplica la línea por un $+$ o un $-$ .
De hecho, podemos hacerlo mejor. La misma idea de "producto" funciona si empezamos con los dos $4\times4\times4$ coloración de abajo, lo que nos da una $6$ -dimensional $4\times4\times4\times4\times4\times4$ dibujar. (Se puede comprobar que las dos coloraciones tienen las mismas propiedades "pares" e "Impares" respectivamente). En lugar de $+$ y $-$ He utilizado el rojo y el azul en el siguiente diagrama.
![enter image description here]()
Por cada $n$ Hay una dimensión en la que el empate es imposible, por la Teorema de Hales-Jewett . Este teorema muestra una afirmación más fuerte en dos sentidos: muestra que hay una dimensión en la que no importa cómo se coloree la cuadrícula (no necesariamente con cantidades iguales de cada color) habrá no sólo una línea, sino una línea con pendiente no negativa en cada coordenada. Sin embargo, los límites superiores de la dimensión necesaria tienden a ser muy grandes.
Para $n > 4$ podemos obtener límites inferiores cada vez más grandes, al menos exponencialmente crecientes, sobre la dimensión en la que es posible un empate, a través de la Números de van der Waerden . Los van der Waerden $W(2,k)$ es el menor número entero tal que no podemos $2$ -color $\{1,2,\dots,W(2,k)\}$ sin encontrar un $k$ -término de progresión aritmética. Por lo tanto, hay una coloración de $\{1,2,\dots,W(2,k)-1\}$ sin esa progresión. Podemos utilizarla para construir para $d = \frac{W(2,k)-2}{k-1}$ un empate en un $d$ -hipercubo de dimensiones con lado $n=2k$ de la siguiente manera:
- Rotula cada celda de la cuadrícula con el número de pasos que hay desde el cuadrado central. Cada paso puede cambiar sólo una coordenada a la vez. Estos números van desde $1$ a $1+(k-1)d = W(2,k)-1$ .
- Colorear cada celda según su etiqueta numérica, por la coloración que evita $k$ -términos de progresión aritmética.
- En la mitad de la cuadrícula (digamos, la mitad con la primera coordenada $k$ o menos), invierta la coloración: esto garantiza que exista un número igual de celdas de cada color.
Entonces, a lo largo de cada línea, no habrá sólo dos colores: a lo largo de cada línea, si tomamos la primera o la segunda mitad de esa línea, entonces las etiquetas a lo largo de esa mitad formarán un $k$ -progresión aritmética, por lo que sólo esa mitad de la línea incluirá dos colores.
Para $n=2k+1$ Podemos ampliar esta misma coloración "insertando" cuidadosamente algunas celdas en el centro.
