과수원 재배 문제

이산형 기하학에서 원래의 과수원 재배 문제는 평면의 특정 점수의 구성으로 얻을 수 있는 최대 3점선 수를 요구한다.나무를 심는 문제 또는 단순히 과수원 문제라고도 한다.k포인트 라인이 얼마나 있을 수 있는지에 대한 조사도 있다.할라드 T.크로프트와 폴 에르디스는 t_k > c² n / k를³ 증명했는데 여기서 n은 포인트 수, t는_k k 포인트 라인 수다.^[1]그들의 구조는 m > k 몇 개의 m-point 선을 포함한다.이것들이 허용되지 않는지 질문할 수도 있다.

정수순서

t₃^orchard(n)를 n개의 점 구성으로 얻을 수 있는 최대 3점선 수로 정의한다.임의의 수의 점 n, t₃^orchard(n)은 1974년에 (1/6)n² - O(n)로 표시되었다.

t₃^orchard(n)의 처음 몇 값은 다음 표에 제시되어 있다(OEIS의 순서 A003035).

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

상한 및 하한

두 개의 선이 두 개의 구별되는 점을 공유할 수 없으므로, n개의 점으로 결정되는 3점 라인 수에 대한 사소한 상한은 다음과 같다.

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

2점 라인 수가 최소 6n/13(Csima & Sawyer 1993)이라는 점을 이용하여 이 상한을 다음과 같이 낮출 수 있다.

${\displaystyle \left\lfloor {n}{2}}~6n/13}{3}\right\nloor =\좌측\lfloor{n^{6}}{6}-{\frac {25n}{78}}}\오른쪽\floor .}$

t₃^orchard(n)에 대한 하한은 3점선이 많은 점 집합에 대한 시공에 의해 주어진다.~(1/8)n의² 초기 2차 하한은 실베스터가 부여한 것으로, 실베스터는 입방곡선 y³ = x에 n 점을 배치했다.이는 1974년 Burr, Grünbaum, Sloane (1974년)에 의해 [(1/6)n² - (1/2)n] + 1로 개선되었으며, Weierstrass의 타원함수에 기초한 구조물을 사용했다.저포시클로이드를 이용한 기초공사가 같은 하한선을 달성한 퓨레디앤팔라스티(1984)에 의해 발견됐다.

2013년 9월, 벤 그린과 테렌스 타오는 충분한 크기 n > n의₀ 모든 포인트 세트에 대해 버르, 그룬바움, 슬로운이 설정한 하한과 일치하는 최대 ([n(n - 3)/6] + 1) = [(1/6)n² - (1/2)n + 1] 3 포인트 라인이 있음을 증명하는 논문을 발표하였다.^[2]따라서 n이 충분히 크면 t₃^orchard(n)의 정확한 값을 알 수 있다.

이는 2점 라인 수인 [n(n - 2)/6]에서 입증된 것과 같은 논문에서 가브리엘 앤드루 디락과 테오도르 모츠킨이 독자적으로 제기한 1951년 문제를 해결하는 것과 직접적으로 일치하는 바운드보다 약간 낫다.

메모들

참조

• Brass, P.; Moser, W. O. J.; Pach, J. (2005), Research Problems in Discrete Geometry, Springer-Verlag, ISBN 0-387-23815-8.
• Burr, S. A.; Grünbaum, B.; Sloane, N. J. A. (1974), "The Orchard problem", Geometriae Dedicata, 2 (4): 397–424, doi:10.1007/BF00147569, S2CID 120906839.
• Csima, J.; Sawyer, E. (1993), "There exist 6n/13 ordinary points", Discrete and Computational Geometry, 9 (2): 187–202, doi:10.1007/BF02189318.
• Füredi, Z.; Palásti, I. (1984), "Arrangements of lines with a large number of triangles", Proceedings of the American Mathematical Society, 92 (4): 561–566, doi:10.2307/2045427, JSTOR 2045427.
• Green, Ben; Tao, Terence (2013), "On sets defining few ordinary lines", Discrete and Computational Geometry, 50 (2): 409–468, arXiv:1208.4714, doi:10.1007/s00454-013-9518-9, S2CID 15813230

외부 링크

• Weisstein, Eric W. "Orchard-Planting Problem". MathWorld.