25 decembra 2008

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

11 decembra 2008

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

07 decembra 2008

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.")

04 decembra 2008

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.

01 decembra 2008

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.

28 novembra 2008

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

25 novembra 2008

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

18 novembra 2008

Č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áč?

10 novembra 2008

Súťaž o najkrajšiu matematickú úlohu

Pred istým časom som Vám prostredníctvom miniankety položil otázku, či by ste mali záujem zúčastniť sa súťaže na blogu QED o najkrajšiu matematickú úlohu. Výsledky tejto ankety boli mierne optimistické, takže som sa rozhodol, že pôjdem do toho.

Stav súťaže k 20.3.: Do súťaže som už dostal všetkých 12 úloh; takže ďalšie už nie je možné posielať. Onedlho začneme vyberať víťaza.

Pravidlá súťaže: Aby ste sa do tejto súťaže zapojili, pošlite mi e-mailom tieto údaje:
  • Vaše meno, alebo pseudonym*
  • názov úlohy*
  • presné znenie úlohy*
  • zdroj úlohy* (vlastná/prevzatá)
  • ilustračný obrázok
  • doplňujúci komentár
  • vzorové riešenie úlohy
  • svoju www stránku
  • ďalšie údaje o sebe, ktoré chce zverejniť
(Údaje s hviezdičkou sú povinné.)

Každý z Vás môže poslať maximálne 3 úlohy, ktoré publikujem tu na blogu QED ako samostatný príspevok. Vyhradzujem si však právo niektoré z nich zamietnuť, ak nedodáte povinné údaje, ak zadanie nebude spĺňať bežné štandardy kultivovaného textu a podobne.

Do súťaže prijmem prvých dvanásť úloh (hoci predpokladám, že kým sa také množstvo nazbiera, uplynie niekoľko mesiacov). Po uverejnení všetkých úloh vyzvem čitateľov, aby súťažné úlohy sami ohodnotili prostredníctvom ankety. Nie je nutné, aby ste boli Vy sami autorom Vami poslanej úlohy, ale originalitu budú ľudia určite hodnotiť pozitívne.

Víťaz dostane hodnotnú cenu - úplne novú, vyše 700 stranovú knihu Magic Universe z vydavateľstva Oxford University Press. Na stránkach books.google môžete do knihy Magic Universe aj nahliadnuť.

01 novembra 2008

Bodkovaná guľa

V komentári k predchádzajúcemu príspevku navrhol Michal nasledovnú zaujímavú úlohu:

Koľko maximálne môžeme na nepriehľadnú guľu nakresliť bodiek tak, aby pre každú z týchto bodiek existoval smer pohľadu, z ktorého je vidieť len túto jednu bodku a žiadnu inú?

V zadaní predpokladáme, že z každého pohľadu vidíme celú polguľu aj s jej hranicou. Keďže pri takejto formulácii sa môžu vyskytnúť nejasnosti, uvediem aj nasledovné spresnenie.

Nájdite najväčšie prirodzené číslo n s vlastnosťou: Existuje 2n vektorov x1,...,xn,v1,...,vn v priestore Rm, m=3, spĺňajúcich


Alebo pomocou matíc:

Nájdite najväčšie prirodzené číslo n s vlastnosťou: Existujú matice X a V typu n×m, m=3, pre ktoré má matica XVT všetky diagonálne prvky nezáporné a všetky mimodiagonálne prvky záporné.

Tento problém je síce ľahko zrozumiteľný, ale nie celkom triviálny. A ak by sa ho niekomu podarilo matematicky precízne vyriešiť pre ľubovoľnerozmernú guľu, resp. z pohľadu druhej a tretej formulácie pre všetky dimenzie m, tak klobúk dolu.

Dodatok 1 (3.11.): Ako poznamenal v komentároch Peťo, ľahšia sa zdá byť verzia b), ktorá vznikne zámenou neostrej nerovnosti vo formulácii 2 na ostrú nerovnosť, resp. zámenou slov "nezáporné" a "záporné" na "kladné" a "nekladné". V tejto verzii je jasné, že optimálne n je minimálne 2m.

Dodatok 2 (3.11.): Tak som to pre m=3 (t.j. pre klasickú guľu) vyriešil počas prechádzky s Aďkou a Agátkou na Partizánskej lúke a ukázalo sa, že ten problém vôbec nie je až taký ťažký. Práve naopak; riešenie by mohol nájsť aj bystrý žiak základnej školy! Ostáva však záhadou, ako je možné, že ma to riešenie napadlo až po asi hodine premýšľania... :-)

25 októbra 2008

Ali Baba a 40 zbojníkov

Keďže Vás včerajšia úloha očividne veľmi nezaujala, možno Vás zaujme nasledovná jednoduchá, ale zábavná klasika.

