ดูต้นฉบับสำหรับ ปัญหาแฮปปี้เอ็นดิ้ง

[[ไฟล์:Happy-End-problem.svg|thumb|250px|ปัญหาแฮปปี้เอ็นดิ้ง: สำหรับจุดห้าจุดใดๆในระนาบ จะต้องมีจุดสี่จุดซึ่งทำให้เกิดสี่เหลี่ยมนูน]]
[[ไฟล์:8-points-no-pentagon.svg|thumb|250px|เซตของจุดแปดจุดที่ไม่มีจุดห้าจุดใดๆที่ทำให้เกิดห้าเหลี่ยมนูน]]

'''ปัญหาแฮปปี้เอ็นดิ้ง''' เป็นปัญหาทาง[[คณิตศาสตร์]] ตั้งชื่อโดย[[พอล แอร์ดิช]] หลังจากปัญหานี้ทำให้เกิดการแต่งงานของ George Szekeres และ Esther Klein มีดังนี้

สำหรับจุดห้าจุดใด ๆ ในระนาบ จะต้องมีจุดสี่จุดซึ่งทำให้เกิด[[สี่เหลี่ยมนูน]]

== ปัญหาที่ใหญ่ขึ้น ==
แอร์ดิช และ Szekeres ได้พิสูจน์ทฤษฎีบทดังนี้

สำหรับจำนวนเต็มบวก N ใดๆ มีเซตจำกัดของจุดบนระนาบที่มีจุด N จุดภายในเซตนั้น ซึ่งทำให้เกิดรูป N เหลี่ยมนูน

ให้ f(N) แทนค่า M ที่น้อยที่สุดที่ทำให้เซตของจุด M จุดใดๆ จะต้องมีจุด N จุดภายในเซตนั้น ซึ่งทำให้เกิดรูป N เหลี่ยมนูน
* f(3) = 3
* f(4) = 5 (พิสูจน์โดย Esther Klein)
* f(5) = 9 (พิสูจน์โดย E. Makai ตีพิมพ์ครั้งแรกใน [[พ.ศ. 2513]])
* f(6) = 17 (พิสูจน์โดย Szekeres and Lindsay Peters โดยใช้คอมพิวเตอร์)

สำหรับ F(N) เมื่อ N เป็นจำนวนเต็มบวกใด ๆ ยังไม่มีสูตรที่ใช้หา
แอร์ดิชและ Szekeres ตั้งข้อคาดเดาไว้ว่า

:<math>f(N) = 1 + 2^{N-2} \quad \mbox{for all } N \geq 3</math>

ในปี [[พ.ศ. 2504]] แอร์ดิชและ Szekeres พิสูจน์ได้ว่า

:<math>f(N) \geq 1 + 2^{N-2}</math>

ขอบเขตบนของ f(N) เมื่อ <math>N \geq 5</math> ที่ดีที่สุดเท่าที่ทราบในปัจจุบันคือ

:<math>f(N) \leq {2N-5 \choose N-3} + 1 = \Theta\left(\frac{4^N}{\sqrt N}\right)</math>

== อ้างอิง ==
{{เริ่มอ้างอิง|2}}
*{{citation
 | 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}}.
*{{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Szekeres | first2 = G. | author2-link = George Szekeres
 | journal = Compositio Math
 | 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}}.
*{{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Szekeres | first2 = G. | author2-link = George Szekeres
 | 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: {{citation
 | last = Erdős | first = P. | author-link = Paul Erdős
 | editor-last = Spencer | editor-first = J.
 | location = Cambridge, MA
 | pages = 680–689
 | publisher = MIT Press
 | title = The Art of Counting: Selected Writings
 | year = 1973}}.
*{{citation
 | 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}}.
*{{citation
 | last = Grünbaum | first = Branko | authorlink = Branko Grünbaum
 | edition = 2nd
 | editor1-last = Kaibel | editor1-first = Volker
 | editor2-last = Klee | editor2-first = Victor | editor2-link = Victor Klee
 | editor3-last = Ziegler | editor3-first = Günter M. | editor3-link = Günter M. Ziegler
 | isbn = 0-387-00424-6
 | publisher = [[Springer-Verlag]]
 | series = Graduate Texts in Mathematics
 | title = Convex Polytopes
 | volume = 221
 | year = 2003}}.
*{{citation
 | last = Harborth | first = Heiko
 | issue = 5
 | journal = Elem. Math.
 | pages = 116–118
 | title = Konvexe Fünfecke in ebenen Punktmengen
 | volume = 33
 | year = 1978}}.
*{{citation
 | 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}}.
*{{citation
 | last1 = Kalbfleisch | first1 = J.D.
 | last2 = Kalbfleisch | first2 = J.G.
 | 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}}.
*{{citation
 | last1 = Kleitman | first1 = D.J. | author1-link = Daniel Kleitman
 | last2 = Pachter | first2 = L.
 | 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}}.
*{{citation
 | 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 = 04
 | url = http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html
 | volume = 37
 | year = 2000}}.
*{{citation
 | 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}}.
*{{citation
 | 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}}.
*{{citation
 | last = Peterson | first = Ivars
 | journal = MAA Online
 | title = Planes of Budapest
 | url = http://www.maa.org/mathland/mathtrek_10_3_00.html
 | year = 2000}}.
*{{citation
 | last1 = Scheinerman | first1 = Edward R.
 | last2 = Wilf | first2 = Herbert S.
 | 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}}.
*{{citation
 | last1 = Szekeres
 | first1 = G.
 | author1-link = George Szekeres
 | 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 = 02
 | url = http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html
 | volume = 48
 | year = 2006
 | access-date = 2012-12-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 = dead
 }}.
*{{citation
 | 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}}.
*{{citation
 | last1 = Tóth | first1 = G.
 | last2 = Valtr | first2 = P.
 | contribution = The Erdős-Szekeres theorem: upper bounds and related results
 | pages = 557–568
 | publisher = Mathematical Sciences Research Institute Publications, no. 52
 | title = Combinatorial and computational geometry
 | year = 2005}}.
*{{citation
 | last = Valtr | first = P.
 | title = On the empty hexagons
 | url = http://kam.mff.cuni.cz/~valtr/h.ps
 | year = 2006}}.
{{จบอ้างอิง}}

== แหล่งข้อมูลอื่น ==
* [http://planetmath.org/encyclopedia/HappyEndingProblem.html ปัญหาแฮปปี้เอ็นดิ้ง] {{Webarchive|url=https://web.archive.org/web/20060925032614/http://planetmath.org/encyclopedia/HappyEndingProblem.html |date=2006-09-25 }} จาก PlanetMath
* Eric W. Weisstein, ''Happy End Problem'' จาก MathWorld.


[[หมวดหมู่:เรขาคณิตไม่ต่อเนื่อง]]
[[หมวดหมู่:ปัญหาทางคณิตศาสตร์]]
[[หมวดหมู่:เรขาคณิต]]
[[หมวดหมู่:เรขาคณิตบนระนาบยุคลิด]]
[[หมวดหมู่:ทฤษฎีแรมซีย์]]
{{โครงคณิตศาสตร์}}