100 vrabcov

Na kruhovú obruč polomeru 10 metrov si náhodne a nezávisle sadne 100 vrabcov. Odhadnite (intuitívne, simulačne, analyticky, akokoľvek) pravdepodobnosť, že ťažisko tohto kŕdľa sediacich vrabcov bude vzdialené menej ako 1 meter od stredu obruče.

Štyri mestá

Ilustračný obrázok

Štyri mestá ležia vo vrcholoch štvorca so stranou 100 kilometrov. Nájdite čo najkratšiu cestnú sieť, po ktorej sa dá prejsť z každého z týchto miest do každého iného. (Dĺžku cestnej siete chápeme ako súčet dĺžok všetkých jej segmentov.)

Poznámka: Toto je problém, ktorý som navrhol pre rubriku "Hádanky" Denníka N. Pozri túto stránku, kde nájdeš riešenie aj diskusiu. :)

Žaba

Nasledovný hlavolam nám na konferencii mODa10 zadal náš švajčiarsky kolega David Ginsbourger.

Za sebou v rade je 100 vypínačov, ktoré sú na začiatku vo vypnutom stave. Žaba postupne poskáče po všetkých vypínačoch, čím ich zapne. Následne sa žaba vráti na začiatok radu vypínačov a poskáče po každom druhom z nich, čím poskákané vypínače vypne. Potom sa žaba opäť vráti na začiatok a poskáče po každom treťom vypínači, čím zapnuté vypínače vypne a vypnuté vypínače zapne. Potom sa žaba znovu vráti na začiatok radu vypínačov a poskáče po každom štvrtom z nich, čím opäť zapnuté vypínače vypne a vypnuté zapne... Žaba takto preskáče cez rad vypínačov stokrát. Ktoré vypínače budú na konci zapnuté?

Samozrejme, riešenie sa dá veľmi rýchlo nájsť na papieri (alebo pomocou počítača). Pokúste sa však túto úlohu vyriešiť bez akýchkoľvek pomôcok.

 

Nová formulácia úlohy:

Za sebou v rade je nekonečne veľa vypínačov očíslovaných 1,2,3,..., ktoré sú na začiatku vo vypnutom stave. Chuck Norris postupne stlačí každý z nich, čím ich zapne. Následne stlačí vypínače 2,4,6,..., čím všetky stlačené vypínače vypne. Potom Chuck Norris stlačí vypínače 3,6,9,..., čím zapnuté vypínače vypne a vypnuté vypínače zapne. Následne Chuck Norris postláča každý štvrtý vypínač, potom každý piaty a tak ďalej. Ktoré vypínače budú na konci zapnuté?

Ak by ste sa čudovali, ako môže Chuck Norris postláčať toľko vypínačov, tak sa teda nečudujte, lebo je to veľmi jednoduché. Chuck totiž stlačí prvý vypínač za 1/2 sekundy, druhý za 1/4 sekundy, tretí za 1/8 sekundy a tak ďalej. Pri stláčaní každého druhého vypínača vykoná prvé stlačenie za 1/4 sekundy, druhé za 1/8 sekundy, tretie za 1/16 sekundy... Pri stláčaní každého tretieho vypínača vykoná prvé stlačenie za 1/8 sekundy, druhé stlačenie za 1/16 sekundy, tretie za 1/32 sekundy a tak ďalej. Koľko to vlastne bude Chuckovi Norisovi celkovo trvať?

Samozrejme, túto úlohu už vyčerpávajúco nevyriešite len pomocou "podčiarkovania" číselného radu zapísaného na papieri. Teda ... pokiaľ nie ste Chuck Norris.

Ťažisko

Úlohou je do n ekvidištantných pozícií na kružnici vo vhodnom poradí rozmiestniť guľôčky s hmotnosťami 1, 2, 3, ..., n gramov a to tak, aby ťažisko sústavy týchto guľôčok bolo presne v strede kružnice. Nájdite čo najviac hodnôt n, pre ktoré sa táto úloha dá vyriešiť.

