Úkol se šťastným koncem

Problém se šťastným koncem je tvrzení, že jakákoliv sada pěti bodů na rovině v obecné poloze [1] má podmnožinu čtyř bodů, které jsou vrcholy konvexního čtyřúhelníku .

Historie

Tento výsledek kombinatorické geometrie nazývá Pal Erdős „problémem se šťastným koncem“, neboť řešení problému skončilo svatbou Györgyho Sekerese a Esther Kleinové ( maď . Eszter Klein ). Také známý jako Erdős-Szekeresův teorém konvexního mnohoúhelníku .

Zobecnění výsledku na libovolný počet bodů zajímá matematiky 20. a 21. století.

Důkaz

Pokud alespoň čtyři body tvoří konvexní trup , pak lze jako konvexní čtyřúhelník vybrat jakoukoli sadu čtyř bodů trupu. Jinak je v něm trojúhelník a dva body. Přímka procházející dvěma vnitřními body neprotíná jednu ze stran trojúhelníku kvůli obecné poloze bodů. Vrcholy této strany a dva vnitřní body tvoří konvexní čtyřúhelník.

Polygony s libovolným počtem vrcholů

Erdős a Szekeres zobecnili tento výsledek na libovolný počet bodů, což je původní vývoj Ramseyovy teorie . Také předložili „Erdős-Szekeresův odhad“ – přesný vzorec pro maximální počet vrcholů konvexního mnohoúhelníku, který musí existovat v množině daného počtu bodů v obecné poloze.

V ( Erdős & Szekeres 1935 ) bylo dokázáno následující zobecnění: pro jakýkoli přirozený , jakákoli dostatečně velká množina bodů v obecné poloze na rovině má podmnožinu bodů, které jsou vrcholy konvexního mnohoúhelníku. Tento důkaz se objevil ve stejném článku, kde je prokázána Erdős-Szekeresova věta o monotónních podposloupnostech v číselných posloupnostech. $N$ $N$

Nastavit velikost jako funkci počtu vrcholů polygonu

Označme minimum , pro které jakákoliv sada bodů v obecné poloze obsahuje konvexní -gon. Je známo že: $f(N)$ $M$ $M$ $N$

$f(3)=3$ , očividně.
$f(4)=5$ , dokázala Esther Sekeresová.
$f(5)=9$ , podle ( Erdős & Szekeres 1935 ) to jako první dokázal E. Makai; první publikovaný důkaz se objevil v ( Kalbfleisch, Kalbfleisch & Stanton 1970 ). Sada osmi bodů, která na obrázku neobsahuje konvexní pětiúhelník, ukazuje, že ; je obtížnější dokázat, že jakákoliv sada devíti bodů v obecné poloze obsahuje konvexní pětiúhelník. $f(5)>8$
$f(6)=17$ , to bylo prokázáno v ( Szekeres & Peters 2006 ). Příspěvek implementuje zkrácený počítačový výčet možných konfigurací ze 17 bodů.
Hodnoty pro . $f(N)$ $N>6$

Erdős-Szekeresova domněnka o minimálním počtu bodů

Na základě známých hodnot pro , Erdős a Székeres navrhli, že: $f(N)$ $N=3,4,5$

f(N)=1+2^{{N-2}}

pro všechny .

N

Tato domněnka nebyla prokázána, ale horní a dolní hranice jsou známé.

Odhady rychlosti růstu f(N)

Konstruktivní konstrukcí mohli autoři domněnky později prokázat spodní odhad, který se shoduje s hypotetickou rovností:

f(N)\geq 1+2^{{N-2}}

, ( Erdős & Szekeres 1961 )

Nejznámější horní hranice však není blízko: $N\geq 7$

f(N)\leq {2N-5 \vyberte N-2}+1=O\left({\frac {4^{N}}{{\sqrt N}}}\vpravo)

, ( Toth & Valtr 2005 )

(použité binomické koeficienty ).

Prázdné polygony

Zajímavá je také otázka, zda dostatečně velká množina bodů v obecné poloze obsahuje prázdný konvexní čtyřúhelník, pětiúhelník a tak dále. To znamená, že mnohoúhelník neobsahuje žádné vnitřní body.

Pokud je uvnitř čtyřúhelníku bod, který existuje podle věty o šťastném konci, pak spojením tohoto bodu se dvěma vrcholy úhlopříčky dostaneme dva čtyřúhelníky, z nichž jeden je konvexní a prázdný. Pět bodů v obecné poloze tedy obsahuje prázdný konvexní čtyřúhelník, jak je vidět na obrázku. Libovolných deset bodů v obecné poloze obsahuje prázdný konvexní pětiúhelník ( Harborth 1978 ). Existují však libovolně velké sady bodů v obecné poloze, které neobsahují prázdný konvexní sedmiúhelník ( Horton 1983 )

