해피 엔딩 문제 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Happy-End-problem.svg|섬네일|300x300픽셀| 해피 엔딩 문제: 일반적인 위치에 있는 다섯 점의 모든 집합은 볼록 사변형의 꼭짓점을 포함한다.]]

'''해피 엔딩 문제'''({{llang|en|happy ending problem}})는 [[수학]]에서 다음 명제이다: {{수학 정리|정리|평면 위에서 [[일반 위치]]<ref>어느 두 점도 일치하지 않고, 어느 세 점도 한 직선 위에 있지 않은 위치이다.</ref>에 있는 임의의 점 다섯 개의 집합은 볼록 사각형을 이루는 점 네 개의 부분집합을 갖는다.}}[[에르되시 팔]]이 이러한 이름을 명명하였는데, 정리를 증명한 [[세케레시 죄르지]]와 [[세케레시 에스더|클라인 에스더]]의 결혼으로 이어졌기 때문이다.<ref>[http://www.smh.com.au/news/obituaries/a-world-of-teaching-and-numbers--times-two/2005/11/06/1131211943674.html A world of teaching and numbers - times two], [[Michael Cowling]], [[The Sydney Morning Herald]], 2005-11-07, cited 2014-09-04</ref> 이는 [[램지 이론]]의 발전으로 이어진 독창적인 결과 중 하나이다.

해피 엔딩 정리는 간단한 사례 분석으로 증명할 수 있다. 4개 이상의 점이 [[볼록 껍질]]의 꼭짓점인 경우 이러한 점 4개를 선택한다. 반면에 볼록 껍질이 내부에 두 개의 점이 있는 [[삼각형]] 형태인 경우 두 개의 내부 점과 삼각형의 모서리 중 하나를 선택할 수 있다. 이 증명에 대한 설명을 보려면 {{하버드 인용 본문|Peterson|2000}} 을 참조할 수 있다. 문제에 대한 보다 자세한 조사는 {{하버드 인용 본문|Morris|Soltan|2000}}을 참조할 수 있다.

'''에르되시-세케레시 추측'''은 일반 위치 점 집합의 점 수와 가장 큰 볼록 [[다각형]] 사이의 보다 일반적인 관계를 정확하게 나타내는 다음 명제이다. 일반 위치에 있는 점 <math>2^{n-2} + 1</math>개의 집합은 볼록 <math>n</math>각형을 포함한다. 에르되시-세케레시 추측은 증명되지 않은 채로 남아 있지만 덜 정확한 경계는 알려져 있다.

== 더 큰 다각형 ==
[[파일:8-points-no-pentagon.svg|섬네일| 볼록 오각형이 없는 일반적인 위치에 있는 8개의 점 집합]]
1935년 에르되시와 세케레시는 일반화된 다음 명제를 증명했다.
{{수학 정리|정리|양의 [[정수]] {{mvar|N}}에 대해, 임의의 충분히 큰 평면 위의 일반 위치에 있는 점들의 집합은 볼록 {{mvar|N}}각형을 이루는 부분집합을 갖는다.}}
증명은 수열의 단조 부분 수열에 대한 [[에르되시–세케레시 정리]]를 증명하는 동일한 논문에 나타났다.

{{수학|''f''(''N'')}}를 평면 위의 일반 위치에 있는 점 {{수학 변수|M}}개의 집합이 볼록 <math>N</math>각형을 포함해야 하는 최소 {{수학 변수|M}}으로 표시하자. 이와 관해 다음 사실이 알려져 있다.

* {{수학|1=''f''(3) = 3}}. 이는 자명하다.
* {{수학|1=''f''(4) = 5}}.<ref>클라인 에스더에 의해 증명된 본래의 해피 엔딩 문제의 결과이다.</ref>
* {{수학|1=''f''(5) = 9}}.<ref>{{하버드 인용 본문|Erdős|Szekeres|1935}}에 따르면, 이는 E. Makai에 의해 처음 증명되었다. 처음으로 출판된 증명은 {{하버드 인용 본문|Kalbfleisch|Kalbfleisch|Stanton|1970}}이다.</ref> 볼록 [[오각형]]이 없는 점 8개의 집합이 그림에 나와 있으며, 이는 {{수학|''f''(5) > 8}}임을 보여준다. 증명의 어려운 부분은 일반적인 위치에 있는 모든 9개의 점 집합이 볼록 오각형의 꼭짓점을 포함한다는 것을 밝히는 것이다.
* {{수학|1=''f''(6) = 17}}.<ref>{{하버드 인용 본문|Szekeres|Peters|2006}}에 의해 증명되었다. They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations.</ref>
* {{수학|''f''(''N'')}}의 값은 모든 {{수학|''N'' > 6}} 에 대해 알려져 있지 않다. {{하버드 인용 본문|Erdős|Szekeres|1935}}의 결과에 따르면 {{수학|''f''(''N'')}}는 모든 양의 정수 {{수학|''N''}}에 대해 유한하다.

''N'' = 3, 4 및 5에 대해 알려진 {{수학|''f''(''N'')}} 값을 기반으로 에르되시와 세케레시는 원래 논문에서 다음과 [[추측]]했다: 모든 <math>N \ge 3</math>에 대해 <math>f(N) = 1 + 2^{N - 2}</math>이다.

그들은 나중에 명백한 예를 구성하여 <math>f(N) \geq 1 + 2^{N - 2}</math>을 증명했다.<ref>{{하버드 인용 본문|Erdős|Szekeres|1961}}</ref>

{{수학|''N'' ≥ 7}}일 때 알려진 가장 좋은 상한은 <math display="inline">f(N) \leq 2^{N + o(N)}</math>이다.<ref>{{하버드 인용 본문|Suk|2016}}. See [[이항 계수|binomial coefficient]] and [[점근 표기법|big O notation]] for notation used here and [[카탈랑 수|Catalan numbers]] or [[스털링 근사|Stirling's approximation]] for the asymptotic expansion.</ref>

== 빈 볼록 다각형 ==
일반 위치에 있는 점들의 충분히 큰 집합이 집합의 다른 점을 포함하지 않는 "빈" 볼록 사각형, 오각형 등이 존재하는지 여부에 대한 질문을 할 수 있다. 해피 엔딩 문제에 대한 원래의 해는 그림과 같이 일반 위치에 있는 5개의 점이 비어 있는 볼록 사변형을 갖는다는 것을 나타내도록 적용될 수 있고, 모든 일반 위치에 있는 점 10개의 집합이 비어 있는 볼록 오각형을 갖는다.<ref>{{하버드 인용 본문|Harborth|1978}}.</ref> 그러나 빈 볼록 [[칠각형]]을 포함하지 않는 충분히 큰 일반 위치에 있는 점들의 집합이 존재한다.<ref>{{하버드 인용 본문|Horton|1983}}</ref>

오랫동안 빈 [[육각형]]의 존재에 대한 질문은 열려 있었지만, {{하버드 인용 본문|Nicolás|2007}} 와 {{하버드 인용 본문|Gerken|2008}} 은 임의의 충분히 큰 일반 위치에 있는 점들의 집합이 빈 볼록 육각형을 포함한다는 것을 증명했다. 보다 구체적으로, Gerken은 위에서 정의한 동일한 함수 ''f''에 대해 필요한 포인트 수가 ''f''(9) 이하임을 보였고 Nicolás는 필요한 점 수가 ''f'' (25) 이하임을 보였다. {{하버드 인용 본문|Valtr|2008}}은 Gerken의 증명을 단순화했지만 ''f''(9) 대신 점 ''f''(15)개로 점을 더 많이 요구한다. 최소한 점 30개가 필요한데, 빈 볼록 육각형이 없는 일반 위치의 점 29개의 집합이 존재한다.<ref>{{하버드 인용 본문|Overmars|2003}}.</ref>

== 관련 문제 ==
볼록 사각형의 수를 최소화하는 ''n''개의 점 집합을 찾는 문제는 [[완전 그래프|완전한 그래프]]의 직선 [[그래프 그리기|그리기]]에서 [[교차 수(그래프 이론)|교차 수]]를 최소화하는 것과 같다. 사각형의 수는 ''n''의 네제곱에 비례하지만 정확한 상수는 알려져 있지 않다.<ref>{{하버드 인용 본문|Scheinerman|Wilf|1994}}</ref>

고차원 [[유클리드 공간]]에서 충분히 큰 점 집합은 차원보다 큰 임의의 <math>k</math>에 대해 [[볼록 다포체]]의 꼭짓점을 형성하는 점 <math>k</math>개의 부분 집합을 가진다. 이는 고차원 점 집합을 임의의 2차원 부분 공간으로 투영함으로써, 충분히 큰 평면 점 집합에서 볼록 <math>k</math>각형의 존재로부터 즉시 보여진다. 그러나 [[볼록 위치]]에 있는 <math>k</math>개의 점을 찾는 데 필요한 점의 수는 평면에서보다 고차원에서 더 작을 수 있으며 더 많이 구속된 부분 집합을 찾는 것이 가능하다. 특히, <math>d</math>차원에서 모든 일반 위치에 있는 <math>d+3</math>개의 점은 [[순환 폴리토프|순환 다포체]]의 꼭짓점을 형성하는 점 <math>d+2</math>개의 부분 집합을 갖는다.<ref>{{하버드 인용 본문|Grünbaum|2003}}, Ex. 6.5.6, p.120. Grünbaum attributes this result to a private communication of Micha A. Perles.</ref> 보다 일반적으로 모든 <math>k>d</math>인 <math>d</math> 및 <math>k</math>에 대해 모든 일반 위치에 있는 점 <math>m(k, d)</math>개의 집합이 [[인접 폴리토프|인접 다포체]]의 꼭짓점을 형성하는 점 ''<math>k</math>''개의 부분 집합을 갖도록 하는 수 <math>m(k, d)</math>가 존재한다.<ref>{{하버드 인용 본문|Grünbaum|2003}}, Ex. 7.3.6, p. 126. This result follows by applying a Ramsey-theoretic argument similar to Szekeres's original proof together with Perles's result on the case ''k''&nbsp;=&nbsp;''d''&nbsp;+&nbsp;2.</ref>

== 각주 ==
{{각주|2}}

== 참고 문헌 ==
{{참고 자료 시작|2}}
* {{인용|last1=Chung|first1=F.R.K.|author1-link=Fan Chung|last2=Graham|first2=R.L.|author2-link=Ronald Graham|doi=10.1007/PL00009353|journal=[[Discrete and Computational Geometry]]|pages=367–371|issue=3|title=Forced convex n-gons in the plane|volume=19|year=1998|doi-access=free}}.
* {{인용|last1=Erdős|first1=P.|author1-link=에르되시 팔|last2=Szekeres|first2=G.|author2-link=세케레시 죄르지|journal=[[Compositio Mathematica]]|pages=463–470|title=A combinatorial problem in geometry|url=http://www.numdam.org/item?id=CM_1935__2__463_0|volume=2|year=1935}}.
* {{인용|last1=Erdős|first1=P.|author1-link=에르되시 팔|last2=Szekeres|first2=G.|author2-link=세케레시 죄르지|journal=Ann. Univ. Sci. Budapest. Eötvös Sect. Math.|pages=53–62|title=On some extremum problems in elementary geometry|volume=3–4|year=1961}}. Reprinted in: {{인용|last=Erdős|first=P.|author-link=에르되시 팔|editor-last=Spencer|editor-first=J.|location=Cambridge, MA|pages=680–689|publisher=MIT Press|title=The Art of Counting: Selected Writings|year=1973}}.
* {{인용|last=Gerken|first=Tobias|doi=10.1007/s00454-007-9018-x|issue=1–3|journal=[[Discrete and Computational Geometry]]|pages=239–272|title=Empty convex hexagons in planar point sets|volume=39|year=2008|doi-access=free}}.
* {{인용|last=Grünbaum|editor3-first=Günter M.|volume=221|title-link=Convex Polytopes|title=Convex Polytopes|series=Graduate Texts in Mathematics|publisher=[[슈프링어|Springer-Verlag]]|isbn=0-387-00424-6|editor3-link=Günter M. Ziegler|editor3-last=Ziegler|first=Branko|editor2-link=Victor Klee|editor2-first=Victor|editor2-last=Klee|editor1-first=Volker|editor1-last=Kaibel|edition=2nd|authorlink=Branko Grünbaum|year=2003}}.
* {{인용|last=Harborth|first=Heiko|issue=5|journal=Elemente der Mathematik|pages=116–118|title=Konvexe Fünfecke in ebenen Punktmengen|volume=33|year=1978}}.
* {{인용|doi=10.4153/CMB-1983-077-8|last=Horton|first=J. D.|issue=4|journal=[[Canadian Mathematical Bulletin]]|pages=482–484|title=Sets with no empty convex 7-gons|volume=26|year=1983}}.
* {{인용|last1=Kalbfleisch|first1=J.D.|last2=Kalbfleisch|first2=J.G.|author2-link=James G. Kalbfleisch|last3=Stanton|first3=R.G.|title=Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing|publisher=Louisiana State Univ.|location=Baton Rouge, La.|series=Congressus Numerantium|pages=180–188|contribution=A combinatorial problem on convex regions|volume=1|year=1970}}.
* {{인용|last1=Kleitman|first1=D.J.|author1-link=Daniel Kleitman|last2=Pachter|first2=L.|author2-link=Lior Pachter|doi=10.1007/PL00009358|journal=[[Discrete and Computational Geometry]]|pages=405–410|issue=3|title=Finding convex sets among points in the plane|volume=19|year=1998|url=https://authors.library.caltech.edu/74983/1/art%253A10.1007%252FPL00009358.pdf|doi-access=free|access-date=2022-05-03|archive-date=2022-02-04|archive-url=https://web.archive.org/web/20220204064547/https://authors.library.caltech.edu/74983/1/art%253A10.1007%252FPL00009358.pdf|url-status=}}.
* {{인용|last1=Morris|first1=W.|last2=Soltan|first2=V.|doi=10.1090/S0273-0979-00-00877-6|journal=[[Bulletin of the American Mathematical Society]]|pages=437–458|title=The Erdős-Szekeres problem on points in convex position—A survey|issue=4|volume=37|year=2000|doi-access=free}}.
* {{인용|last=Nicolás|first=Carlos M.|doi=10.1007/s00454-007-1343-6|issue=2|journal=[[Discrete and Computational Geometry]]|pages=389–397|title=The empty hexagon theorem|volume=38|year=2007|doi-access=free}}.
* {{인용|last=Overmars|first=M.|author-link=Mark Overmars|doi=10.1007/s00454-002-2829-x|journal=[[Discrete and Computational Geometry]]|pages=153–158|title=Finding sets of points without empty convex 6-gons|issue=1|volume=29|year=2003|doi-access=free}}.
* {{인용|last=Peterson|first=Ivars|authorlink=Ivars Peterson|journal=MAA Online|title=Planes of Budapest|url=http://www.maa.org/mathland/mathtrek_10_3_00.html|archive-url=https://web.archive.org/web/20130702060326/http://www.maa.org/mathland/mathtrek_10_3_00.html|archive-date=2013-07-02|url-status=dead|year=2000}}.
* {{인용|last1=Scheinerman|first1=Edward R.|author1-link=Ed Scheinerman|last2=Wilf|first2=Herbert S.|author2-link=Herbert Wilf|doi=10.2307/2975158|issue=10|journal=[[American Mathematical Monthly]]|pages=939–943|title=The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability|volume=101|year=1994|publisher=Mathematical Association of America|jstor=2975158}}.
* {{인용|last=Suk|first=Andrew|doi=10.1090/jams/869|journal=J. Amer. Math. Soc.|title=On the Erdős–Szekeres convex polygon problem|year=2016|volume=30|issue=4|pages=1047–1053|arxiv=1604.08657|s2cid=15732134}}.
* {{인용|last1=Szekeres|first1=G.|author1-link=세케레시 죄르지|last2=Peters|first2=L.|doi=10.1017/S144618110000300X|journal=[[ANZIAM Journal]]|pages=151–164|title=Computer solution to the 17-point Erdős-Szekeres problem|issue=2|url=http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html|volume=48|year=2006|doi-access=free|access-date=2022-05-03|archive-date=2019-12-13|archive-url=https://web.archive.org/web/20191213025301/http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html|url-status=}}.
* {{인용|last1=Tóth|first1=G.|last2=Valtr|first2=P.|doi=10.1007/PL00009363|journal=[[Discrete and Computational Geometry]]|pages=457–459|title=Note on the Erdős-Szekeres theorem|issue=3|volume=19|year=1998|doi-access=free}}.
* {{인용|last1=Tóth|editor1-first=Jacob E.|editor3-link=Emo Welzl|editor3-last=Welzl|editor3-first=Emo|editor2-link=János Pach|editor2-last=Pach|editor2-first=János|editor1-link=Jacob E. Goodman|editor1-last=Goodman|url=http://library.msri.org/books/Book52/files/30toth.pdf|first1=G.|title=Combinatorial and Computational Geometry|publisher=Cambridge University Press|volume=52|series=Mathematical Sciences Research Institute Publications|pages=557–568|contribution=The Erdős-Szekeres theorem: upper bounds and related results|first2=P.|last2=Valtr|year=2005|access-date=2022-05-03|archive-date=2019-07-28|archive-url=https://web.archive.org/web/20190728224026/http://library.msri.org/books/Book52/files/30toth.pdf|url-status=}}.
* {{인용|last=Valtr|editor1-last=Goodman|editor3-link=Richard M. Pollack|editor3-last=Pollack|editor3-first=Richard|editor2-link=János Pach|editor2-last=Pach|editor2-first=János|editor1-link=Jacob E. Goodman|editor1-first=Jacob E.|first=P.|publisher=American Mathematical Society|series=Contemporary Mathematics|volume=453|title=Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, June 18-22, 2006, Snowbird, Utah|year=2008|url=http://kam.mff.cuni.cz/~valtr/h.ps|pages=433–442|contribution=On empty hexagons|isbn=9780821842393}}.
{{참고 자료 끝}}

== 외부 링크 ==

* [[플래닛매스|PlanetMath]]에서 [https://web.archive.org/web/20060925032614/http://planetmath.org/encyclopedia/HappyEndingProblem.html 해피 엔딩 문제] 및 [https://web.archive.org/web/20060925032736/http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html Erdős-Szekeres 정리의 Ramsey 이론 증명]
* {{매스월드|title=Happy End Problem|urlname=HappyEndProblem}}

[[분류:에르되시 팔]]
[[분류:램지 이론]]
[[분류:수학 문제]]
[[분류:다각형]]
[[분류:사각형]]
[[분류:유클리드 평면기하학]]
[[분류:이산기하학]]