Na ilustračnom obrázku je rozmiestnených 5 guľôčok s hmotnosťami 1,3,4,2 a 5 gramov (v tomto poradí), ktorých ťažisko, označené červenou bodkou, je však máličko vychýlené voči stredu kružnice.

Šesť bodov

Navrhovanie experimentov je pre mňa už skoro desať rokov nevyčerpateľný zdroj inšpirácie. Teória takzvaných blokových návrhov obsahuje matematické tvrdenia, ktoré sa dajú preformulovať do podoby nasledovného príkladu kombinujúceho teóriu grafov a lineárnu algebru.

Pýtame sa, či existuje šestica vektorov x_1,2, x_1,3, x_1,4, x_2,3, x_2,4, x_3,4 v trojrozmernom priestore, ktorá charakterizuje súvislosť obyčajných grafov so štyrmi vrcholmi týmto spôsobom: Graf s hranami h₁, h₂, ..., h_n je súvislý vtedy a len vtedy, keď sa každý vektor v trojrozmernom priestore dá napísať ako lineárna kombinácia vektorov x_h1, x_h2, ..., x_hn.

Ekvivalentná formulácia príkladu: Pýtame sa, či existuje šestica bodov x_1,2, x_1,3, x_1,4, x_2,3, x_2,4, x_3,4 v trojrozmernom priestore s nasledovnou vlastnosťou: Graf s hranami h₁, h₂, ..., h_n je nesúvislý vtedy a len vtedy, keď existuje rovina prechádzajúca počiatkom súradnicového systému obsahujúca súčasne všetky body x_h1, x_h2, ..., x_hn.

Fúrik

Prevážame fúrikom tehly z miesta A na miesto B. Doba trvania jednej "obrátky" (naloženie fúrika, prevoz z A do B, vyloženie, cesta naspať z B do A) závisí od toho, koľko tehál prevážame. Urobili sme 5 pokusných obrátok, ktorých výsledky sumarizuje nasledovná tabuľka.

Počet naložených tehál	3	6	9	12	15	18
Čas obrátky (v sekundách)	18	28	52	60	96	152

Koľko tehál by ste odporučili nakladať do fúrika?

Na rozdiel od väčšiny zábavných hlavolamov, táto úloha nemá "jediné správne" riešenie. V reálnych aplikáciách sa však často vyskytujú práve takéto problémy: údaje zaťažené náhodnou chybou, neznámy alebo veľmi komplikovaný matematický model, niekedy dokonca nie celkom presne definovaný cieľ.

Acknowledgements: Úloha je motivovaná podobnou úlohou, ktorú nám opäť poslal Peťo Mikloš.

Horiace tyče

Majme dve tyče z neznámeho nehomogénneho materiálu, pričom vieme len to, že každá z nich zhorí presne za 1 minútu. Rýchlosť horenia v jednotlivých častiach tyčí kvôli neznámemu zloženiu nevieme určiť. Ako pomocou nich zmerať presne čas 45 sekúnd? Čas zapálenia tyče neuvažujeme. 

Túto peknú úlohu nám poslal Peter Mikloš; ďakujeme! :)

Úloha zo sna

O matematike sa mi sníva pomerne často, no len občas si obsah môjho sna zapamätám natoľko presne, aby malo zmysel sa nad ním viac zamýšľať. V noci zo soboty na nedeľu sa mi snívalo o tom, ako jeden známy slovenský profesor matematiky dostal od študentov úlohu a ani za nič sa mu ju nedarilo vyriešiť; pamätám sa, ako frustrovane mával rukami, v jednej špongia, v druhej krieda, pred tabuľou pokreslenou čiarami pripomínajúcimi abstraktný obraz z pohľadu značne podguráženého obdivovateľa umenia.

