Problema sin tres en línea

Problema de geometría en puntos de la cuadrícula.

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

El problema de no tener tres en línea en geometría discreta pregunta cuántos puntos se pueden colocar en la cuadrícula de modo que no haya tres puntos en la misma línea. El problema afecta a las líneas de todas las vertientes, no sólo a las alineadas con la cuadrícula. Fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo llaman "una de las cuestiones geométricas más antiguas y más estudiadas sobre los puntos de la red". ^[1] ${\displaystyle n\times n}$

Como máximo , se pueden colocar puntos, porque los puntos en una cuadrícula incluirían una fila de tres o más puntos, según el principio de casillero . Aunque el problema se puede resolver con puntos por cada hasta , se conjetura que se pueden colocar menos puntos en cuadrículas 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 . ${\displaystyle 2n}$ ${\displaystyle 2n+1}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle 46}$ ${\displaystyle 2n}$ ${\displaystyle 3n/2}$ ${\displaystyle 2n}$

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. Aunque se originó en las matemáticas recreativas , el problema del no tres en línea tiene aplicaciones en el dibujo de gráficos y en el problema del triángulo de Heilbronn .

Pequeñas instancias

Solución al rompecabezas de Dudeney de colocar 16 peones en un tablero de ajedrez de modo que no haya tres peones en la misma línea y los peones estén en las casillas d4 y e5.

El problema fue planteado por primera vez por Henry Dudeney en 1900, como un rompecabezas de matemáticas recreativas, formulado en términos de colocar los 16 peones de un tablero de ajedrez en el tablero de modo que no haya tres en línea. ^[2] Este es exactamente el problema del 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 estén 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 se podían colocar puntos en una cuadrícula sin tres en una línea para todos hasta 46, y algunos valores mayores. ^[6] Los números de soluciones con puntos para valores pequeños de , a partir de , son ${\displaystyle 2n}$ ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n=2}$

1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, ... (secuencia A000755 en el OEIS ).

Los números de clases de equivalencia de soluciones con puntos bajo reflexiones y rotaciones son ${\displaystyle 2n}$

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (secuencia A000769 en el OEIS ). ^[3]

Límites superior e inferior

Se desconoce el número exacto de puntos que se pueden colocar, en función de . ${\displaystyle n}$Sin embargo, tanto los límites probados como los conjeturados limitan este número dentro de un rango proporcional a . ${\displaystyle n}$

Métodos generales de colocación

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 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}$

Una solución de Paul Erdős , publicada por Roth (1951), se basa en la observación de que cuando es un número primo , el conjunto de puntos de la cuadrícula mod , para , no contiene tres puntos colineales. Cuando no es primo, se puede realizar esta construcción para una cuadrícula contenida en la cuadrícula, donde es el primo más grande que es como máximo . Debido a que la brecha entre números primos consecutivos es mucho más pequeña que los propios números primos, siempre estará cerca de , por lo que este método se puede usar para colocar puntos en la cuadrícula sin tres puntos colineales. ^[7] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (i,i^{2}}$ ${\displaystyle n)}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle n}$ ${\displaystyle p\times p}$ ${\displaystyle n\times n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n-o(n)}$ ${\displaystyle n\times n}$

El límite de Erdős se ha mejorado posteriormente: Hall et al. (1975) muestran que, cuando es primo, se puede obtener una solución con puntos, colocando puntos en múltiples copias de la hipérbola (mod ), donde se puede elegir arbitrariamente siempre que sea mod distinto de cero . Nuevamente, de forma arbitraria, se puede realizar esta construcción para un primo cercano para obtener una solución con puntos. ^[8] ${\displaystyle n/2}$ ${\displaystyle 3(n-2)/2}$ ${\displaystyle xy=k}$ ${\displaystyle n/2}$ ${\displaystyle k}$ ${\displaystyle n/2}$ ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle {\tfrac {3}{2}}n-o(n)}$

límite superior

En la mayoría de los puntos se pueden colocar en una cuadrícula de cualquier tamaño . Porque, si se colocan más puntos, entonces, según el principio del casillero , unos tres de ellos estarían todos en la misma línea horizontal de la cuadrícula. Para , se sabe que este límite trivial es estricto. ^[3] ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n\leq 46}$

Límites conjeturados