Ali Baba zajal 40 zbojníkov (trochu sme si prispôsobili pôvodný dej), ale rozhodol sa niektorých z nich ušetriť. Ali sa rozhodol, že zoradí všetkých 40 zbojníkov do zástupu tak, že každý z nich bude vidieť na hlavu všetkých zbojníkov pred ním, no nebude vidieť na zbojníkov za ním; bude ich len počuť. Potom im všetkým Ali položí na hlavu buď bielu, alebo čiernu čiapku. Ušetrený bude ten zbojník, ktorý uhádne, akú čiapku má na hlave. Svoj tip, t.j. slovo "biela", alebo "čierna" bude môcť každý zbojník povedať len raz a okrem toho nebude môcť povedať nič iné. Poradie, v akom budú zbojníci vyhlasovať svoje tipy, si môžu zvoliť. Predtým však môžete poradiť úbohým zbojníkom stratégiu, ktorá ich zachráni čo najviac. Pokúste sa ju vysvetliť čo najjednoduchšie, pretože je známe, že zbojníci vedia počítať len na prstoch a pritom niektorým z nich už zostal len jeden.

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?

14 októbra 2008

Neodbytný nápadník

Matfyzáčka Katka sa práve nachádza na člnku v strede kruhového jazera, keď zrazu zbadá, že z brehu sa na ňu usmieva jej neodbytný nápadník Fero. Katka vie, že na pevnej pôde Ferovi určite utečie, ak sa Fero nedostaví na miesto jej vylodenia skôr ako ona. Veslovaním sa však Katka pohybuje štyrikrát pomalšie, ako vie Fero bežať po brehu, čiže zamieriť priamo na opačnú stranu jazera jej nepomôže (keďže 4r>πr). Existuje stratégia pohybu po jazere, ktorá Katke zaručí, že sa stretnutiu s Ferom určite vyhne? (Predpokladáme, že Katka v každom okamihu presne pozná pozíciu ako svojho člnku, tak aj Fera. A samozrejme Fero nevie plávať.)

S touto elementárnou, ale peknou úlohou som sa stretol v už viackrát spomínanej knihe Martina Gardnera. Pochopiteľne, trochu som pomenil osoby a obsadenie. Svoje riešenie môžete napísať ako komentár k tomuto príspevku.

03 októbra 2008

Kto z Vás má najlepší kvantitatívny odhad?

Pokúste sa odhadnúť bez použitia akýchkoľvek pomôcok okrem svojho zraku a rozumu nasledovné čísla: 1) Počet zelených bodíkov na prvom obrázku; 2) Celkovú dĺžku červenej uzavretej krivky na druhom obrázku; 3) Vertikálnu (y-ovú) súradnicu ťažiska systému modrých krúžkov na treťom obrázku.

Svoje tri číselné odhady môžete napísať do komentárov; vyhráva ten, kto dosiahne minimálnu hodnotu chyby vypočítanej podľa vzorca:

kde n1, n2, n3 sú Vaše odhady a n*1, n*2, n*3 sú skutočné hodnoty. (Všimnite si, že tento vzorec penalizuje nulou presný odhad a jednotkou odhad, ktorý je buď dvojnásobok, alebo polovica v porovnaní so skutočnou hodnotou.)

Poznámka 7.10.: Tipovaciu súťaž sme už ukončili. Výsledky a "diskusiu" si môžete prečítať v komentároch.

30 septembra 2008

Zábava s angličtinou: kvázipalindrómy

V poslednej dobe mám menej času na blog (začal sa semester) ale v rámci oddychu sem občas niečo malé pridám. Dnes som sa trochu pohral s anglickým frekvenčným slovníkom a vyhľadal som také štvor- a viacpísmenové slová, ktoré majú význam aj keď ich prečítame odzadu (akési kvázipalindrómy; možno to má nejaké oficiálne meno). Pozrite si ich zoznam; víťazmi sa pre mňa stali dvojice tinker-reknit, live-evil a repel-leper. :-)

Poznámka 2.10.: Mišov komentár ma primäl k tomu, aby som (pomocou počítača) vyhľadal aj tie anglické jednoslovné "kvázipalindrómy", ktoré nie sú v základnom tvare. Je ich celkom dosť (tu je zoznam) a to mi určite ešte nejaké chýbajú.

23 septembra 2008

Zábava s angličtinou: palindromes

palindrome: a word, line, verse, number, sentence, etc., reading the same backward as forward, as "madam".

Pokúste sa v priebehu troch minút napísať čo najviac anglických jednoslovných palindrómov, t.j. slov, ktoré sa čítajú rovnako odpredu aj odzadu, pričom nepočítame vlastné podstatné mená, skratky a citoslovcia. Koľko ste ich našli? (Slovo "madam" sa nezapočítava :-)

Skontrolujte si správnosť podľa tohoto zoznamu, ktorý som vygeneroval v R-ku pomocou frekvenčného slovníka. Svoj výsledok prosím zaznačte do formulára v pravom stĺpci blogu. (Poll sme už ukončili; výsledky si môžete pozrieť na obrázku na konci príspevku.)

Poznámka 29.9.: Do zoznamu palindrómov som doplnil niektoré slová, ktoré nie sú v základnom tvare. Samozrejme, stále nemôžem s istotou tvrdiť, že môj zoznam je kompletný.

22 septembra 2008

Počítame šesťuholníky II