Prekvapivo, úloha, ktorú v mojom sne dali študenti profesorovi, je zmysluplná a dosť odlišná od všetkých úloh, nad ktorými som dosiaľ uvažoval v bdelom stave. Fungovanie ľudského mozgu ma neprestáva fascinovať. Tu je spomínaná úloha:

Nech M je množina bodov v rovine a nech x je vektor. Posunutím množiny M o vektor x budeme rozumieť množinu M+x pozostávajúcu z bodov tvaru B+x, kde B patrí M. Racionálnym bodom v rovine nazveme taký bod, ktorého obidve súradnice sú racionálne čísla. Dokážte, že ak M je zjednotením konečného počtu úsečiek, potom existuje vektor x taký, že M+x neobsahuje žiadne racionálne body.

Opica

Opica stotisíckrát náhodne udrie do klávesnice s 26 základnými písmenami, pričom pri každom údere zasiahne každé z písmen s pravdepodobnosťou 1/26. Čo má vo výslednom reťazci väčšiu strednú hodnotu: počet výskytov podreťazca "aaaa", alebo počet výskytov podreťazca "abcd"?

Odpovede na anticipované otázky: Ak sa v reťazci vyskytnú viac ako 4 a-čka za sebou, započítavame každý výskyt štvorice a-čiek ako rôzny podreťazec "aaaa". Čiže napríklad reťazec "xaaaaaaaay" obsahuje až 5 podreťazcov "aaaa", nie dva, zatiaľ čo reťazec "xabcdabcdy" obsahuje samozrejme len dva podreťazce "abcd". Túto úlohu mám od môjho kolegu Jana Somorčíka

Veže

  Agátka si z 21 drevených kociek postavila niekoľko veží. Z každej veže vzala vrchnú kocku a zo zozbieraných kociek postavila novú vežu. Potom opäť vzala z každej veže najvrchnejšiu kocku a z týchto kociek postavila novú vežu a tak ďalej. Keď po dlhom čase so svojou hrou skončila, koľko mala veží? 

Poznámka: Aj jednu kocku považujeme za vežu. Keď z takejto veže vezme Agátka vrchnú (čiže jedinú) kocku, táto veža zanikne a príslušná kocka sa stane súčasťou novej veže.

Tri čísla

  Nájdite tri rôzne prirodzené čísla a,b,c také, že a+b je deliteľné číslom c+1, súčasne a+c je deliteľné číslom b+1 a súčasne b+c je deliteľné číslom a+1.

Poznamenám, že túto úlohu je možné vyčerpávajúco vyriešiť (čiže nájsť všetky riešenia a tiež dokázať, že tie riešenia sú naozaj všetky) na pár riadkov a to len pomocou základnej aritmetiky a úvah týkajúcich sa deliteľnosti.

Studňa

Nasledovnú úlohu položili autori knihy "How to Solve It: Modern Heuristics" veľkému počtu ľudí, z ktorých každý mal aspoň bakalársky titul z matematiky, informatiky, prípadne techniky. Nechce sa mi tomu ani veriť, ale údajne len jedno percento týchto ľudí našlo (nejaké) správne riešenie, pričom mali k dispozícii celú hodinu! Pokúste sa túto úlohu vyriešiť aj Vy a napíšte nám do komentárov ako dlho Vám to trvalo.

Do "dvojrozmernej studne" s vodorovným dnom a zvislými stenami vzdialenými od seba 3 metre sme hodili dve rovné palice dĺžok 4 a 5 metrov, ktoré sa ustálili v pozícii zaznačenej na obrázku. Ako vysoko od dna leží bod, v ktorom sa tieto palice "pretínajú"?

Znamienka

Pre ktoré čísla n existuje n-tica e₁,...,e_n "znamienok" (čiže n-tica pozostávajúca z čísiel -1 a 1) taká, že e₁1+e₂2+...+e_nn=0?

Polárny súčet kružníc

