幸福結局問題

幸福结局问题：任何五个点中一定存在四个点组成凸四边形。

幸福結局問題（由保羅·艾狄胥命名，因為這個問題令喬治·塞凱賴什和愛絲特·克萊共諧連理）是問，在平面上，給定一般位置（即平面上任意三點不共線）上的多少點，才令其中必可以找到${\displaystyle n}$點能組成凸${\displaystyle n}$邊形？

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

將${\displaystyle f(N)}$表示為${\displaystyle M}$的最小可能值，已知

• ${\displaystyle f(3)=3}$：顯然易見
• ${\displaystyle f(4)=5}$ ：愛絲特·克萊證明；這就是最初的問題[1]
• ${\displaystyle f(5)=9}$ ：艾狄胥和塞凱賴什表示E. Makai證明了這點，但首個印刷出來的證明則在1970年出現在Kalbfleisch et al
• ${\displaystyle f(6)=17}$：由塞凱賴什和Lindsay Peters以機器證明所有可能性。

1961年，艾狄胥和塞凱賴什證明 ${\displaystyle f(N)\geq 1+2^{N-2}}$[2]。

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

${\displaystyle f(N)\leq {2n-5 \choose n-3}+2}$

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

${\displaystyle f(N)\leq {2n-5 \choose n-3}+1}$

2016年，Andrew Suk證明了：

${\displaystyle f(N)\leq 2^{N+o(N)}}$[3]

參考

• 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.

註解

1. 證明：若這五點的凸包是四邊形或五邊形，則結果易見。若否，則凸包是三角形，其中兩點在三角形內。連接這兩點的直線，與三角形其中兩邊相交，則這兩點與三角形第三邊的兩點組成凸四邊形。
2. Erdős & Szekeres (1961) harvtxt模板錯誤: 無指向目標: CITEREFErdősSzekeres1961 (幫助)
3. Suk, Andrew, On the Erdős–Szekeres convex polygon problem, 2016, arXiv:1604.08657  

外部連結

• 從鴿籠原理到幸福結局問題，台灣大學數學系 張鎮華^[永久失效連結] （繁體中文）