Máme šesťuholník, ktorého všetky vnútorné uhly sú 120 stupňov, pričom dĺžka strán AB a DE je n1, dĺžka strán BC a EF je n2 a dĺžka strán CD a FA je n3 (kde n1, n2 a n3 sú prirodzené čísla). Tento šesťuholník pokryjeme rovnostrannými trojuholníkmi so stranami dĺžky 1. Koľko pravidelných (rovnostranných) šesťuholníkov sa dá nájsť vo vzniknutom obrazci?

Na ilustračnom obrázku máme znázornený prípad n1=2, n2=3 a n3=5, kde nájdeme 30 pravidelných šesťuholníkov (8 takých, ktoré majú strany dĺžky 2 a 22 takých, ktorých strany majú dĺžku 1).

Pomocou Katkinho riešenia predchádzajúceho príkladu by nemal byť problém túto úlohu vyriešiť. Riešenie indukciou môže byť užitočná nezávislá kontrola.

19 septembra 2008

Počítame šesťuholníky

Nasledovná úloha ma opäť napadla pri hre s Agátkou a geomagom. Je samozrejme veľmi jednoduchá, avšak riešenie je netradične príjemné.

Koľko pravidelných šesťuholníkov je možné nájsť na obrázku veľkého pravidelného šesťuholníka so stranami dĺžky n, ktorý je poskladaný z rovnostranných trojuholníkov so stranami dĺžky 1?

Na ilustračnom obrázku je znázornený prípad n=2, pre ktorý je správna odpoveď 8; jeden pravidelný šesťuholník má strany dĺžky 2 a 7 ďalších šesťuholníkov má strany dĺžky 1.

Poznámka 22.1.: Vidím, že sa nemáte k činu, čo ma trochu mrzí, pretože mám pripravené zovšeobecnenie tejto úlohy a nechcem ho uviesť skôr, ako máme vyriešený tento špeciálny prípad. Aby som Vás trochu inšpiroval, zobrazil som situáciu pre n=3:


Na obrázku je 1 pravidelný šesťuholník so stranou veľkosti tri, 7 pravidelných šesťuholníkov so stranou veľkosti 2 a 19 pravidelných šesťuholníkov so stranou veľkosti 1. Spolu je to teda 27 šesťuholníkov.

04 septembra 2008

Hadamardova hypotéza

Sériu príspevkov týkajúcich sa konfigurácií kameňov by som chcel ukončiť jednou naozaj ťažkou úlohou. Tak ťažkou, že odoláva pokusom o vyriešenie už minimálne od tridsiatych rokov 20. storočia, no s veľkou pravdepodobnosťou nad ňou rozmýšľali už v 19. storočí James Sylvester a Jacques Hadamard. Ale kto vie? Možno je medzi Vami niekto, koho napadne nejaký veľmi originálny trik a stane sa slávnym...

Jedno z viacerých možných zadaní tejto úlohy je prekvapivo jednoduché:

Hadamardova domnienka: Nech n je akýkoľvek násobok štyroch a nech mriežka n×n má najnižší riadok ako aj najľavší stĺpec pokrytý čiernymi kameňmi. Je možné túto mriežku doplniť bielymi a čiernymi kameňmi tak, že každá dvojica riadkov ako aj každá dvojica stĺpcov má presne na n/2 pozíciách kamene rovnakej farby a na zvyšných n/2 pozíciách kamene rôznej farby?

Na ilustračnom obrázku je názorná ukážka, že to skutočne je možné pre n=4 a n=8:


Uveďme si ešte dve ekvivalentné formulácie Hadamardovej domnienky; prvá je klasická a druhú som pre Vás poprivymyslel ja.

Ekvivalentná formulácia 1: Existuje pre každé n, ktoré je násobkom štyroch Hadamardova matica Hn? Hadamardova matica Hn je taká matica typu n×n, ktorej prvky sú buď -1, alebo 1 a pre ktorú platí HnHnT=nIn, kde T označuje transpozíciu matice a In je jednotková matica rozmeru n×n.

Ekvivalentná formulácia 2: Nech n je akýkoľvek násobok štyroch. Dá sa vybrať n vrcholov (n-1)-rozmernej kocky tak, aby všetky vzájomné vzdialenosti týchto vrcholov boli rovnaké?

Všimnite si, že pre n=4 je podmienka z formulácie 2 splnená: Skutočne, ľahko nájdeme také štyri vrcholy klasickej trojrozmernej kocky, ktoré majú všetky vzájomné vzdialenosti rovnaké, t.j. tvoria vrcholy pravidelného štvorstenu:


Dôležitosť Hadamardovej domnienky umocňuje fakt, že Hadamardove matice nie sú len intelektuálnou zábavkou pre čistých matematikov, ale majú veľmi konkrétne aplikácie, napríklad v teórii kódovania, alebo pri navrhovaní štatistických experimentov.

Ak sa Vám nepodarí vyriešiť našu úlohu vo všeobecnosti, t.j. pre všetky násobky štyroch, môžete sa pokúsiť aspoň nájsť príslušnú konfiguráciu kameňov (Hadamardovu maticu, resp. n-ticu vrcholov kocky) pre konkrétny násobok štyroch. Najmenšia veľkosť, pre ktorú takáto konfigurácia ešte nie je skonštruovaná, je n=668.