Keď som sa dnes zabával s Matlabom, natrafil som na jeden celkom pozoruhodný fenomén, ktorý ma v prvej chvíli prekvapil. Formulujme si ho ako úlohu.

V rovine máme zakreslených n kružníc C₁,...,C_n prechádzajúcich počiatkom O súradnicovej sústavy. Každá priamka p prechádzajúca bodom O pretne kružnicu C_k v dvoch bodoch - v bode O a v bode, ktorý si označíme A_k(p). (Ak je priamka p dotyková ku kružnici C_k, tak definujeme A_k(p)=O.) Aká je množina všetkých bodov tvaru S(p)=A₁(p)+...+A_n(p), kde p je priamka prechádzajúca počiatkom O? (Body sčítavame ako vektory.)

Táto úloha je možno trochu ťažšia, takže vítané sú aj čiatočné riešenia (napríklad riešenia pre špeciálne prípady), nápady, skrátka akékoľvek potenciálne zaujímavé komentáre.

Vláčik

  V piatok pred dvomi týždňami som cestoval vlakom z Londýna do Paríža a cestu som si krátil čítaním učebnice, ktorú som dostal na recenziu, konkrétne časti o miere zakrivenia kriviek. Vtedy ma napadla nasledovná úloha.

 
  Tri mestečká A,B,C ležia na spoločnej priamke, pričom vzdialenosť A a B je 2 a vzdialenosť B a C je tiež 2. Je potrebné vybudovať systém koľajníc, po ktorých bude nepretržite premávať vlak z A do B, z B do C, z C do A, z A do B atď. Konštrukcia vlaku (s lokomotívou len na jednom konci) si vyžaduje, aby zakrivenie koľajníc nebolo nikde väčšie ako 1, čím myslíme to, že žiadne tri blízke body na koľajnici nebudú ležať na kružnici, ktorá má polomer menší ako 1. Takže koľajnice môžu napríklad pozostávať z "hladko nadväzujúcich" úsečiek a častí kružníc s polomerom aspoň 1. Jeden možný návrh koľajníc je na ilustračnom obrázku. Nájdite taký systém koľajníc, ktorý umožní vlaku urobiť v priebehu dňa čo najväčší počet návštev všetkých troch miest. Na celkovej dĺžke koľajníc nezáleží a na železničnej trati môžu byť mosty a výhybky, nie však zariadenie na otáčanie vlaku do opačného smeru.

  Táto úloha je samozrejme jednoduchá, avšak hľadanie najkratšej krivky s ohraničenou krivosťou prechádzajúcej zadanými bodmi je vo všeobecnosti veľmi ťažká úloha. (Upozorňujem, že riešením nášho problému, tak ako je formulovaný, nemusí byť jediná nepretínajúca sa sa krivka.) Keď Vás napadne nejaká iná úloha z tejto kategórie, budem rád, ak nám ju napíšete do komentárov.

Servítkový problém

Pozdravujem všetkých z Cambridge. Počas minulotýždňovej konferencie na Matematickom inštitúte Isaaca Newtona začal Andrei Bejan svoju prednášku nasledovným rekreačným problémom (autorom je Vladimir Letsko).

Štvorcovú servítku preložíme tak, aby zhyb prechádzal jej stredom, čím dostaneme nekonvexný deväťuholník (pozri obrázok). Aký je maximálny možný obsah tohto deväťuholníka?

Na večeri sme sa s kolegami o tomto probléme rozprávali a niektorí z nich bez dlhšieho premýšľania odhadli, že rigorózne riešenie je možné len pomocou nudných analytických metód hľadania extrémov funkcií. Nie je to však tak! Podarí sa niekomu z Vás nájsť "some beautiful solution"?

Náhodný rez kocky

Zvolíme náhodne rovinu prechádzajúcu ťažiskom kocky ABCDEFGH.  S akou pravdepodobnosťou bude rez kocky ABCDEFGH touto rovinou šesťuholník?

