Problema de l'hort

Una disposició de nou punts (relacionada amb la configuració de Pappus) formant deu línies de 3 punts.

En geometria discreta, el problema de l'hort demana el màxim nombre de línies de 3 punts assolibles per una configuració de punts en el pla. També s'anomena problema de plantar arbres o simplement el problema de l'hort. També hi ha investigacions sobre quantes línies de punts k hi pot haver. Hallard T. Croft and Paul Erdős han demostrat t_k > c n² / k³, on n és el nombre de punts i t_k és el nombre de línies 'k. La seva construcció conté algunes línies de m punts, on m> k. També es pot fer la pregunta si aquests no estan permesos.

Seqüència de nombre enter

Definiu t₃^hort(n) com el nombre màxim de línies de 3 punts assolibles amb una configuració de n punts. Per a un nombre arbitrari de punts, n, t₃^hort(n) va ser (1/6)n² − O(n) el 1974.

Els primers valors de t₃^hort(n) es donen a la taula següent (successió A003035 a l'OEIS).

n	4	5	6	7	8	9	10	11	12	13	14
t3hort(n)	1	2	4	6	7	10	12	16	19	22	26

Límits superiors i inferiors

Atès que cap de les dues línies pot compartir dos punts diferents, un límit superior trivial per al nombre de línies de 3 punts determinades per n punts és

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

Utilitzant el fet que el nombre de línies de 2 punts és com a mínim 6n/13 (Csima & Sawyer 1993), aquest superior lligat pot ser abaixat a

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

Els límits inferiors per a t₃^hort(n) veuen construccions per a conjunts de punts amb moltes línies de 3 punts. El límit quadràtic més primerenc de ~ (1/8)n² va ser donat per Sylvester, que va col·locar n punts a la corba cúbica y = x³. Això va ser millorat per [(1/6)n² − (1/2)n] + 1 el 1974 per (txt), emprant una construcció basada en les funcions el·líptiques de Weierstrass.

Al setembre de 2013, Ben Green i Terence Tao van publicar un document en el qual demostren que per a tots els conjunts de punts de mida suficient, n > n₀, hi ha com a màxim ([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] línies de 3 punts que aparella el més baix va lligar establert per Burr, Grünbaum i Sloane. Això és lleugerament més ben que el lligat que directament seguiria del seu estanc més baix lligat de n/2 pel nombre de línies de 2 punts: [n(n − 2)/6], es va demostrar en el mateix document i es va resoldre un problema de 1951 plantejat de forma independent per Gabriel Andrew Dirac i Theodore Motzkin.

Referències

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

Enllaços externs

• Weisstein, Eric W., «Orchard-Planting Problem» a MathWorld (en anglès).