Dnes sa u mňa stavil Braňo Novotný (doktorand na MÚ SAV) a z voľnej debaty vyplynul nasledovný rekreačný matematický problém. Poznámka: rekreačný sa vo všeobecnosti nerovná jednoduchý.Pre 2n bodov v rovine nazveme disjunktným párovaním také rozdelenie týchto bodov do n dvojíc, že úsečky spájajúce jednotlivé páry sa nepretínajú (krajné body považujeme za súčasť úsečky). Z ilustračného obrázku vľavo hore vidíme, že vieme nájsť konfigurácie štyroch bodov v rovine, pre ktoré existuje práve jedno, práve dve a aj práve tri disjunktné párovania. Viac disjunktných párovaní štvorice bodov očividne nemôže existovať. Pre šesť bodov je však situácia komplikovanejšia:
Koľko disjunktných párovaní môže mať šestica bodov v rovine? Formálnejšie: Nájdite množinu M tých čísel m, že existuje šestica bodov v rovine, ktoré je možné disjunktne popárovať práve m spôsobmi.
Keď usporiadame 6 bodov tak, aby ležali na spoločnej priamke, existuje len jedno párovanie, t.j. množina M obsahuje číslo 1. Ak usporiadame 6 bodov do vrcholov pravidelného šesťuholníka, nájdeme 5 rôznych popárovaní, čiže aj číslo 5 patrí do množiny M. (Pozri obrázok vpravo; každá z piatich farieb určuje iné disjunktné párovanie.)Ktoré ďalšie čísla patria do tejto množiny? (Väčšinu z nich nájdete jednoduchým experimentovaním s obrázkmi.) Viete nájsť horné ohraničenie množiny M, t.j. také číslo, že žiadne m z M nemôže byť väčšie?
27.10.: Nasledujúce obrázky ukazujú, že do množiny M patria čísla 3,4,5,6,7,10.
10.11.: Ako upozornil Braňo v komentároch, existujú aj konfigurácie (zobrazené nižšie) vedúce na 11 a 12 disjunktných párovaní.
Zostáva nám teda ešte nasledovná úloha: Patria do množiny M niektoré z čísiel 2,8,9,13,14,15?
6 komentárov:
no, povedala by som, ze do M patria este cisla 3, 4 a nepatri tam 2 (aj ked poriadny dokaz na to nemam :-)). najvacsi pocet disjunktnych parovani, co sa mi podaril najst, je 10... zaoberal sa touto ulohou este niekto? :-)
Ahoj. Som rád, že aspoň niekoho táto úloha zaujala. Počty párovaní, ktoré som našiel ja sám, som ilustroval na obrázkoch, ktoré som pridal k hlavnému textu príspevku. Ale na rozdiel od Teba som nenašiel takú konfiguráciu, v ktorej existujú práve 3 párovania. Vedela by si ju nejako popísať?
Rado, ak sa nemýlim, tak tá tvoja konfigurácia, o ktorej tvrdíš, že má 2 párovania, tak má v skutočnosti 3 -- ešte môžeme spojiť spodný so stredným z horných piatich.
misof: Ooops. Tam som sa pomýlil; ďakujem za upozornenie. Hneď to opravím. Druhá časť môjho prvého komentára k tomuto príspevku je teda už irelevantná.
myslim, ze sa mi podarilo najst konfiguracie pre 11, 12
trojuholnicek vnutri trojuholnicka, od vzajomneho pootocenia zavisi, ci 11 alebo 12
Braňo: nakreslil som si to a zdá sa, že máš pravdu; aj 11 aj 12 sa dá dosiahnuť. Fajn! Keď budem mať čas, tak dám obrázky do hlavného textu článku.
Zverejnenie komentára