Úlohy pod stromček

Prajem Vám všetkým krásne sviatky! Aby ste vedeli, že na Vás myslím, tak som pre Vás ako darček pod vianočný stromček vymyslel tri matematické úlohy. Časti a) sú jednoduchšie a časti b) náročnejšie.

1. a) Koľko existuje rôznych ofarbení kocky dvomi farbami? Predpokladáme, že každá stena musí byt celá zafarbená jedinou farbou. Pochopiteľne, dve farbenia považujeme za identické, ak sa líšia len rotáciou kocky. b) Koľko existuje rôznych ofarbení kocky tromi farbami?

2. V súťaži o najkrajšiu matematickú úlohu je 12 úloh. Vzhľadom na to, že všetky sú rovnako pekné, každý hlasujúci sa rozhodne dať svoj hlas každej z týchto úloh s pravdepodobnosťou 1/12. Nájdite pravdepodobnosť, že niektoré dve úlohy dostanú rovnaký počet hlasov, ak je hlasujúcich a) 65; b) 650. Predpokladáme, že hlasujúci sa správajú navzájom nezávisle.

3. Máme štyri kladné čísla a,b,c,d, z ktorých najväčšie je menšie ako súčet zvyšných troch. a) Dokážte, že existuje štvoruholník so stranami dĺžok a,b,c,d, ktorého vrcholy ležia na spoločnej kružnici. b) Je možné takýto štvoruholník skonštruovať len pomocou ceruzky, pravítka a kružidla? (Predpokladáme, že na papieri už máme úsečky dĺžok a,b,c,d zakreslené.)

Pri riešení úloh 1b, prípadne 2b môžete použiť počítač. Priznám sa, že úlohu 3b som (v mojom limite 30 minút) nevyriešil, takže som zvedavý, ako úspešní budete Vy.

Ako si zašnurovať topánky s krátkymi šnúrkami (súťažná úloha č.6)

V poradí šiestu úlohu pre našu súťaž pripravila Ajka Bachratá, tretiačka na odbore matematika FMFI UK.

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

Prieskumná expedícia (súťažná úloha č.5)

Piatu súťažnú úlohu nám poslal Mišo 'mišof' Forišek, doktorand na FMFI UK.

Na štvorcovej mriežke žije národ panákov. Doteraz obývali polrovinu pod osou x. No teraz kráľ rozhodol, že vyšle zvedov, aby zistili, ako to vyzerá nad osou x.

Na začiatku expedície sa všetci zvedi rozostavia po kráľovstve, teda na navzájom rôzne políčka pod osou x. Následne začne expedícia. Počas expedície sa v každom kroku pohne práve jeden zved. Zvedi sa môžu pohybovať ako kamene v solitéri: Ak má zved v jednom zo 4 hlavných smerov pred sebou iného zveda a za ním voľné políčko, môže ho preskočiť. Preskočený zved už v expedícii nepokračuje.

Príklad povoleného ťahu.

Ľahko zistíme, že na to, aby sme dostali zveda do prvého riadku neznámeho územia, potrebujeme na začiatku zvedov aspoň dvoch, a na dosiahnutie druhého riadku treba zvedov aspoň štyroch:

Optimálne riešenia pre prvý a druhý riadok. V riešení vpravo si všimnite, že v okamihu, kedy najpravejší zved robí skok označený poradovým číslom 2, je už jeho cieľové políčko voľné.

Rozcvička číslo 1. Nájdite optimálne riešenie pre tretí riadok. Prezradíme, že stačí 8 zvedov. (Komu sa fakt nechce, tu nájde jedno možné riešenie. Ale odporúčame pohrať sa, nie je to ťažké.)

Po číslach 2, 4 a 8 je každému jasné, koľko zvedov treba na dosiahnutie štvrtého riadku, že? Až na to, že nemáte pravdu, lebo správny počet je 20.

Rozcvička číslo 2. Nájdite čo najlepšie riešenie pre štvrtý riadok a pochváľte sa v diskusii pod článkom.

No a už sme pri pointe: Použite svoju matematickú intuíciu a tipnite si, koľko najmenej zvedov treba na to, aby sa jeden z nich dostal až do piateho riadku neznámeho územia. A potom skúste nejaké, čo najlepšie riešenie zostrojiť.

Ak sa vzdáte a úlohu nevyriešite, tu je riešenie prezrádzajúce pointu.

(Zdroj: Berlekamp, E. R.; Conway, J. H; and Guy, R. K. "The Solitaire Army.")

Dve fľaše (súťažná úloha č.4)

Štvrtú úlohu do našej súťaže poslal Peter Richtárik, bývalý študent FMFI UK a autor nám dobre známeho blogu "predbarákom".

Máme k dispozícii dve identické fľaše, ktoré sa pri pustení z určitej (neznámej) výšky rozbijú. Fľaše môžeme skúšobne púšťať voľným pádom na zem z okien 100 poschodovej budovy. Ak sa fľaša rozbije, už je nepoužiteľná, ale ak sa nerozbije, ani trochu sa nepoškodí. Našim cieľom je zistiť číslo najvyššieho poschodia, z ktorého keď pustíme fľašu tohoto typu, tak sa ešte nerozbije. Koľko pokusných hodov na to určite stačí? Presnejšie povedané: Aký je minimálny počet hodov, pomocou ktorých vieme zaručene určiť číslo najvyššieho poschodia, z ktorého flaša nášho typu prežije pád?

