種樹問題

  關於算術應用題，請見植樹問題。

安排的九點(相關的冠毛配置)形成3點線。

在離散幾何中，原始的果園種植問題要求的是在一個平面中過定點的3點線的可達到的最大數量。它也被稱為植樹造林問題，或只簡稱為果園問題。也可以是研究有多少k點線可以存在。Hallard T.克羅夫特和埃爾德什·帕爾證明了t_k > c n² / k³，n是點的數量並且t_k是k點線的數量。

他們的構造物包含了一些m-點線，其中m>k。你也可以問，如果這些是不允許的問題。

整數序列

定義t₃^果園(n)為過n定點可達到的3點線的最大數量。

在1974年，對於任意的正整數點n、t₃^果園(n)被證明是(1/6)n² − O(n)。

第一個t₃^果園(n)的數值在右表中（OEIS數列A003035）.

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

上極限和下極限

由於沒有兩個直線可以共同經過兩個不同點，一個平凡的3點線的數量上限由以下n點的情況確定

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

事實是數的2點線至少是6n/13 (Csima & Sawyer 1993)，該上限可以降低到

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

t₃^果園(n)的下限由通過定點的許多的3點線的構造給出。最早的二次方程式下限-(1/8)n²由西爾維斯特給出，他在三次曲線y = x³放了n個點。這在1974年由 Burr, Grünbaum, and Sloane （1974）採用一個魏爾斯特拉斯橢圓函數基礎上的結構改善至[(1/6)n² − (1/2)n] + 1。一個Füredi & Palásti (1984)建立的圓內螺線基本的構造取得了相同的下限。

在2013年九月, Ben Green和陶哲軒發表的一篇論文中，他們證明了所有的點集必然的大小，n > n₀，至多有([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] 3點線，其中相應的下限由Burr, Grünbaum和Sloane確立。 這有一個比直接從他們的緊的下限得出的2點線的數n/2要略勝一籌的極限：[n(n − 2)/6]，分別由Gabriel Andrew Dirac和Theodore Motzkinproved 在相同的論文中和解決一個1951問題以獨立地身份證明。

參考文獻

• 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, 1974, 2 (4): 397–424, doi:10.1007/BF00147569 .
• Csima, J.; Sawyer, E., There exist 6n/13 ordinary points, Discrete and Computational Geometry, 1993, 9: 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, 1984, 92 (4): 561–566, JSTOR 2045427, doi:10.2307/2045427 .

外部連結

• 埃里克·韋斯坦因. Orchard-Planting Problem. MathWorld.