Lösung des Obstgartenproblems: eine Anordnung von neun Punkten, bei der auf zehn Geraden jeweils drei Punkte liegen

Als Obstgarten-Problem (englisch orchard problem) wird in der Mathematik die folgende Fragestellung bezeichnet: Wie können neun Obstbäume so angeordnet werden, dass sich zehn Sichtachsen mit jeweils drei Bäumen ergeben? Das allgemeinere Problem, wie Punkte in der Ebene so angeordnet werden können, dass möglichst viele Geraden mit jeweils Punkten darauf existieren, beschäftigt Mathematiker bis heute.

Obstgarten-Folge

Bearbeiten

Sei   die maximale Anzahl von Geraden mit drei Punkten, die in einer Konfiguration von   Punkten in der Ebene existieren können. Die ersten Glieder dieser Folge sind:

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

Diese Folge wird als Folge A003035 in OEIS aufgeführt.

Upper and lower bounds

Bearbeiten

Since no two lines may share two distinct points, a trivial upper-bound for the number of 3-point lines determined by n points is

 

Using the fact that the number of 2-point lines is at least 6n/13 Vorlage:Harv, this upper bound can be lowered to

 

Lower bounds for t3orchard(n) are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of ~(1/8)n2 was given by Sylvester, who placed n points on the cubic curve y = x3. This was improved to [(1/6)n2 − (1/2)n] + 1 in 1974 by Vorlage:Harvs, using a construction based on Weierstrass's elliptic functions. An elementary construction using hypocycloids was found by Vorlage:Harvtxt achieving the same lower bound.

In September 2013, Ben Green and Terence Tao published a paper in which they prove that for all point sets of sufficient size, n > n0, there are at most ([n(n - 3)/6]  + 1) = [(1/6)n2 − (1/2)n + 1] 3-point lines which matches the lower bound established by Burr, Grünbaum and Sloane.[1] Thus, for sufficiently large n, the exact value of t3orchard(n) is known.

This is slightly better than the bound that would directly follow from their tight lower bound of n/2 for the number of 2-point lines: [n(n − 2)/6], proved in the same paper and solving a 1951 problem posed independently by Gabriel Andrew Dirac and Theodore Motzkin

Orchard-planting problem has also been considered over finite fields. In this version of the problem, the n points lie in a projective plane defined over a finite field.Vorlage:Harv.

Vorlage:Reflist

References

Bearbeiten
  1. Vorlage:Harvtxt