fbpx
วิกิพีเดีย

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

ปัญหาแฮปปี้เอ็นดิ้ง เป็นปัญหาทางคณิตศาสตร์ ตั้งชื่อโดยพอล แอร์ดิช หลังจากปัญหานี้ทำให้เกิดการแต่งงานของ 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. (บ.ก.), 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. (บ.ก.), 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), , ANZIAM Journal, 48 (02): 151–164, doi:10.1017/S144618110000300X, คลังข้อมูลเก่า เก็บจาก แหล่งเดิม เมื่อ 2019-12-13, สืบค้นเมื่อ 2012-12-03.
  • 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.

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

ญหาแฮปป, เอ, นด, เป, นป, ญหาทางคณ, ตศาสตร, งช, อโดยพอล, แอร, หล, งจากป, ญหาน, ทำให, เก, ดการแต, งงานของ, george, szekeres, และ, esther, klein, งน, สำหร, บจ, ดห, าจ, ดใดๆในระนาบ, จะต, องม, ดส, ดซ, งทำให, เก, ดส, เหล, ยมน, เซตของจ, ดแปดจ, ดท, ไม, ดห, าจ, ดใดๆท, . pyhaaehppiexnding epnpyhathangkhnitsastr tngchuxodyphxl aexrdich hlngcakpyhanithaihekidkaraetngngankhxng George Szekeres aela Esther Klein midngnipyhaaehppiexnding sahrbcudhacudidinranab catxngmicudsicudsungthaihekidsiehliymnun estkhxngcudaepdcudthiimmicudhacudidthithaihekidhaehliymnun sahrbcudhacudid inranab catxngmicudsicudsungthaihekidsiehliymnunpyhathiihykhun aekikhaexrdich aela Szekeres idphisucnthvsdibthdngnisahrbcanwnetmbwk N id miestcakdkhxngcudbnranabthimicud N cudphayinestnn sungthaihekidrup N ehliymnunih f N aethnkha M thinxythisudthithaihestkhxngcud M cudid catxngmicud N cudphayinestnn sungthaihekidrup N ehliymnun f 3 3 f 4 5 phisucnody Esther Klein f 5 9 phisucnody E Makai tiphimphkhrngaerkin ph s 2513 f 6 17 phisucnody Szekeres and Lindsay Peters odyichkhxmphiwetxr sahrb F N emux N epncanwnetmbwkid yngimmisutrthiichha aexrdichaela Szekeres tngkhxkhadedaiwwa f N 1 2 N 2 for all N 3 displaystyle f N 1 2 N 2 quad mbox for all N geq 3 inpi ph s 2504 aexrdichaela Szekeres phisucnidwa f N 1 2 N 2 displaystyle f N geq 1 2 N 2 khxbekhtbnkhxng f N emux N 5 displaystyle N geq 5 thidithisudethathithrabinpccubnkhux f N 2 N 5 N 3 1 8 4 N N displaystyle f N leq 2N 5 choose N 3 1 Theta left frac 4 N sqrt N right xangxing aekikhChung 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 Erdos P Szekeres G 1935 A combinatorial problem in geometry Compositio Math 2 463 470 Erdos P Szekeres G 1961 On some extremum problems in elementary geometry Ann Univ Sci Budapest Eotvos Sect Math 3 4 53 62 Reprinted in Erdos P 1973 Spencer J b k 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 Grunbaum Branko 2003 Kaibel Volker Klee Victor Ziegler Gunter M b k Convex Polytopes Graduate Texts in Mathematics 221 2nd ed Springer Verlag ISBN 0 387 00424 6 Harborth Heiko 1978 Konvexe Funfecke 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 Erdos 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 Nicolas 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 Erdos Szekeres problem ANZIAM Journal 48 02 151 164 doi 10 1017 S144618110000300X khlngkhxmuleka ekbcak aehlngedim emux 2019 12 13 subkhnemux 2012 12 03 Toth G Valtr P 1998 Note on the Erdos Szekeres theorem Discrete and Computational Geometry 19 3 457 459 doi 10 1007 PL00009363 Toth G Valtr P 2005 The Erdos 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 aehlngkhxmulxun aekikhpyhaaehppiexnding Archived 2006 09 25 thi ewyaebkaemchchin cak PlanetMath Eric W Weisstein Happy End Problem cak MathWorld bthkhwamekiywkbkhnitsastrniyngepnokhrng khunsamarthchwywikiphiediyidodyephimkhxmul duephimthi sthaniyxy khnitsastr ekhathungcak https th wikipedia org w index php title pyhaaehppiexnding amp oldid 9651071, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม