查看“︁種樹問題”︁的源代码

{{for2|算術應用題|{{link-ja|植樹問題|植木算}}}}
[[File:Orchard-planting_problem.svg|缩略图|安排的九点(相关的冠毛配置)形成3点线。]]
在[[離散幾何]]中，原始的'''果園种植问题'''要求的是在一個平面中過定点的3点线的可达到的最大数量。它也被称为植树造林问题，或只簡稱為果園问题。也可以是研究有多少k点线可以存在。Hallard T.克罗夫特和[[埃尔德什·帕尔]]证明了''t''<sub>''k''</sub>&#x20;>&#x20;''c'' ''n''<sup>2</sup>&#x20;/&#x20;''k''<sup>3</sup>，''n''是点的数量並且''t''<sub>''k''</sub>是''k''点线的数量。<ref>''The Handbook of Combinatorics'', edited by [[László_Lovász]],  {[[葛立恒]], et al, in the chapter titled ''Extremal Problems in Combinatorial Geometry'' by [[Paul_Erdős]] and {{Tsl|en|George_B._Purdy}}.</ref>

他们的構造物包含了一些m-点线，其中m>k。你也可以问，如果这些是不允许的问题。

== 整数序列 ==
定义''t''<sub>3</sub><sup>果園</sup>(''n'')为過''n''定点可達到的3点线的最大数量。

在1974年，对于任意的正整數点''n''、''t''<sub>3</sub><sup>果園</sup>(''n'')被證明是(1/6)''n''<sup>2</sup>&#x20;&#x2212;&#x20;O(n)。

第一個''t''<sub>3</sub><sup>果園</sup>(''n'')的数值在右表中{{OEIS|A003035}}.
{| class="wikitable" style="margin-bottom: 10px;"
! n
! 4
! 5
! 6
! 7
! 8
! 9
! 10
! 11
! 12
! 13
! 14
|-
| '''''t''<sub>3</sub><sup>果園</sup>(''n'')'''
| 1
| 2
| 4
| 6
| 7
| 10
| 12
| 16
| 19
| 22
| 26
|}

== 上極限和下極限 ==
由于没有两个直线可以共同經過两个不同点，一个[[平凡_(數學)|平凡的]]3点线的数量上限由以下''n''点的情況确定
: <math>\left\lfloor\binom{n}{2}\Big/\binom{3}{2}\right\rfloor=\left\lfloor\frac{n^2-n}{6}\right\rfloor.</math>
事实是[[西爾維斯特-加萊定理#推廣|数的2点线]]至少是6''n''/13 {{Harvard citation|Csima|Sawyer|1993}}，该上限可以降低到
: <math>\left\lfloor\frac{\binom{n}{2}-6n/13}{3}\right\rfloor=\left\lfloor\frac{n^2}{6}-\frac{25n}{78}\right\rfloor.</math>

''t''<sub>3</sub><sup>果園</sup>(''n'')的下限由通过定点的许多的3点线的構造給出。最早的二次方程式下限-(1/8)''n''<sup>2</sup>由[[詹姆斯·約瑟夫·西爾維斯特|西尔维斯特]]給出，他在三次曲线''y'' = ''x''<sup>3</sup>放了''n''個点。这在1974年由{{Harvard citations|txt|last1=Burr|last2=Grünbaum|last3=Sloane|author1-link=Stefan Burr|author2-link=Branko Grünbaum|author3-link=Neil Sloane|year=1974}}采用一个[[魏爾斯特拉斯橢圓函數]]基础上的结构改善至[(1/6)''n''<sup>2</sup>&#x20;&#x2212;&#x20;(1/2)''n'']&#x20;+&#x20;1。一個{{Harvard citation text|Füredi|Palásti|1984}}建立的[[圆内螺线]]基本的構造取得了相同的下限。

在2013年九月, Ben Green和[[陶哲轩]]發表的一篇论文中，他们证明了所有的点集必然的大小，''n'' &#x3E; ''n''<sub>0</sub>，至多有([''n''(''n''&nbsp;-&nbsp;3)/6] &nbsp;+&nbsp;1) =  [(1/6)''n''<sup>2</sup>&nbsp;&#x2212;&nbsp;(1/2)''n''&nbsp;+&nbsp;1] 3点线，其中相應的下限由Burr, Grünbaum和Sloane確立。<ref>{{Harvard citation text|Green|Tao|2013}}</ref> 這有一個比直接从他們的紧的下限得出的[[西爾維斯特-加萊定理|2点线]]的數''n''/2要略胜一筹的極限：[''n''(''n'' &#x2212; 2)/6]，分別由Gabriel Andrew Dirac和Theodore Motzkinproved 在相同的论文中和解决一個1951問題以独立地身份证明。

== 注釋 ==
{{reflist|2}}

== 参考文献 ==
* {{citation|title=Research Problems in Discrete Geometry|last1=Brass|first1=P.|last2=Moser|first2=W. O. J.|last3=Pach|first3=J.|authorlink3=János Pach|publisher=Springer-Verlag|year=2005|ISBN=0-387-23815-8}}.
* {{citation|title=The Orchard problem|last1=Burr|first1=S. A.|authorlink1=Stefan Burr|last2=Grünbaum|first2=B.|authorlink2=Branko Grünbaum|last3=Sloane|first3=N. J. A.|authorlink3=Neil Sloane|journal=[[Geometriae Dedicata]]|volume=2|issue=4|pages=397–424|year=1974|doi=10.1007/BF00147569}}.
* {{citation| last1 = Csima | first1 = J. | last2 = Sawyer | first2 = E.| title = There exist 6''n''/13 ordinary points| journal = [[Discrete and Computational Geometry]]| year = 1993| volume = 9| pages = 187–202| doi = 10.1007/BF02189318}}.
* {{citation|title=Arrangements of lines with a large number of triangles|last1=Füredi|last2=Palásti|first1=Z.|first2=I.|author1-link=Zoltán Füredi|journal=[[Proceedings of the American Mathematical Society]]|volume=92|issue=4|pages=561–566|year=1984|jstor=2045427|doi=10.2307/2045427}}.
* <ref name=GreenTao2013>{{Citation |last1=Green|first1=Ben|author1-link=Ben Green (mathematician)|last2=Tao|first2=Terence|author2-link=陶哲軒|title=On sets defining few ordinary lines|journal = [[Discrete and Computational Geometry]]|year=2013|doi=    10.1007/s00454-013-9518-9|volume=50|issue=2|pages = 409–468}}</ref>

== 外部連結 ==
* {{MathWorld |title=Orchard-Planting Problem|urlname=Orchard-PlantingProblem}}
[[Category:離散幾何]]
[[Category:平面幾何]]
[[Category:数学问题]]