Formuláciu 2 odporúčam pre tých, ktorí majú obzvlášť dobrú geometrickú predstavivosť. Stačí si totiž predstaviť 667 rozmernú hyperkocku a z jej približne 6×10200 vrcholov vybrať 668, ktoré tvoria vrcholy pravidelného 667 rozmerného simplexu.

Držím palce! :-)

Poznámka: Budúci týždeň som na konferencii, takže chvíľu nebudem písať na blog. Stay tuned!

27 augusta 2008

Chaotický trojfarebný trojuholník

Chaotickým k-farebným trojuholníkom veľkosti n nazvime trojuholník poskladaný z 1+2+...+n kameňov k farieb, ktorý neobsahuje žiadnu trojicu kameňov rovnakej farby umiestnených vo vrcholoch trojuholníka so stranami rovnobežnými so základným trojuholníkom.

Formulujeme si jednu teoretickú úlohu a jednu súťaž pre všetkých, ktorí si myslia, že sú programátorskí machri.

Úloha: Dokážte, že existuje najväčší trojfarebný chaotický trojuholník. Inými slovami, ukážte, že existuje prirodzené číslo n také, že trojfarebný chaotický trojuholník veľkosti n už principiálne nie je možné skonštruovať. Môžete použiť Peťove riešenie predchádzajúceho príkladu a Van der Waerdenovu vetu, na ktorú nás upozornil Nanyk.

Súťaž: Pomocou počítača nájdite trojfarebný chaotický trojuholník s veľkosťou aspoň 15, t.j. väčší ako ten, ktorý som našiel ja:


Nie som si úplne istý s tým, že existuje väčší trojfarebný chaotický trojuholník ako ten môj, ale považujem to za veľmi pravdepodobné. Môj trojuholník je totiž výsledkom krátkeho výpočtu jednoduchého programu v pomalom jazyku R. Každopádne ak sa do riešenia tejto úlohy pustíte, pošlite nám najväčší trojfarebný chaotický trojuholník aký nájdete.

28.8.: Mišo našiel chaotický trojfarebný trojuholník veľkosti 16! Tu je:


Kto Miša prekoná má môj obdiv! To už ale bude asi poriadne ťažké...

26 augusta 2008

Neexistujúce trojuholníky

Na rozdiel od predchádzajúcej úlohy, vyriešenie nasledovného problému si vyžaduje len trochu postrehu a systematický postup.

Z čiernych a bielych kameňov sa snažím poskladať rovnostranný trojuholník so základňou "dĺžky" 5 kameňov ale tak, aby neobsahoval žiadny "monochromatický" rovnostranný trojuholník, t.j. trojuholník, ktorého strany sú rovnobežné so stranami základného trojuholníka a ktorého vrcholy tvoria kamene rovnakej farby. Otázka znie: dá sa to?

Na obrázku je jeden môj neúspešný pokus. (Inak mienim napísať už len tri blogové príspevky o konfiguráciách farebných kameňov a prejdem na niečo iné. Sľubujem :-)

Poznámka 27.8.: Veľmi pekné riešenie tohoto príkladu napísal na svoj blog Peter.

25 augusta 2008

Me3ce

Predstavme si, že vedľa seba kladieme farebné kamene. Monochromatická ekvidištantná trojica, skrátene me3ca, bude každá taká trojica kameňov rovnakej farby, pre ktorú platí: vzdialenosť prvého a druhého kameňa tejto trojice je rovnaká ako vzdialenosť druhého a tretieho kameňa tejto trojice. Na ilustračnom obrázku som znázornil sériu 10 kameňov dvoch farieb, ktorá obsahuje až 5 me3íc.

Ako sa môžete sami ľahko presvedčiť (napríklad otestovaním všetkých 512 možností na počítači), každá séria pozostávajúca z deväť kameňov dvoch farieb už nutne obsahuje nejakú me3cu. Osem kameňov dvoch farieb však me3cu obsahovať nemusí; všimnite si napríklad postupnosť 0X0XX0X0. Takže s dvomi farbami je otázka existencie bezme3cových sérií jednoduchá. Ukazuje sa však, že pre tri farby je to oveľa ťažšie:

Existuje také prirodzené číslo n, že každá séria n kameňov troch farieb obsahuje aspoň jednu me3cu?

Sám na túto zdanlivo jednoduchú otázku neviem odpovedať; môj polhodinový limit na jej vyriešenie nestačil. Preto sa opäť s dôverou obraciam na Vás. :-) Vzhľadom na to, že tento problém nie je triviálny, môžete do komentárov uvádzať nielen úplné riešenie, ale aj každý potenciálne užitočný postreh.

Poznámka 26.8.: Ako v komentári upozornil Nanyk, tento problém je zhodou okolností známy a veľmi ťažký a odpoveď je kladná pre ľubovoľný počet farieb a ľubovoľnú dĺžku ekvidištantnej série. Pre tri farby je maximálna bezme3cová séria dĺžky 26, napríklad