Aunque exactamente se pueden colocar puntos en cuadrículas pequeñas, Guy y Kelly (1968) conjeturaron que para cuadrículas grandes, existe un límite superior significativamente menor en el número de puntos que se pueden colocar. Más precisamente, conjeturaron que el número de puntos que se pueden colocar es como máximo una cantidad sublineal mayor que , con ^[9] ${\displaystyle 2n}$ ${\displaystyle cn}$

$${\displaystyle c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1.874.}$$

^[10]. ${\displaystyle cn}$

$${\displaystyle c={\frac {\pi }{\sqrt {3}}}\approx 1.814.}$$

Aplicaciones

Se pueden utilizar soluciones al problema de no tener tres en línea para evitar ciertos tipos de degeneraciones en el dibujo de gráficos . El problema al que se aplican implica colocar los vértices de un gráfico dado en coordenadas enteras en el plano y dibujar los bordes del gráfico como segmentos de línea recta . Para ciertos gráficos, como el gráfico de utilidad , los cruces entre pares de aristas son inevitables, pero aun así se deben evitar ubicaciones que hagan que un vértice se encuentre en una arista que pasa por otros dos vértices. Cuando los vértices se colocan sin tres en línea, este tipo de ubicación problemática no puede ocurrir, porque toda la línea que pasa por dos vértices cualesquiera, y no solo el segmento de línea, está libre de otros vértices. ^[11] El hecho de que el problema de no tres en línea tenga una solución con muchos puntos linealmente se puede traducir en términos de dibujo de gráficos en el sentido de que cada gráfico, incluso un gráfico completo , se puede dibujar sin incidencias no deseadas en los bordes de los vértices usando una cuadrícula cuya área es cuadrática en el número de vértices, y que para gráficos completos no es posible dibujar con un área menor que cuadrática. Los gráficos completos también requieren un número lineal de colores en cualquier color de gráfico , pero otros gráficos que se pueden colorear con menos colores también se pueden dibujar en cuadrículas más pequeñas: si un gráfico tiene vértices y un gráfico se colorea con colores, se puede dibujar en una cuadrícula con área proporcional a . El dibujo sin tres en línea de un gráfico completo es un caso especial de este resultado con . ^[12] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle nk}$ ${\displaystyle k=n}$

El problema del no-tres en línea también tiene aplicaciones a otro problema de geometría discreta, el problema del triángulo de Heilbronn . En este problema, se deben colocar puntos, en cualquier lugar de un cuadrado unitario, sin limitarse a una cuadrícula. El objetivo de la colocación es evitar triángulos de área pequeña y, más específicamente, maximizar el área del triángulo más pequeño formado por tres de los puntos. Por ejemplo, una ubicación con tres puntos en línea sería muy mala según este criterio, porque estos tres puntos formarían un triángulo degenerado con área cero. Por otro lado, si los puntos se pueden colocar en una cuadrícula de longitud de lado dentro del cuadrado unitario, sin tres en una línea, entonces, según el teorema de Pick, cada triángulo tendría un área de al menos , la mitad de un cuadrado de cuadrícula. Por lo tanto, resolver un caso del problema del no-tres en línea y luego reducir la cuadrícula de números enteros para que quepa dentro de un cuadrado unitario produce soluciones al problema del triángulo de Heilbronn donde el triángulo más pequeño tiene un área . Esta aplicación fue la motivación para que Paul Erdős encontrara su solución al problema del no-tres en línea. ^[13] Siguió siendo el mejor límite inferior de área conocido para el problema del triángulo de Heilbronn desde 1951 hasta 1982, cuando se mejoró mediante un factor logarítmico utilizando una construcción que no se basaba en el problema de no tres en línea. ^[14] ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon ^{2}/2}$ ${\displaystyle \Omega (1/n^{2})}$

Generalizaciones y variaciones.

Subconjuntos de posiciones generales

En geometría computacional , se dice que los conjuntos finitos de puntos sin tres en línea están en posición general . En esta terminología, el problema de no tres en línea busca el subconjunto más grande de una cuadrícula que esté en posición general, pero los investigadores también han considerado el problema de encontrar el subconjunto de posición general más grande de otros conjuntos de puntos que no pertenecen a la cuadrícula. Es NP-difícil encontrar este subconjunto, para ciertos conjuntos de entradas, y difícil aproximar su tamaño dentro de un factor constante; Este resultado de dureza de aproximación se resume diciendo que el problema es APX-duro . Si el subconjunto más grande tiene tamaño , ${\displaystyle k}$ se puede obtener una solución con una relación de aproximación no constante mediante un algoritmo codicioso que simplemente elige los puntos uno a la vez hasta que todos los puntos restantes se encuentran en líneas que pasan por pares de puntos elegidos. ^[15] ${\displaystyle O({\sqrt {k}})}$

