Problema del huerto

En geometría discreta, el problema original del huerto consiste en determinar el número máximo de líneas de 3 puntos que se puede alcanzar mediante una configuración dada de puntos en el plano. También se le llama el problema de la plantación de árboles o simplemente el problema de la huerta.

También se han realizado investigaciones sobre cuántas líneas de k-puntos pueden formarse. Hallard T. Croft y Paul Erdős demostraron que:

t_k > c n² / k³

donde n es el número total de puntos y t_k es el número de líneas de k-puntos.^[1]​ Su construcción contiene algunas líneas de m-puntos, donde m > k. También se puede plantear el problema en el caso de que estas configuraciones de más de k puntos alineados no están permitidas.

Secuencia de enteros

Se define t₃^huerto (n) como el número máximo de líneas de 3 puntos alcanzables con una configuración de n puntos. Para un número arbitrario de puntos n, se demostró en 1974 que t₃^huerto (n) es (1/6) n².

Los primeros valores de t₃^huerto (n) se dan en la siguiente tabla (sucesión A003035 en OEIS).

Límites superior e inferior

Puesto que no hay dos líneas que puedan compartir dos puntos distintos, un límite superior trivial para el número de líneas de 3 puntos determinado por n puntos es:

${\displaystyle \left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .}$

Utilizando el hecho de que según el Teorema de Sylvester-Gallai para el número de líneas de 2 puntos es al menos 6n/13 (Csima y Sawyer, 1993), este límite superior se puede rebajar a:

${\displaystyle \left\lfloor {\frac {{\binom {n}{2}}-6n/13}{3}}\right\rfloor =\left\lfloor {\frac {n^{2}}{6}}-{\frac {25n}{78}}\right\rfloor .}$

(donde la notación ${\displaystyle \left\lfloor x\right\rfloor }$ indica la función suelo)

Los límites inferiores para t₃^huerto(n) están dados por construcciones para conjuntos de puntos con muchas líneas de 3 puntos. El primer límite cuadrático inferior de ~(1/8)n² fue dado por Sylvester, quien situó n puntos en la curva cúbica y = x³. Esto se mejoró a [(1/6)n² − (1/2)n] + 1 en 1974 por Plantilla:Harvs, usando una construcción basada en funciones elípticas de Weierstrass. Una construcción elemental usando hipocicloides fue hallada por Füredi y Palásti (1984), logrando el mismo límite inferior.

En septiembre de 2013, Ben Green y Terence Tao publicaron un artículo en el que demuestran que para todos los conjuntos de puntos de tamaño suficiente, n > n₀, hay como máximo ([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] líneas de 3 puntos, lo que coincide con el límite inferior establecido por Burr, Grünbaum y Sloane.^[2]​ Esto es ligeramente mejor que lo que resultaría directamente de su límite inferior estricto de n/2 para el número de líneas de 2 puntos: [n(n − 2)/6], demostrado en el mismo documento y resolviendo un problema planteado independientemente por Gabriel Andrew Dirac y Theodore Motzkin en 1951.

Referencias

Bibliografía

• Brass, P.; Moser, W. O. J.; Pach, J. (2005), Research Problems in Discrete Geometry, Springer-Verlag, ISBN 0-387-23815-8 ..
• Burr, S. A.; Grünbaum, B.; Sloane, N. J. A. (1974), «The Orchard problem», Geometriae Dedicata 2 (4): 397-424, doi:10.1007/BF00147569 ..
• Csima, J.; Sawyer, E. (1993), «There exist 6n/13 ordinary points», Discrete and Computational Geometry 9: 187-202, doi:10.1007/BF02189318 ..
• Füredi, Z.; Palásti, I. (1984), «Arrangements of lines with a large number of triangles», Proceedings of the American Mathematical Society 92 (4): 561-566, JSTOR 2045427, doi:10.2307/2045427 ..
• Green, Ben; Tao, Terence (2013), «On sets defining few ordinary lines», Discrete and Computational Geometry 50 (2): 409-468, doi:10.1007/s00454-013-9518-9 .

Enlaces externos

• Weisstein, Eric W. «Orchard-Planting Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.