Úlohu Peťovi zadal kolega z Ruska Anton Belyakov. Vzorové riešenie zatiaľ nemáme, takže sa teším na Vaše riešenia v komentároch.

Problém lámání stébla (súťažná úloha č.3)

Tretiu súťažnú úlohu nám poslal známy český autor šachových úloh Václav Kotěšovec.

Vezměme stéblo trávy a náhodně ho zlomíme A) ve dvou různých bodech, B) v jednom bodě a potom znovu v bodě napravo od prvního bodu. Jaká je pravděpodobnost v případech A a B, že z těchto 3 dílů je možné sestavit trojúhelník? Zobecněte úlohu pro n-úhelník a určete limitu této pravděpodobnosti pro n jde do nekonečna.

Z komentárov k zadaniu vyberám: "Zapojuji se do soutěže touto mojí vlastní úlohou, kterou jsem vymyslel při loňské dovolené. Úlohu jsem publikoval 9.8.2007 na moji stránce. Článek je k dispozici i v PDF formátu zde. V článku samozřejmě najdete i řešení."

Ja by som poznamenal, že časť a) je známa úloha, ktorá sa často rieši ako vzorový príklad na takzvanú geometrickú pravdepodobnosť. S úlohou z časti b) a zovšeobecnením na n-uholník som sa však dosiaľ nestretol.

Zapadajúce množiny (súťažná úloha č.2)

Druhý príspevok do súťaže o najkrajšiu úlohu poslal Ondrej Budáč, študent 3. ročníka FMFI UK, odbor matematika.

Majme množinu M, ktorá obsahuje podmnožiny prirodzených čísel. Pre každé dva prvky A, B množiny M platí, že A je podmožina B, alebo naopak B je podmožina A. (Formálne povedané, M je úplne usporiadaná vzhľadom na inklúziu.) Môže sa stať, že množina M bude nespočitateľná?

Úloha je prevzatá; riešenie nájdete tu (pdf).

Sto väzňov (súťažná úloha č.1)

Prvú úlohu do našej súťaže poslal Ondrej Budáč, študent 3. ročníka FMFI UK, odbor matematika.

V miestnosti je sto krabičiek uložených v jednom rade. V každej je meno jedného zo sto väzňov (žiadni dvaja sa nevolajú rovnako) a meno každého väzňa je práve v jednej krabičke. Každý väzeň je vpustený dnu a môže sa pozerať do krabičiek, otvoriť ich môže však najviac 50. Po jeho odchode musí miestnosť ostať presne v takom istom stave, ako keď do nej vošiel. Ak sa každému väzňovi podarí nájsť jeho meno, tak sú všetci voľní. Väzni sa môžu na začiatku poradiť, ale potom ich odvedú na samotky a do miestnosti vodia postupne. Ako sa majú dohodnúť, aby maximalizovali šancu na úspech?

Ondrejov komentár: "Ak by sa väzni správali náhodne a navzájom nezávisle, je zrejmé, že šanca na priepustku je polovica umocnená na 100. Dá sa však vymyslieť postup, pri ktorom dostanú väzni priepustku s cca 30% šancou. Riešenie tejto úlohy sa dá celkom ľahko pochopiť, je veľmi elegantné a nápadité. O to ťažšie je na to dôjsť sám. Ja som to nevydržal a po polhodine uvažovania som si pozrel vzorové riešenie. Ale aj dosť veľké hlavy (kamaráti Česi na súťaži v Bulharsku a mnohí ďalší) si nad tým lámali hlavy a bezvýsledne..."

Úloha je prevzatá. Vzorové riešenie je uvedené na tejto stránke (pdf).

Čakanie dvoch na prvú trojicu

Príspevky do našej novej súťaže sa nejako nehrnú, tak som sa rozhodol Vás trochu inšpirovať nasledovnou úlohou:

Dvaja hráči sa dohodli na takýchto pravidlách: Na začiatku si každý hráč zvolí trojicu po sebe idúcich výsledkov hodu mincou, t.j. jednu z možností HHH, HHZ, HZH, HZZ, ZHH, ZHZ, ZZH a ZZZ, kde H znamená hlava a Z znamená znak. Vyhráva ten hráč, ktorého trojica sa pri hádzaní mincou vyskytne ako prvá. Napríklad ak si prvý hráč vyberie trojicu HZZ, druhý hráč trojicu ZZH a na minci padne postupne ZHZHHZHHHZZ, tak vyhráva prvý hráč, pretože trojica HZZ po sebe idúcich výsledkov sa pri hádzaní objavila skôr ako trojica ZZH. Hráč, ktorý si vyberá svoju trojicu ako druhý v poradí, si nemôže zvoliť rovnakú trojicu ako prvý hráč, avšak vie čo si prvý hráč vybral a tomu môže svoju voľbu trojice prispôsobiť. Otázka znie: Je táto hra spravodlivá pre oboch hráčov? Ak nie, ktorý hráč má výhodu?

Dodatok 21.11.: Rasťo už tento problém správne intuitívne odhadol a načrtol riešenie. Aby sme si vyjasnili aj detaily, nakreslil som nasledovný diagram (zodpovedajúci modelu situácie markovovským reťazcom):


Ako je možné z tohoto obrázka vyčítať, ktorú trojicu si má zvoliť druhý hráč v závislosti od toho, ktorú trojicu si zvolí prvý hráč?