Se puede obtener una comprensión más detallada del tiempo de ejecución de los algoritmos para encontrar la solución óptima exacta utilizando la complejidad parametrizada , en la que los algoritmos se analizan no solo en términos del tamaño de entrada, sino en términos de otros parámetros de la entrada. En este caso, para las entradas cuyo subconjunto de posición general más grande tiene tamaño , ${\displaystyle k}$ se puede encontrar en una cantidad de tiempo que es una función exponencial de multiplicado por un polinomio en el tamaño de entrada , sin que el exponente del polinomio dependa de . Los problemas con este tipo de límite de tiempo se denominan tratables de parámetros fijos . ^[dieciséis] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Para conjuntos de puntos que tienen como máximo puntos por línea, con , existen subconjuntos de posición general de tamaño casi proporcional a . El ejemplo de la cuadrícula muestra que este límite no se puede mejorar significativamente. ^[17] La ​​prueba de la existencia de estos grandes subconjuntos de posiciones generales se puede convertir en un algoritmo de tiempo polinomial para encontrar un subconjunto de posiciones generales de , de tamaño que coincida con el límite de existencia, utilizando una técnica algorítmica conocida como compresión de entropía . ^[15] ${\displaystyle S}$ ${\textstyle \ell }$ ${\textstyle \ell =O({\sqrt {|S|}})}$ ${\textstyle \ell =O({\sqrt {|S|}})}$ ${\displaystyle S}$

Colocación codiciosa

Repitiendo una sugerencia de Adena, Holton y Kelly (1974), Martin Gardner pidió el subconjunto más pequeño de una cuadrícula que no pueda extenderse: no tiene tres puntos en una línea, pero todo superconjunto adecuado tiene tres en una línea. De manera equivalente, este es el conjunto más pequeño que podría producir un algoritmo codicioso que intenta resolver el problema del no-tres en línea colocando puntos uno a la vez hasta que se atasca. ^[3] Si solo se consideran líneas diagonales y paralelas al eje, entonces cada conjunto tiene al menos puntos. ^[18] Sin embargo, se sabe menos sobre la versión del problema donde se consideran todas las líneas: cada ubicación codiciosa incluye al menos puntos antes de quedarse atascado, pero no se conoce nada mejor que el trivial límite superior. ^[19] ${\displaystyle n\times n}$ ${\displaystyle n-1}$ ${\displaystyle \Omega (n^{2/3})}$ ${\displaystyle 2n}$

Dimensiones superiores

Pór y Wood (2007) consideraron conjuntos de puntos no colineales en la cuadrícula tridimensional. Probaron que el número máximo de puntos en la cuadrícula sin tres puntos colineales es . De manera similar a la construcción 2D de Erdős, esto se puede lograr usando puntos mod , donde es un primo congruente con 3 mod 4 . ^[20] Así como el problema original de no tres en línea se puede usar para dibujar gráficos bidimensionales, se puede usar esta solución tridimensional para dibujar gráficos en la cuadrícula tridimensional. Aquí la condición de no colinealidad significa que un vértice no debe estar en un borde no adyacente, pero es normal trabajar con el requisito más estricto de que no se crucen dos bordes. ^[21] ${\displaystyle n\times n\times n}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle (x,y,x^{2}+y^{2}}$ ${\displaystyle p)}$ ${\displaystyle p}$

En dimensiones mucho más altas, se han utilizado conjuntos de puntos de cuadrícula sin tres en línea, obtenidos eligiendo puntos cerca de una hiperesfera , para encontrar grandes conjuntos de Salem-Spencer , conjuntos de números enteros sin tres que forman una progresión aritmética. ^[22] Sin embargo, no funciona bien utilizar esta misma idea de elegir puntos cerca de un círculo en dos dimensiones: este método encuentra puntos que forman polígonos convexos, que satisfacen el requisito de no tener tres en línea, pero que son demasiado pequeños. Los polígonos convexos más grandes con vértices en una cuadrícula solo tienen vértices. ^[23] El problema del conjunto de límites se refiere a un problema similar al problema de no tener tres en línea en espacios que son de alta dimensión y se basan como espacios vectoriales sobre campos finitos en lugar de sobre números enteros. ^[24] ${\displaystyle n\times n}$ ${\displaystyle O(n^{2/3})}$

