Tento príklad by mal ukázať, že aj prízemná matematika môže byť pekná. Konkrétne matematika na topánkach. Matematickú topánku si zadefinujme ako graf, ktorý obsahuje dva rovnobežné a rovnako početné rady vrcholov (dierky) a cesty medzi nimi (šnúrky) -pozrite si ilustračné obrázky:
Pritom cesty musia spĺňať dve podmienky:
1. Z každého vrchola idú práve dve cesty (pozrite si topánku)
2. Z každého vrchola ide aspoň jedna cesta do druhej skupiny vrcholov (na druhú stranu). Je to preto, aby sa topánka dala aj používať a držala na nohe.
Úloha pozostáva z dvoch častí, ktoré je možné riešiť navzájom nezávisle:
A) Máme topánku s 12 dierkami, teda dva rady po 6 dierok. Vzdialenosť medzi radmi je 1 a vzdialenosť medzi dvomi susednými dierkami v jednom rade je tiež 1. Nájdite čo najkratšie šnurovanie na takejto topánke. Predpokladáme, že dĺžka šnúrky medzi dvomi dierkami je rovná vzdialenosti týchto dvoch dierok; t.j. šnúrky nie sú uvoľnené. (Ľavá šnúrka na obrázku je "zakrivená" len kvôli prehľadnosti; pri zaviazaní, aké uvažujeme my, by bola rovná.)
B) Zoberme si binomickú topánku, t.j. obe šnúrky z vrcholu idú do druhej skupiny vrcholov (na druhú stranu; napríklad ako viazanie v pravej časti ilustračného obrázku). Nech má 2n vrcholov, teda n v každom rade. Koľko je možných spôsobov ako zašnurovať takúto topánku?
Táto úloha pochádza z knihy od Burkarda Polstera s názvom "The shoelace book: A mathematical guide to the best (and worst) ways to lace your shoes". Vzorové riešenie nemáme a sme zvedaví, kto túto úlohu správne vyrieši ako prvý.
Hmm, otázka, napríklad v tej podúlohe A tá topánka vyzerá tak ako na obrázku? Teda okrem 12 dierok je ešte úplne hore pevne daný začiatok a koniec? Teda ako graf to má 14 vrcholov a začínať sa musí vľavo hore a končiť vpravo hore?
OdpovedaťOdstrániťNo tak B by malo byť ľahké: Nech mám N dierok vľavo a N vpravo, pričom začínať musím v hornej ľavej a končiť v hornej pravej. Keď teraz začnem šnúrku postupne navliekať, určite pôjde striedavo cez dieru vľavo a vpravo. Môžem si nezávisle na sebe určiť poradie v akom chcem ísť cez ľavé diery okrem hornej a v akom chcem ísť cez pravé diery okrem hornej, takže by to malo byť ((N-1)!)^2.
OdpovedaťOdstrániťInak, tento model ešte neuvažuje, že šnúrka sa dá cez dierku pchať zhora dole aj zdola hore, na reálnych topánkach je v tom rozdiel -- a teda je možných šnurovaní výrazne viac :)
Viem už asi dokázať aj optimálne riešenie Ačko, ale chce to obrázok a na ten to chce čas. (A nezmestí sa mi na okraj tejto strany :D )
Ahoj Misof,
OdpovedaťOdstrániťobrazok sa zmeni na lepsi. Topanka vyzera tak, ze aj vrchne dve dierky su spojene snurkou, rovnako ako spodne dve dierky (a moze sa stat, ze budu vrchne dve spojene len z nizsimi dierkami a nie medzi sebou).
S dovysvetlenim ako to je s topankou sa trosicku meni aj tvoje spravne riesenie casti B, ale len minimalne.
Ak sa ti to zapacilo a nemas co popri haluzi, tak skus cast po B na takychto topankach: Obsahuju vsetky horizontalne spojenia dierok a okrem nich uz len vertikalne spojenia dierok (teda ziadna snurka nemoze ist "sikmo"). A kedze noc bude dlha mozes to skusit aj pre povodnu topank zadefinovanu na zaciatku (je to tazsie).
konecne prakticka aplikacia zakladneho vyskumu! :)
OdpovedaťOdstrániťmisof: Uploadol som nový Ajkin obrázok. Ja úlohu chápem tak, že horné dierky nie sú ničím odlišné od iných dierok, t.j. akákoľvek permutácia vrcholov v ľavej skupine alebo aj akákoľvek permutácia vrcholov v pravej skupine nám opäť dá prípustné viazanie (či už to všeobecné, alebo binomické; permutáciou vrocholov niektorej zo skupín sa samozrejme zmení dĺžka šnúrky, ale nie prípustnosť daného viazania).
OdpovedaťOdstrániťInými slovami: Prípustným viazaním na dvoch skupinách po n vrcholov je akýkoľvek cyklus dĺžky 2n taký, že každý vrchol je incidentný s aspoň jedným vrcholom z opačnej skupiny ako je tá, do ktorej patrí on sám. Pre binomické viazanie je každý vrchol incidentý s dvomi vrcholmi, ktoré sú obidva z opačnej skupiny ako je on sám.
OdpovedaťOdstrániťVyplyva formalne zo zadania to, ze by to cele mal byt prave jeden cyklus? Mne sa mari ze zadaniu vyhovuju aj tri cykly, kazdy s dlzkou 4.
OdpovedaťOdstrániťcharon: Hm. To by boli tri šnúrky a nie jedna (a podstatne by to menilo riešenie). Ale máš pravdu, že nie je stoporcentne jasné, že to zadanie vylučuje. Opýtame sa Ajky.
OdpovedaťOdstrániťPrepacte, ze to nebolo jasne uz od zaciatku. Na zasnurovanie celej topanky pouzivame len jednu snurku, teda robime len jeden cyklus. V podstate vo vsetkych nejasnostniach sa co najviac snazime napodobnit skutocnost.
OdpovedaťOdstrániťno ja si myslim, ze odpoved na B) je N!(N-1)!/2
OdpovedaťOdstrániťmame cyklus s fix. polohou LH dierky to je (N-1)! za L dierky a N! za P dierky (to misof: asi netreba kocit v PH) a /2 za symetriu v smere snurovania
Uloha A: moj nazor je odmocnina z 200 a k tomu +2 na dokoncenie hore aj dole.
OdpovedaťOdstrániťVizeralo by to tak ze z kazdej strany sa ide sikmo hore o jednu dierku. Nie som si isty ci to dokazujem spravne ale v dokaze ide o to ze ked je horizontalne viazanie tak sa to predlzi ...
Tuším máme uhorkovú sezónu... tak je čas pouzatvárať nejaké tie nevyriešené úlohy :-)
OdpovedaťOdstrániťMoje riešenie A-čka je také, že hornú a dolnú dvojicu dierok spojíme horizontálne, inak striedame "dole" a "dole-na-opačnú-stranu" (pričom začíname s "dole"). Celková dĺžka potom bude 8 + 4 * sqrt(2) = zhruba 13,66.
Otočené o 90 stupňov by to vyzeralo takto: [=x=x=] :-)