RRYYRRYBYBBRBRRYRYYBRBBYBY

a je dokázané, že každá séria dĺžky 27 už nejakú me3cu obsahuje.

A ak si chcete privyrobiť 1000 dolárov stačí, keď pre každé k ukážete, že pre niektoré n menšie než 2 na k2 platí, že každá séria kameňov dvoch farieb dĺžky n už obsahuje nejakú ekvidištantnú monochromatickú k-ticu. Túto odmenu Vám udelí jeden z najvýznamnejších žijúcich matematikov, Ronald Graham.

22 augusta 2008

Neexistujúce obdĺžniky II

Z riešenia úlohy "neexistujúce obdĺžniky" plynie, že konfigurácia kameňov dvoch farieb na mriežke 5×5, alebo väčšej, musí nutne obsahovať aspoň jeden monochromatický obdĺžnik. Ak však máme k dispozícii kamene viacerých farieb, úloha sa skomplikuje.

Existuje vôbec nejaké prirodzené číslo n také, že akákoľvek konfigurácia n×n kameňov troch farieb obsahuje aspoň jeden monochromatický obdĺžnik?

Na ilustračnom obrázku je znázornená konfigurácia 7×7 kameňov troch farieb, ktorá žiadny monochromatický obdĺžnik neobsahuje. To znamená, že ak aj existuje n zo zadania našej úlohy, tak je minimálne 8.

Poznámka 1: Nanyk už našu úlohu vyriešil (pozri komentáre) a z jeho riešenia plynie, že ak je n aspoň 22, tak mriežka n×n kameňov troch farieb už určite obsahuje aspoň jeden monochromatický obdĺžnik. Ak sa chcete s týmto problémom ešte trochu pozabávať, môžete sa pokúsiť buď hornú hranicu 22 znížiť, alebo dolnú hranicu 8 zvýšiť.

Poznámka 2: Trochu som sa s tým hral a podarilo sa mi nájsť konfiguráciu 9×9 kameňov troch farieb neobsahujúcu monochromatický obdĺžnik; pozri obrázok:

Minimálne n, pre ktoré mriežka n×n troch farieb nutne musí obsahovať monodĺžnik, je teda medzi 10 a 22.

21 augusta 2008

FErdóšove piškvorky

Včerajší problém sa nám podarilo úspešne vyriešiť a ešte sme k tomu pridali aj viacero ďalších zaujímavých nápadov. Obdĺžnik, ktorý má všetky vrcholy na kameňoch rovnakej farby, sme nazvali monochromatický obdĺžnik, alebo skrátene monodĺžnik.

Z komentárov ma zaujala hra, ktorú by som nazval "FErdóšove piškvorky", s nasledovnými jednoduchými pravidlami:

Dvaja hráči kladú na mriežku veľkosti n×n kamene, prvý hráč biele a druhý čierne. Vyhráva ten, kto ako prvý vytvorí zo svojich kameňov monodĺžnik.

Keďže na mriežke 5×5 obsahuje každá konfigurácia z kameňov dvoch farieb nejaký monodĺžnik, tak na tejto mriežke, alebo aj na akejkoľvek väčšej, nemôže táto hra skončiť remízou. Stačí si zobrať jednu sadu GO kameňov a môžete hrať! Zaujímavé by to bolo vtedy, ak by neexistovala jednoduchá vyhrávajúca stratégia. Keď si kliknete na ilustračný obrázok, spustí sa Vám animovaný gif jednej hry, v ktorej si biely vynútil výhru už po druhom ťahu čierneho.

Ak si FErdóšove piškvorky zahráte, napíšte nám do komentárov svoje dojmy.

Variant 1: Trochu som sa s tým pohral a vyzerá to tak, že v klasickej hre si biely vždy pomerne jednoducho vynúti výhru. Zaujímavou sa táto hra môže stať vtedy, keď trochu upravíme pravidlá:

Ja mám biele a Ty čierne kamene. Na začiatku Ty umiestniš moje dva biele a svoje dva čierne kamene kdekoľvek chceš, samozrejme tak, aby si mi otvorenie čo najviac sťažil a sebe čo najviac zjednodušil. Potom už kladieme kamene striedavo, t.j. ja biely kameň, Ty čierny a tak ďalej, až kým jeden z nás nevytvorí monodĺžnik.

Variant 2: V komentári ma Nanyk presvedčil, že predchádzajúca obmena pravidiel už dáva rozhodujúcu výhodu čiernemu. Napadla ma však ďalšia obmena, ktorá stavia všetko na hlavu:

Dvaja hráči kladú na mriežku veľkosti 5×5 kamene, prvý hráč biele a druhý čierne. Ten, kto ako prvý vytvorí zo svojich kameňov monodĺžnik, PREHRÁVA.

Cieľom je teda prinútiť svojho súpera aby vytvoril monodĺžnik. Opäť, na základe výsledku predchádzajúcej úlohy vieme, že táto hra nemôže skončiť remízou.

Ak máte chuť, môžeme si dať prostredníctvom komentárov jednu partičku. Sĺpce označíme a-e a riadky 1-5. Keďže sa zdá jasné, že biely je v nevýhode, tak biely budem ja a začínam ťahom c3. :-)

