ปัญหาแฮปปี้เอ็นดิ้ง

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
ปัญหาแฮปปี้เอ็นดิ้ง: สำหรับจุดห้าจุดใดๆในระนาบ จะต้องมีจุดสี่จุดซึ่งทำให้เกิดสี่เหลี่ยมนูน
เซตของจุดแปดจุดที่ไม่มีจุดห้าจุดใดๆที่ทำให้เกิดห้าเหลี่ยมนูน

ปัญหาแฮปปี้เอ็นดิ้ง เป็นปัญหาทางคณิตศาสตร์ ตั้งชื่อโดยพอล แอร์ดิช หลังจากปัญหานี้ทำให้เกิดการแต่งงานของ 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 ตั้งข้อคาดเดาไว้ว่า

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

ขอบเขตบนของ f(N) เมื่อ ที่ดีที่สุดเท่าที่ทราบในปัจจุบันคือ

อ้างอิง[แก้]

  • Chung, F.R.K.; Graham, R.L. (1998), "Forced convex n-gons in the plane", Discrete and Computational Geometry, 19 (3): 367–371, doi:10.1007/PL00009353.
  • Erdős, P.; Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Math, 2: 463–470.
  • Erdős, P.; Szekeres, G. (1961), "On some extremum problems in elementary geometry", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3–4: 53–62. Reprinted in: Erdős, P. (1973), Spencer, J., ed., The Art of Counting: Selected Writings, Cambridge, MA: MIT Press, pp. 680–689.
  • Gerken, Tobias (2008), "Empty convex hexagons in planar point sets", Discrete and Computational Geometry, 39 (1–3): 239–272, doi:10.1007/s00454-007-9018-x.
  • Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M., eds., Convex Polytopes, Graduate Texts in Mathematics, 221 (2nd ed.), Springer-Verlag, ISBN 0-387-00424-6.
  • Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elem. Math., 33 (5): 116–118.
  • Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26 (4): 482–484, doi:10.4153/CMB-1983-077-8.
  • Kalbfleisch, J.D.; Kalbfleisch, J.G.; Stanton, R.G. (1970), "A combinatorial problem on convex regions", Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Congressus Numerantium, 1, Baton Rouge, La.: Louisiana State Univ., pp. 180–188.
  • Kleitman, D.J.; Pachter, L. (1998), "Finding convex sets among points in the plane", Discrete and Computational Geometry, 19 (3): 405–410, doi:10.1007/PL00009358.
  • Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", Bulletin of the American Mathematical Society, 37 (04): 437–458, doi:10.1090/S0273-0979-00-00877-6.
  • Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete and Computational Geometry, 38 (2): 389–397, doi:10.1007/s00454-007-1343-6.
  • Overmars, M. (2003), "Finding sets of points without empty convex 6-gons", Discrete and Computational Geometry, 29 (1): 153–158, doi:10.1007/s00454-002-2829-x.
  • Peterson, Ivars (2000), "Planes of Budapest", MAA Online.
  • Scheinerman, Edward R.; Wilf, Herbert S. (1994), "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability", American Mathematical Monthly, Mathematical Association of America, 101 (10): 939–943, doi:10.2307/2975158, JSTOR 2975158.
  • Szekeres, G.; Peters, L. (2006), "Computer solution to the 17-point Erdős-Szekeres problem", ANZIAM Journal, 48 (02): 151–164, doi:10.1017/S144618110000300X.
  • Tóth, G.; Valtr, P. (1998), "Note on the Erdős-Szekeres theorem", Discrete and Computational Geometry, 19 (3): 457–459, doi:10.1007/PL00009363.
  • Tóth, G.; Valtr, P. (2005), "The Erdős-Szekeres theorem: upper bounds and related results", Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications, no. 52, pp. 557–568.
  • Valtr, P. (2006), On the empty hexagons.

แหล่งข้อมูลอื่น[แก้]