種樹問題

安排的九点(相关的冠毛配置)形成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)的数值在右表中Template:OEIS.

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点的情況确定

$\lfloor (\genfrac{}{}{0ex}{}{n}{2})/(\genfrac{}{}{0ex}{}{3}{2})\rfloor =\lfloor \frac{n^2-n}{6}\rfloor .$

事实是数的2点线至少是6n/13 Template:Harvard citation，该上限可以降低到

$\lfloor \frac{(\genfrac{}{}{0ex}{}{n}{2})-6n/13}{3}\rfloor =\lfloor \frac{n^2}{6}-\frac{25n}{78}\rfloor .$

t₃^果園(n)的下限由通过定点的许多的3点线的構造給出。最早的二次方程式下限-(1/8)n²由西尔维斯特給出，他在三次曲线y = x³放了n個点。这在1974年由Template:Harvard citations采用一个魏爾斯特拉斯橢圓函數基础上的结构改善至[(1/6)n² − (1/2)n] + 1。一個Template:Harvard citation text建立的圆内螺线基本的構造取得了相同的下限。

在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問題以独立地身份证明。

参考文献

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.

外部連結

• Template:MathWorld