Otra generalización a dimensiones superiores es encontrar tantos puntos como sea posible en una cuadrícula tridimensional de modo que no haya cuatro de ellos en el mismo plano. Esta secuencia comienza 5, 8, 10, 13, 16,... OEIS : A280537 para N = 2, 3, 4 , etc. ${\displaystyle N\times N\times N}$

Toro

Otra variación del problema implica convertir la cuadrícula en un toro discreto mediante el uso de condiciones de contorno periódicas en las que el lado izquierdo del toro está conectado al lado derecho y el lado superior está conectado al lado inferior. Esto tiene el efecto, en líneas inclinadas a través de la cuadrícula, de conectarlas en líneas más largas a través de más puntos y, por lo tanto, hace más difícil seleccionar puntos con como máximo dos de cada línea. Estas líneas extendidas también se pueden interpretar como líneas normales a través de una cuadrícula infinita en el plano euclidiano, tomadas en módulo las dimensiones del toro. Para un toro basado en una cuadrícula, el número máximo de puntos que se pueden elegir sin tres en línea es como máximo . ^[25] Cuando ambas dimensiones son iguales y primos, no es posible colocar exactamente un punto en cada fila y columna sin formar un número lineal de ternas colineales. ^[26] También se han estudiado versiones toroidales del problema con dimensiones superiores. ^[27] ${\displaystyle m\times n}$ ${\displaystyle 2\gcd(m,n)}$

Ver también

• Rompecabezas de ocho reinas , al colocar puntos en una cuadrícula sin dos en la misma fila, columna o diagonal

Notas

1. Latón, Moser y Pach 2005.
2. The Weekly Dispatch , 29 de abril y 13 de mayo de 1900, citado por Knuth 2008.
3. Gardner 1976.
4. Dudeney 1917.
5. Craggs y Hughes-Jones 1976; Klove 1978, 1979; Anderson 1979; Harborth, Oertel y Prellberg 1989; Flammenkamp 1992, 1998.
6. Flammenkamp 1992, 1998.
7. Erdős no publicó esta observación; aparece en Roth 1951.
8. Hall y otros. 1975.
9. Chico y Kelly 1968.
10. Según lo informado por Pegg 2005. Pegg atribuyó el descubrimiento de este error a Gabor Ellmann.
11. Latón y col. 2007.
12. Madera 2005.
13. Roth 1951.
14. Komlós, Pintz y Szemerédi 1982.
15. Eppstein 2018.
16. Froese y col. 2017; Eppstein 2018
17. Payne y madera 2013.
18. Cooper y col. 2014.
19. Aichholzer, Eppstein y Hainzl (2023).
20. Por & Wood 2007.
21. Pach, Thiele y Tóth 1998; Dujmović, Morin y Wood 2005; Di Giacomo, Liotta y Meijer 2005
22. Elkin 2011.
23. Jarnik 1926.
24. Klarreich 2016.
25. Misiak y col. 2016.
26. Cooper y Solymosi 2005.
27. Ku y Wong 2018.

Referencias

