查看“︁幸福結局問題”︁的源代码

{{Expand|time=2013-02-14T04:59:29+00:00 }}{{noteTA
|1=zh-hans:埃尔德什; zh-hant:艾狄胥;
}}
[[Image:Happy-End-problem.svg|thumb|300px|幸福结局问题：任何五个点中一定存在四个点组成凸四边形。]]
'''幸福結局問題'''（由[[保羅·艾狄胥]]命名，因為這個問題令[[喬治·塞凱賴什]]和[[愛絲特·克萊]]共諧連理）是問，在[[平面 (数学)|平面]]上，給定[[一般位置]]（即平面上任意三點不共線）上的多少[[點]]，才令其中必可以找到<math>n</math>點能組成凸<math>n</math>邊形？

1935年，艾狄胥和塞凱賴什證明：給定任意正整數<math>N</math>，存在正整數<math>M</math>使得給定在平面上一般位置上的<math>M</math>點，其中必可以找到<math>N</math>點能組成凸<math>N</math>邊形。

將<math>f(N)</math>表示為<math>M</math>的最小可能值，已知

* <math>f(3)=3</math>：顯然易見
* <math>f(4)=5</math> ：愛絲特·克萊證明；這就是最初的問題<ref>證明：若這五點的[[凸包]]是四邊形或五邊形，則結果易見。若否，則凸包是三角形，其中兩點在三角形內。連接這兩點的直線，與三角形其中兩邊相交，則這兩點與三角形第三邊的兩點組成凸四邊形。</ref>
* <math>f(5)=9</math> ：艾狄胥和塞凱賴什表示E. Makai證明了這點，但首個印刷出來的證明則在1970年出現在''Kalbfleisch et al'' 
* <math>f(6)=17</math>：由塞凱賴什和Lindsay Peters以[[電腦協助證明|機器證明]]所有可能性。

1961年，艾狄胥和塞凱賴什證明 <math>f(N) \geq 1 + 2^{N-2}</math><ref>{{harvtxt|Erdős|Szekeres|1961}}</ref>。

1998年，一连三篇关于对<math>f(N)</math>的上界的文章被发表，其中最好的结果是由Tóth和Valtr找到的：

:<math>f(N) \leq {2n-5 \choose n-3} + 2</math>

2005年，他们进一步将此上界降低了1：

:<math>f(N) \leq {2n-5 \choose n-3} + 1</math>

2016年，Andrew Suk證明了：
:<math>f(N)\leq 2^{N + o(N)}</math><ref>{{citation|title=On the Erdős–Szekeres convex polygon problem|first=Andrew|last=Suk|year=2016|arxiv=1604.08657}}</ref>

== 參考 ==
* Erdős, P., Szekeres, G., A combinatorial problem in geometry, ''Compositio Math.'' 2 (1935), 463--470.
* Erdős P., Szekeres G., On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3-4 (1961), 53–62. Reprinted in: Paul Erdős: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 680–689, MIT Press, Cambridge, MA, 1973.
* Kalbfleisch J.D., Kalbfleisch J.G., Stanton R.G., A combinatorial problem on convex regions, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La, 1970. Congr. Numer. 1 (1970), 180-188.
* Morris, W., and V. Soltan. 2000. The Erdös-Szekeres problem on points in convex position--A survey. Bulletin of the American Mathematical Society 37(October): 437.
*Tóth G., Valtr P., Note on the Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457–459.

== 註解 ==
{{Reflist|2}}

==外部連結==
* [http://www.math.ntu.edu.tw/~gjchang/courses/2004-02-high-school-stud/happy-ending-problem.doc 從鴿籠原理到幸福結局問題，台灣大學數學系  張鎮華]{{Dead link|date=2018年6月 |bot=InternetArchiveBot |fix-attempted=no }} {{Zh-tw}}

[[Category:離散幾何]]
[[Category:数学问题]]
[[Category:拉姆齊理論]]