Problém prázdných polygonů tedy není problémem Ramseyho teorie a byl v zásadě vyřešen.

Otázka existence prázdného šestiúhelníku zůstávala dlouho otevřená. Ale v ( Nicolás 2007 ) a ( Gerken 2008 ) bylo prokázáno, že každá dostatečně velká množina bodů v obecné poloze obsahuje prázdný šestiúhelník. Dnes je známo, že tato množina by měla obsahovat nejvýše f (9) (pravděpodobně 129) a nejméně 30 bodů ( Overmars 2003 ).

Poznámky

↑ Obecná poloha v tomto kontextu znamená, že žádné tři body neleží na stejné přímce.

Literatura

Chung, FRK & Graham, R. L. (1998), Vynucené konvexní n-úhelníky v rovině , Discrete and Computational Geometry , svazek 19 (3): 367–371 , DOI 10.1007/PL00009353 .
Erdős, P. & Szekeres, G. (1935), Kombinatorický problém v geometrii , Compositio Math sv. 2: 463–470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > .
Erdős, P. & Szekeres, G. (1961), O některých extrémních problémech v elementární geometrii, Ann. Univ. sci. Budapešť. Sekta Eötvös. Matematika. T. 3–4: 53–62 . Přetištěno v: Erdős, P. (1973), Spencer, J., ed., The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, s. 680–689 .
Gerken, Tobias (2008), Prázdné konvexní šestiúhelníky v planárních bodových sadách , Diskrétní a výpočetní geometrie vol. 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 , sv. 221 (2. vyd.), Postgraduální texty z matematiky, Springer-Verlag , ISBN 0-387-00424-6 .
Harborth, Heiko (1978), Konvexe Fünfecke v ebenen Punktmengen, Elem. Matematika. T. 33(5): 116–118 .
Horton, JD (1983), Sady bez prázdných konvexních 7-úhelníků , Canadian Mathematical Bulletin T. 26 (4): 482–484 , DOI 10.4153/CMB-1983-077-8 .
Kalbfleisch, JD; Kalbfleisch, JG & Stanton, RG (1970), Kombinatorický problém na konvexních oblastech, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing , sv. 1, Congressus Numerantium, Baton Rouge, La.: Louisiana State Univ., str. 180–188 .
Kleitman, DJ & Pachter, L. (1998), Hledání konvexních množin mezi body v rovině , Discrete and Computational Geometry, svazek 19 (3): 405–410 , DOI 10.1007/PL00009358 .
Morris, W. & Soltan, V. (2000), Erdős-Szekeresův problém o bodech v konvexní poloze – průzkum , Bulletin of the American Mathematical Society , svazek 37 (04): 437–458, doi : 10.1090/S0273- 0979-00-00877-6 , < http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html > .
Nicolás, Carlos M. (2007), The empty hexagon theorem , Discrete and Computational Geometry vol. 38 (2): 389–397 , DOI 10.1007/s00454-007-1343-6 .
Overmars, M. (2003), Hledání množin bodů bez prázdných konvexních 6-úhelníků , Discrete and Computational Geometry , svazek 29 (1): 153–158 , DOI 10.1007/s00454-002-2829-x .
Peterson, Ivars (2000), Planes of Budapest , MAA Online , < http://www.maa.org/mathland/mathtrek_10_3_00.html > .
Scheinerman, Edward R. & Wilf, Herbert S. (1994), Přímé křížení čísla úplného grafu a Sylvesterův "čtyřbodový problém" geometrické pravděpodobnosti , American Mathematical Monthly (Mathematical Association of America). - T. 101 (10): 939–943 , DOI 10.2307/2975158 .
Szekeres, G. & Peters, L. (2006), Počítačové řešení 17bodového problému Erdős-Szekeres , ANZIAM Journal vol . 48 (02): 151–164, doi : 10.1017 / S144618110000300X .austms.org.au/Publ/ANZIAM/V48P2/2409.html > Archivováno 13. prosince 2019 na Wayback Machine .
Tóth, G. & Valtr, P. (1998), Poznámka k Erdős-Szekeresově větě , Discrete and Computational Geometry, svazek 19 (3): 457–459 , DOI 10.1007/PL00009363 .
Tóth, G. & Valtr, P. (2005), Erdős-Szekeresův teorém: horní odhady a související výsledky, Kombinatorická a výpočetní geometrie , Publikace Výzkumného ústavu matematických věd, no. 52, str. 557–568 .
Valtr, P. (2006), O prázdných šestiúhelnících , < http://kam.mff.cuni.cz/~valtr/h.ps > .

Odkazy

Problém se šťastným koncem Archivováno 25. září 2006 na Wayback Machine a Ramseyho teoretický důkaz Erdős-Szekeresovy věty na PlanetMath
Weisstein, Eric W. Happy End Problem (anglicky) na webu Wolfram MathWorld .