• Adena, Michael A.; Holton, Derek A.; Kelly, Patrick A. (1974). "Algunas reflexiones sobre el problema de los tres en línea". En Holton, Derek A. (ed.). Matemáticas combinatorias: Actas de la Segunda Conferencia Australiana (Universidad de Melbourne, 1973) . Apuntes de conferencias de matemáticas. vol. 403, págs. 6-17. doi :10.1007/BFb0057371. SEÑOR  0349396.
• Aichholzer, Oswin; Eppstein, David ; Hainzl, Eva-Maria (enero de 2023). "Conjuntos geométricos dominantes: una versión mínima del problema de los tres en línea". Geometría Computacional . Elsevier. 108 : 101913. arXiv : 2203.13170 . doi : 10.1016/j.comgeo.2022.101913 . S2CID  249687906.
• Anderson, David Brent (1979). "Actualización sobre el problema de los tres en línea". Revista de teoría combinatoria . Serie A. 27 (3): 365–366. doi : 10.1016/0097-3165(79)90025-6 . SEÑOR  0555806.
• Latón, Peter; Cenek, Éowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna ; Mitchell, Joseph SB (2007). "Sobre incrustaciones simultáneas de gráficos planos". Geometría Computacional . 36 (2): 117-130. doi : 10.1016/j.comgeo.2006.05.006 . SEÑOR  2278011.
• Latón, Peter; Moser, William; Pach, János (2005). "Sección 10.1: Empaquetado de puntos de red en subespacios". Problemas de investigación en geometría discreta . Springer, Nueva York. págs. 417–421. ISBN 978-0-387-29929-7. SEÑOR  2163782.
• Cooper, Alec S.; Pikhurko, Oleg; Schmitt, John R.; Warrington, Gregory S. (2014). "El problema mínimo de los 3 en línea de Martin Gardner". Mensual Matemático Estadounidense . 121 (3): 213–221. arXiv : 1206.5350 . doi : 10.4169/amer.math.monthly.121.03.213. JSTOR  10.4169/amer.math.monthly.121.03.213. S2CID  887220.
• Cooper, Josué N.; Solymosi, József (2005). "Puntos colineales en permutaciones" (PDF) . Anales de combinatoria . 9 (2): 169-175. arXiv : matemáticas/0408396 . doi :10.1007/s00026-005-0248-4. SEÑOR  2153735. S2CID  11035679.
• Craggs, D.; Hughes-Jones, R. (1976). "Sobre el problema de los tres en línea". Revista de teoría combinatoria . Serie A. 20 (3): 363–364. doi : 10.1016/0097-3165(76)90030-3 . SEÑOR  0406804.
• Dudeney, Henry (1917). "317. Un rompecabezas con peones". Diversiones en Matemáticas . Edimburgo: Nelson. pag. 94.Solución, pág. 222. Publicado originalmente en el London Tribune , 7 de noviembre de 1906.
• Di Giacomo, Emilio; Liotta, Giuseppe; Meijer, Henk (2005). "Cálculo de dibujos de cuadrícula 3D en línea recta de gráficos en volumen lineal". Geometría computacional: teoría y aplicaciones . 32 (1): 26–58. doi : 10.1016/j.comgeo.2004.11.003.
• Dujmović, Vida ; Morín, Pat ; Madera, David R. (2005). "Diseño de gráficos con ancho de árbol acotado". Revista SIAM de Computación . 34 (3): 553–579. arXiv : cs/0406024 . doi :10.1137/S0097539702416141. S2CID  3264071.
• Elkin, Michael (2011). "Una construcción mejorada de conjuntos sin progresión". Revista Israelí de Matemáticas . 184 : 93-128. arXiv : 0801.4310 . doi : 10.1007/s11856-011-0061-1 . SEÑOR  2823971.
• Eppstein, David (2018). "Capítulo 9: Posición general". Configuraciones Prohibidas en Geometría Discreta . Prensa de la Universidad de Cambridge. págs. 72–86.
• Flammenkamp, ​​Achim (1992). "Avances en el problema de los tres en línea". Revista de teoría combinatoria . Serie A. 60 (2): 305–311. doi : 10.1016/0097-3165(92)90012-J .
• Flammenkamp, ​​Achim (1998). "Avances en el problema de los tres en línea, II". Revista de teoría combinatoria . Serie A. 81 (1): 108–113. doi : 10.1006/jcta.1997.2829 .
• Froese, Vicente; Kanj, Iyad; Nichterlein, André; Niedermeier, Rolf (2017). "Encontrar puntos en posición general". Revista internacional de aplicaciones y geometría computacional . 27 (4): 277–296. arXiv : 1508.01097 . doi :10.1142/S021819591750008X. SEÑOR  3766097. S2CID  47260245.
• Gardner, Martín (octubre de 1976). "Problemas combinatorios, algunos antiguos, otros nuevos y todos recién atacados por computadora". Juegos matemáticos. Científico americano . vol. 235, núm. 4. págs. 131-137. JSTOR  24950467.
• Chico, RK ; Kelly, Pensilvania (1968). "El problema de los tres en línea". Boletín de Matemáticas Canadiense . 11 (4): 527–531. doi : 10.4153/CMB-1968-062-3 . SEÑOR  0238765.
• Salón, baño; Jackson, TH; Sudbery, A.; Salvaje, K. (1975). "Algunos avances en el problema de los tres en línea". Revista de teoría combinatoria . Serie A. 18 (3): 336–341. doi : 10.1016/0097-3165(75)90043-6 .
• Harborth, Heiko ; Oertel, Philipp; Prellberg, Thomas (1989). "No hay tres en fila para diecisiete y diecinueve". Actas de la reunión de Oberwolfach “Kombinatorik” (1986). Matemáticas discretas . 73 (1–2): 89–90. doi : 10.1016/0012-365X(88)90135-5 . SEÑOR  0974815.
• Jarník, Vojtěch (1926). "Über die Gitterpunkte auf konvexen Kurven" [Sobre los puntos de la cuadrícula en curvas convexas]. Mathematische Zeitschrift (en alemán). 24 (1): 500–518. doi :10.1007/BF01216795. SEÑOR  1544776. S2CID  117747514.
• Klarreich, Erica (31 de mayo de 2016). "La prueba de juego de conjuntos simples aturde a los matemáticos". Cuantos .
• Kløve, Torleiv (1978). "Sobre el problema de los tres en línea. II". Revista de teoría combinatoria . Serie A. 24 (1): 126–127. doi : 10.1016/0097-3165(78)90053-5 . SEÑOR  0462998.
• Kløve, Torleiv (1979). "Sobre el problema de los tres en línea. III". Revista de teoría combinatoria . Serie A. 26 (1): 82–83. doi :10.1016/0097-3165(79)90055-4. SEÑOR  0525088.
• Komlós, J .; Pintz, J .; Szemerédi, E. (1982). "Un límite inferior para el problema de Heilbronn". Revista de la Sociedad Matemática de Londres . 25 (1): 13–24. doi :10.1112/jlms/s2-25.1.13. SEÑOR  0645860.
• Knuth, Donald E. (2008). "Respuesta al ejercicio 242". El arte de la programación informática, fascículo 1b: borrador de la sección 7.1.4: Diagramas de decisión binaria . pag. 130.
• Ku, Cheng Sí; Wong, Kok Bin (2018). "Sobre el problema de no tres en línea en un toro de m dimensiones". Gráficas y Combinatoria . 34 (2): 355–364. doi :10.1007/s00373-018-1878-8. SEÑOR  3774457. S2CID  3935268.
• Misiak, Aleksander; Stępień, Zofia; Szymaszkiewicz, Alicja; Szymaszkiewicz, Lucjan; Zwierzchowski, Maciej (2016). "Una nota sobre el problema del no tres en línea en un toroide". Matemáticas discretas . 339 (1): 217–221. arXiv : 1406.6713 . doi :10.1016/j.disc.2015.08.006. SEÑOR  3404483. S2CID  40210322.
• Pach, János ; Thiele, Torsten; Toth, Géza (1998). "Dibujos cuadriculados tridimensionales de gráficos". Dibujo de gráficas, 5to Int. Símp., GD '97 . Apuntes de conferencias sobre informática. vol. 1353. Springer-Verlag. págs. 47–51. doi : 10.1007/3-540-63938-1_49 .
• Payne, Michael S.; Madera, David R. (2013). "Sobre el problema de selección de subconjuntos de posiciones generales". Revista SIAM de Matemática Discreta . 27 (4): 1727-1733. arXiv : 1208.5289 . doi :10.1137/120897493. SEÑOR  3111653. S2CID  7164626.
• Pegg, Ed Jr. (11 de abril de 2005). "Tareas de tablero de ajedrez". Juegos de Matemáticas . Asociación Matemática de América . Consultado el 25 de junio de 2012 .
• Por, Atila; Madera, David R. (2007). "No tres en línea en 3D". Algorítmica . 47 (4): 481. doi :10.1007/s00453-006-0158-9. S2CID  209841346.
• Roth, KF (1951). "Sobre un problema de Heilbronn". Revista de la Sociedad Matemática de Londres . 26 (3): 198–204. doi :10.1112/jlms/s1-26.3.198.
• Madera, David R. (2005). "Dibujos de cuadrícula de k-gráficos coloreables". Geometría computacional: teoría y aplicaciones . 30 (1): 25–28. doi : 10.1016/j.comgeo.2004.06.001 .

enlaces externos

• Flammenkamp, ​​Achim. "El problema de los tres en línea".
• Weisstein, Eric W. "El problema de los tres en línea". MundoMatemático .