20 augusta 2008

Neexistujúce obdĺžniky

Počas poobedňajšej prestávky ma dnes napadol jeden rekreačný problém, ktorý som sa bezúspešne snažil vyriešiť asi pol hodiny a viac času naň neobetujem. Ale Vy možno budete úspešnejší.

Existuje taká konfigurácia 25 bielych a čiernych kameňov na mriežke 5 krát 5, že žiadna štvorica kameňov rovnakej farby neleží na vrcholoch spoločného obdĺžnika, ktorý má strany rovnobežné so stranami štvorca?

Na obrázku je znázornený jeden môj neúspešný pokus, v ktorom existujú až dva obdĺžniky s vrcholmi rovnakej farby. Keďže riešenie tohoto problému nepoznám, nemôžem zaručiť, že nie je veľmi ťažký!

15 augusta 2008

Katalóg konvexných polyédrov

Pri riešení najnovšieho problému od Peťa ma napadlo, že by sme si mohli zadať nasledovnú úlohu trochu nezvyklého typu:

Na obrázku vyššie (kliknutím sa zväčší) zodpovedajú riadky počtu v vrcholov a stĺpce počtu e hrán. Do niektorých políčok som už doplnil telesá, ktoré majú príslušný počet vrcholov a hrán. Bod získava ten, kto ako prvý doplní do niektorého prázdneho políčka nejaký konvexný polyéder s príslušným počtom vrcholov a hrán, prípadne ak dokáže, že pre kombináciu v a e (spomedzi tých kombinácií, ktoré sú na obrázku) neexistuje žiadny konvexný polyéder s počtom vrcholov v a počtom hrán e.

Pochopiteľne, výhodu má ten, kto sa do riešenia pustí ako prvý, pretože neskôr sa budú hľadať príslušné telesá alebo dôkazy ťažšie. Nájdené telesá môžete popísať slovne (napríklad ako ich možno dostať z iných telies) v komentári k tomuto príspevku, alebo mi môžete poslať načrtnutý obrázok mailom. Pokúste sa riešiť daný problém vlastnými silami. Nikomu by nepomohlo, ak by ste vypátrali kompletné riešenie niekde na internete a potom sa ním tu prezentovali.

17.8.: Štyri polyédre doplnila Hugo.
18.8.: Ďalších päť polyédrov doplnila Hugo.
19.8.: Ešte ďalších päť polyédrov doplnila Hugo.
20.8.: Peťo ukázal nemožnosť konštrukcie 17-tich polyédrov.
20.8.: Posledné okienko zaplnila Hugo.

Ako Dumbledore udeľujem ešte 1 bod navyše pre Huga(u?) za pozitívne výsledky a Peťovi -1 bod za negatívne výsledky, čiže celkový výsledok zápasu Hugo-Peťo je 16:16. :-)

12 augusta 2008

Geomag

Konštrukčná sada Geomag nie je lacný špás, ale čo by už človek nekúpil svojej jedinej dcérke, všakže. Základom Geomagu sú oceľové guličky a magnety v podobe tyčiniek, ktorých spájaním je možné vyrobiť množstvo priestorových modelov, napríklad základných trojrozmerných telies. Agátkina sada obsahuje okrem guličiek a tyčiniek aj farebné "výplne" v tvare rovnostranného trojuholníka, štvorca, kosoštvorca a pravidelného päťuholníka, ktoré je možné použiť na spevnenie, alebo skrášlenie vzniknutých konštrukcií.

Zoo konvexných priestorových telies, ktoré majú všetky hrany rovnakej dĺžky a ktorých steny sú pravidelné n-uholníky, môžeme v zásade rozdeliť do piatich skupín: platónske telesá, archimedovské telesá, prizmy, antiprizmy a Johnsonove telesá. Na nasledovnom obrázku sú znázornené štyri Johnsonove telesá poskladané z Geomagu (kliknutím sa obrázok zväčší).


Konkrétne, na fotografiách sú augmented tridiminished icosahedron (vľavo hore), square gyrobicupola (vpravo hore), biaugmented pentagonal prism (vľavo dole) a bilunabirotunda (vpravo dole). Samozrejme, na zložitejšie telesá by sme potrebovali oveľa viac ako 31 tyčiniek a 24 guličiek, ktoré obsahuje naša sada. Vytrínový kúsok by mohol byť napríklad taký Parabigyrate Rhombicosidodecahedron.

Na koniec tohto príspevku ešte jedna oddychová úloha, ktorá je inšpirovaná tabuľkou v dolnej časti stránky mathworldu o Johnsonovych telesách.

Konvexné trojrozmerné teleso má n3+n4+n5 stien, z toho n3 trojuholníkových, n4 štvorcových a n5 päťuholníkových. Koľko má toto teleso vrcholov?

08 augusta 2008

Štyri guličky

