# Problema de l'hort

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$^3$, 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$^3$. 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$_0$, 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.

## Notes

* ↑ The Handbook of Combinatorics, edited by László Lovász, Ron Graham, et al, in the chapter titled Extremal Problems in Combinatorial Geometry by Paul Erdős and George B. Purdy.
* ↑ Green & Tao (2013)

## 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).