No hay problema de tres en línea

El problema de no tres en línea en geometría discreta pregunta cuántos puntos se pueden colocar en la cuadrícula para que no haya tres puntos en la misma línea. Este número es como máximo , porque los puntos en una cuadrícula incluirían una fila de tres o más puntos, según el principio de casillero . El problema fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo llaman "una de las cuestiones geométricas más antiguas y estudiadas sobre los puntos de celosía". ^[1]${\ Displaystyle n \ times n}$${\ Displaystyle 2n}$${\ Displaystyle 2n + 1}$

Aunque el problema se puede resolver con puntos por cada hasta que , se conjetura que menos puntos se pueden colocar en las redes de gran tamaño. Los métodos conocidos pueden colocar linealmente muchos puntos en cuadrículas de tamaño arbitrario, pero el mejor de estos métodos coloca un poco menos de puntos, no . También se han estudiado varios problemas relacionados con la búsqueda de puntos sin tres en línea, entre otros conjuntos de puntos distintos de las cuadrículas.${\ Displaystyle 2n}$${\ Displaystyle n}$${\ displaystyle 46}$${\ Displaystyle 2n}$${\ Displaystyle 3n / 2}$${\ Displaystyle 2n}$

Aunque tiene su origen en las matemáticas recreativas , el problema tiene aplicaciones en el dibujo de gráficos y en el problema del triángulo de Heilbronn .

El problema fue planteado por primera vez por Henry Dudeney en 1900, como un rompecabezas en matemáticas recreativas, expresado en términos de colocar los 16 peones de un tablero de ajedrez en el tablero de modo que no haya tres en una línea. ^[2] Este es exactamente el problema de no tres en línea, para el caso . ^[3]${\displaystyle n=8}$ En una versión posterior del rompecabezas, Dudeney modificó el problema, haciendo que su solución fuera única, pidiendo una solución en la que dos de los peones estuvieran en las casillas d4 y e5 , atacándose entre sí en el centro del tablero. ^[4]

Muchos autores han publicado soluciones a este problema para valores pequeños de , ^[5]${\displaystyle n}$ y en 1998 se sabía que los puntos podían colocarse en una cuadrícula sin tres en una línea para todos hasta 46, y algunos valores más grandes. ^[6] El número de soluciones (sin contar las reflexiones y rotaciones como distintas) para valores pequeños de , a partir de , es ^{[3] [7]}${\displaystyle 2n}$${\displaystyle n\times n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n=2}$

El número exacto de puntos que se puede colocar, como una función de ,${\displaystyle n}$ no se conoce. Sin embargo, tanto los límites probados como los conjeturados limitan este número dentro de un rango proporcional a .${\displaystyle n}$

Un conjunto de 20 puntos en una cuadrícula de 10 × 10, sin tres puntos en una línea.

Colocación subóptima de puntos en la cuadrícula, utilizando el método de Erdős. El primo más grande menor que el tamaño de la cuadrícula es ; la solución coloca puntos en las coordenadas mod para . Por ejemplo, se incluye porque ( mod ).${\displaystyle 11}$${\displaystyle 12\times 12}$${\displaystyle p}$${\displaystyle p=11}$${\displaystyle (i,i^{2}}$${\displaystyle p)}$${\displaystyle i=0,1,\dots p-1}$${\displaystyle (4,5)}$${\displaystyle 4^{2}=16\cong 5}$ ${\displaystyle }$${\displaystyle 11}$