幸福結局問題

维基百科,自由的百科全书
跳转至: 导航搜索
幸福结局问题:任何五个点中一定存在四个点组成凸四边形。

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

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

將f(N)表示為M的最小可能值,已知

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

1961年,艾狄胥和塞凱賴什證明 f(N) \geq 1 + 2^{N-2}

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

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

2005年,他们进一步将此上界降低了1:

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

(參見二項式係數)。

參考[编辑]

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

外部連結[编辑]

  • ^ 證明:若這五點的凸包是四邊形或五邊形,則結果易見。若否,則凸包是三角形,其中兩點在三角形內。連接這兩點的直線,與三角形其中兩邊相交,則這兩點與三角形第三邊的兩點組成凸四邊形。