24 októbra 2008

Braňov problém

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:

Anonymný povedal(a)...

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? :-)

Radoslav Harman povedal(a)...

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ť?

misof povedal(a)...

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.

Radoslav Harman povedal(a)...

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

Brano povedal(a)...

myslim, ze sa mi podarilo najst konfiguracie pre 11, 12

trojuholnicek vnutri trojuholnicka, od vzajomneho pootocenia zavisi, ci 11 alebo 12

Radoslav Harman povedal(a)...

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.