Predpokladáme, že rovinu zo zadania volíme "rovnomerne" náhodne, čiže všetky orientácie tejto roviny sú rovnako pravdepodobné, alebo ešte presnejšie: jednotkový normálový vektor tejto roviny má rovnomerné rozdelenie na povrchu jednotkovej gule.

Poznámka 4.12.: Vídím, že táto úloha nikoho nezaujala, avšak ja osobne mám celkom radosť, že ma napadla. Na prvý pohľad sa totiž zdá ťažká, no v skutočnosti sa dá pomocou istých trikov z teórie pravdepodobnosti vyriešiť na niekoľko riadkov.

Tri trojuholníky

Problémy optimálneho navrhovania experimentov, čo je moja hlavná oblasť výskumu, sú prekvapivo pestré, pretože zasahujú do takmer všetkých matematických disciplín: od štatistiky a pravdepodobnosti, cez kombinatoriku, teóriu grafov, analýzu, lineárnu algebru, teóriu matíc, až po numerickú matematiku. Dnes sa mi pri písaní článku z tejto oblasti dokonca vyskytlo jednoduché tvrdenie z klasickej rovinnej geometrie; formulujme si ho ako úlohu.

Majme päť priamok p₁, p₂, q₁, q₂, q₃, ako je znázornené na obrázku, pričom priamky q₁, q₂, q₃ sú rovnobežné. Označme ako A_ij prienik priamok p_i a q_j. Dokážte, že súčet obsahov trojuholníkov A₁₁A₁₂A₂₃ a A₁₂A₁₃A₂₁ je rovný obsahu trojuholníka A₁₁A₁₃A₂₂.

Konvexné smery

Nech f je reálna funkcia definovaná na množine všetkých dvojíc reálnych čísiel. Smerom nazveme každý vektor (u,v) jednotkovej dĺžky.  Budeme hovoriť, že funkcia f je konvexná v smere (u,v), ak pre každý bod (a,b) je konvexnou funkcia priradzujúca číslu α číslo f(a+αu,b+αv). Je zrejmé, že ak je funkcia f konvexná vo všetkých smeroch, tak je sama konvexná. Konvexnosť v jednom smere však samozrejme nestačí; napríklad nekonvexná funkcia f(x,y)=x²+y³ je konvexná v smere (1,0):

Stačí na zabezpečenie konvexnosti funkcie f konvexnosť v dvoch rôznych smeroch? V troch? ...

Aké je maximálne prirodzené číslo n, pre ktoré existuje nekonvexná reálna funkcia f  dvoch reálnych premenných, ktorá je konvexná v n rôznych smeroch (u₁,v₁), ... ,(u_n,v_n)?

Hlavolam z výstavy

Dnes som sa v rámci nedeľného oddychu vybral s manželkou a dcérkou do Slovenského národného múzea na výstavu "Matematika pre potešenie". Aj keď na prvý pohľad pôsobí táto výstavka pomerne chudobne, dá na nej celkom dobre zabaviť, čo platí dvojnásobne, ak máte so sebou dieťa :). Väčšina exponátov je založená na dobre známych princípoch, napríklad Galtonova skrinka, Buffonova ihla, Kreslenie grafu jedným ťahom, Möbiusov list, Tangram a podobne. Mňa najviac zaujalo vedro s mydlovou vodou, do ktorého bolo možné ponárať drôtené modely telies (napríklad kocka, pravidelný simplex, štvorboký ihlan) a sledovať tvar vzniknutých membrán, podobne ako v jednom našom staršom príspevku.

Výstavka obsahuje aj niekoľko hlavolamov, z ktorých sa mi jeden nepodarilo vyriešiť, hoci som nad ním strávil možno aj štvrť hodiny. (Trochu ma to rozladilo, pretože riešenie je určite veľmi jednoduché. :) Vy však možno budete úspešnejší ...

Poskladajte štvorec rozmerov 6x6 z ôsmich kúskov znázornených na nasledovnom obrázku.