Obligátnou súčasťou zbierok úloh z rekreačnej matematiky sú príklady týkajúce sa váženia guličiek. Tú najznámejšiu úlohu tohoto typu sme už na blogu QED mali a ak by ste mali záujem, môžeme si tu formulovať aj inú podobnú klasiku. Dnes večer som však pre Vás vymyslel zbrusu nový príklad, ktorý sa tiež týka váženia. Na jeho vyriešenie nie je nutné poznať žiadnu vyššiu matematiku; odborné vzdelanie pri jeho riešení nepredstavuje veľkú výhodu. Logické myslenie však samozrejme áno.


Mám štyri na pohľad rovnaké guličky, pričom s istotou viem, že práve jedna z nich je buď ľahšia alebo ťažšia v porovnaní so zvyšnými tromi, ktoré majú presne rovnakú hmotnosť. Máme k dispozícii dvojmiskovú elektronickú váhu, ktorá vie oznámiť len dva rôzne výsledky a to: "hmotnosť v miske naľavo je väčšia ako hmotnosť v miske napravo", alebo "hmotnosť v miske napravo je väčšia ako hmotnosť v miske naľavo". Ak sa na miskách vážia rôzne hmotnosti, odpovie váha zaručene správne. Ale ak sa vážia rovnaké hmotnosti, zvolí váha každú zo svojich dvoch možných odpovedí s pravdepodobnosťou 1/2. Našim cieľom je zistiť, ktorá z guličiek je odlišná od ostatných dvoch a či je ľahšia, alebo ťažšia. Môžeme však vykonať maximálne 3 váženia. Aký systém váženia by ste zvolili?

07 augusta 2008

Banachov-Tarskeho paradox: časť 3: baby

Samotný Banachov-Tarskeho paradox nie je vôbec jednoduché dokázať, pretože pozostáva z pomerne veľkého počtu krokov. Avšak existujú aj také tvrdenia, ktoré v sebe obsahujú podobný kolaps intuície ako Banachov-Tarskeho paradox, no ich formálny dôkaz je relatívne krátky. Tieto tvrdenia sa nazývajú "baby Banach-Tarski" a my si teraz jedno takéto baby ukážeme.

Povieme, že reálne čísla x a y z intervalu [0,1] sú "ekvivalentné", zapisujeme x~y, ak je rozdiel x-y racionálne číslo. Relácia "~" je takzvanou reláciou ekvivalencie, pretože platí a) x~x, b) ak x~y, tak y~x a c) ak súčasne x~y a y~z, tak aj x~z. Relácia ~ rozkladá interval [0,1] na disjunktné "triedy ekvivalencie", t.j. na množiny navzájom ekvivalentných čísiel.

Jednou z tých tried ekvivalencií je napríklad množina všetkých racionálnych čísiel v intervale [0,1]. Ak s je akékoľvek fixné iracionálne číslo, tak všetky tie čísla s+q z intervalu [0,1], pre ktoré je q racionálne číslo, tiež tvoria triedu ekvivalencie. Je zrejmé, že každá z týchto tried ekvivalencie je spočítateľná množina, ale samotný počet týchto tried je nespočítateľný.

Všimnite si, že už tento rozklad intervalu [0,1] na triedy ekvivalencie je dosť nenázorný. Príslušné triedy ekvivalencie sú navzájom úplne "prepletené"; napríklad platí, že pre každé číslo x v intervale (0,1) a pre ľubovoľné dostatočne malé kladné ε obsahuje intervalík (x-ε, x+ε) nekonečne veľa prvkov z každej jednej tejto triedy ekvivalencie.

Každopádne, na základe axiómy výberu vieme z každej z týchto tried ekvivalencie vybrať po jednom čísle. Množina pozostávajúca z práve jedného zástupcu z každej triedy ekvivalencie sa nazýva Vitaliho množina a my ju budeme označovať symbolom V. (Samozrejme, takýchto výberov existuje nekonečne veľa, čiže aj Vitaliho množín je v zmysle našej definície nekončene veľa. My však budeme pracovať s jednou fixnou Vitaliho množinou V.)

Označme množinu racionálnych čísiel Q a množinu racionálnych čísiel v intervale [0,1] ako Q[0,1]. Keďže množiny Q[0,1] a Q sú obe nekonečné spočítateľné, tak existuje bijektívne zobrazenie f medzi množinami Q[0,1] a Q. To znamená, že pre každé racionálne číslo q existuje práve jedno racionálne číslo r z intervalu [0,1], pre ktoré platí f(r)=q.

Uvažujme nasledovné dva spočítateľné systémy množín.


Ľahko si dokážete platnosť nasledovných tvrdení.

1) Ako systém A, tak aj systém B pozostáva z navzájom disjunktných množín.
2) Každá množina zo systému A je podmnožinou intervalu [0,2].
3) Množiny systému B sú len posunutím množín systému A.
4) Zjednotenie množín zo systému B je množina všetkých reálnych čísiel.

Čiže, voľne povedané, množiny V+r, kde r je z Q[0,1], sa navzájom nijako neprekrývajú a všetky spoločne okupujú len istú časť intervalu [0,2]. No napriek tomu je ich možné poposúvať tak, že kompletne pokryjú celú reálnu priamku!

Ako je takéto niečo možné? Základom všetkých podobných paradoxov je existencia "nemerateľných množín", t.j. množín, ktorým principiálne nevieme priradiť "úhrnnú dĺžku" (v prípade štandardného Banachovho-Tarskeho paradoxu sa jedná o množiny, ktorým nie je možné nijako konzistentne priradiť "celkový objem"). V našom prípade je nemerateľnou množinu práve Vitaliho množina.

04 augusta 2008

Dva znaky


Budeme hádzať mincou až pokým nepadne znak dvakrát za sebou. Koľko budeme potrebovať v strednej hodnote (t.j. "v priemere") hodov?

Toto je pomerne prirodzená a častá úloha, ktorej riešenie však nie je úplne triviálne. (Jej ekvivalentná formulácia sa vyskytuje napríklad v tejto Oxfordskej učebnici).

5.8.: Úlohu sme už nielenže vyriešili (pozri komentáre), ale Peťo prišiel s takým postupom, ktorý sa dá použiť na vyriešenie oveľa všeobecnejšej úlohy:

Robíme nezávislé experimenty, pričom každý experiment môže skončiť výsledkom "úspech" (s pravdepodobnosťou p), alebo výsledkom "neúspech" (s pravdepodobnosťou 1-p). Skončíme akonáhle zaznamenáme k úspešných experimentov za sebou. Aká je stredná hodnota všetkých experimentov, ktoré vykonáme?

Výsledok je nasledovný:


S prvou formulkou sa ľahšie počíta ak je k veľké číslo, druhá mi však pripadá krajšia. V špeciálnom prípade, ktorý zodpovedá pôvodnému zadaniu, máme p=1/2 a k=2, čiže výsledok je 6. Ak by sme napríklad hádzali kockou a čakali na padnutie troch šestiek za sebou, tak p=1/6 a k=3, čiže očakávaný počet hodov je 6+62+63=258 :-)

Inak uvažujem, že vypíšem súťaž, ktorú vyhrá ten z Vás, kto nám pošle najzaujímavejšiu matematickú úlohu. Čo Vy na to? Svoje názory, prípadne organizačné pripomienky môžete písať do komentárov k tomuto príspevku a tiež sa môžete vyjadriť v novej miniankete (v pravom stĺpci blogu).

30 júla 2008

Blcha v meste

Nasledovná jednoduchá úloha ma dnes napadla pri čítaní učebnice teórie informácie. (Matematickým základom teórie informácie je teória pravdepodobnosti.)

Blšia krajina je tvorená n dedinami rozmiestnenými vo vrcholoch pravidelného n-uholníka a jedným mestom. Keď sa blcha nachádza v dedine, skočí buď do niektorej z dvoch najbližších susedných dedín, alebo do mesta (každú z týchto troch možností si vyberá s pravdepodobnosťou 1/3). Ak je blcha v meste, skočí náhodne do niektorej z dedín (každú si volí s rovnakou pravdepodobnosťou). Predpokladáme, že blcha urobí jeden skok každú minútu a samotný skok trvá zanedbateľný čas. Blcha už takto skáče veľmi dlho. Odhadnite, s akou pravdepodobnosťou sa blcha práve nachádza v meste.

Na obrázku je ilustrovaná blšia krajina s n=6. Túto úlohu vie mechanicky vyriešiť každý, kto absolvoval prednášku z Markovovych reťazcov, ale s malým nápadom sa dá vyriešiť aj bez akejkoľvek vyššej matematiky.

Poznámka 31.7.: Trochu to zadanie upresním. Označme ako pn pravdepodobnosť, že po n skokoch sa bude blcha nachádzať v meste. Dá sa ukázať, že nezávise na tom, kde blcha svoje skoky začala, konverguje postupnosť p1, p2, p3, ... k pevnému číslu. Pýtame sa práve aké je to číslo.

29 júla 2008

Archimedov problém

S nasledovným problémom som sa prvýkrát stretol v Gardnerovej zbierke matematických hlavolamov. Túto úlohu však riešil a správne vyriešil už Archimedes. Ja som si ňou lámal hlavu vyše pol hodiny, kým som zistil, aká je triviálna :-)

Uvažujme dva nekonečne dlhé valce, oba s priemerom 1, ktorých osi sa pretínajú pod pravým uhlom. Aký je objem telesa zodpovedajúceho prieniku týchto dvoch valcov?

25 júla 2008

Hádanky z Wordle

Program Wordle je založený na jednoduchom, no veľmi peknom nápade: Z akéhokoľvek vstupného textu urobí "oblak slov", pričom veľkosť jednotlivých slov je určená ich frekvenciou výskytu v danom texte. Farby, pozíciu a niekoľko ďalších vlastností výsledného oblaku si môžete sami nastaviť. Jednoducho príjemná zábava na daždivé dni. Dnes ma však napadlo, že pomocou Wordle sa dajú vyrobiť aj originálne hádanky.

Nasledujúce oblaky slov zodpovedajú stručným životopisom štyroch významných Rakúšanov. Viete odhaliť, o ktorých ľudí sa jedná?

Keď na obrázky kliknete, tak sa zväčšia. Aj menšie slová môžu znamenať rozhodujúcu nápovedu.