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

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

Dva trojuholníky a tri štvorce

Po dlhšom čase som pre Vás vymyslel dve nové úlohy; keďže je leto, tak rekreačné a navyše také, ktoré je možné riešiť skoro všade. Stačí papier a ceruzka, alebo piesok a prst. :)

Je možné, aby dva trojuhoníky vytvorili útvar, ktorý celkovo obsahuje viac ako 8 rôznych trojuholníkov? Je možné, aby tri štvorce vytvorili útvar, ktorý celkovo obsahuje viac ako 7 rôznych štvorcov?

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.

Ajkina úloha

Moja doktorandka Ajka Bachratá mi včera zadala takúto domácu úlohu:

Vieme, že v istej skupine 1000 ľudí je aritmetický priemer IQ presne 100 a rozptyl je presne 900. Aký je maximálny možný počet ľudí v tejto skupine, ktorí majú IQ aspoň 150?

Ako svedomitý školiteľ som si svoju domácu úlohu vyriešil a keďže sa mi celkom páčila, rozhodol som sa, že sa o ňu podelím aj s Vami. Riešenie si nevyžaduje žiadnu náročnú matematiku, no súčasne nie je úplne priamočiare.

Poznámka: V našej úlohe nie je úplne jednoznačne povedané čo sa myslí pod pojmom "rozptyl". Keď si pozrieme príslušnú stránku wikipedie, tak zistíme, že do úvahy prichádzajú dve mierne odlišné definície: "vychýlený výberový rozptyl" a "nevychýlený výberový rozptyl". Ak by mal štatistik len súbor reálnych dát

y₁,y₂,...,y₁₀₀₀

bez znalosti presnej strednej hodnoty rozdelenia, z ktorého dáta pochádzajú, skoro určite by použil "nevychýlený výberový rozptyl". Avšak v našom príklade sa dohodnime, že kvôli jednoduchosti riešenia budeme pod pojmom "rozptyl" uvažovať "vychýlený výberový rozptyl", čiže aritmetický priemer čísiel

(y₁-100)²,(y₂-100)²,..., (y₁₀₀₀-100)².

Ak by sme náhodne vybrali 1000 ľudí z populácie, tak ich priemerné IQ bude skutočne okolo 100, ale výberový rozptyl bude oveľa menší ako 900 (pre štandardizované testy bude približne 225). Skupina zo zadania by musela byť teda veľmi zvláštna...

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.

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?

Nemožné?

Použitím cifier 1, 2, 3, ..., 9 (každú najviac raz) a operácii plus, mínus, krát, deleno, druhá odmocnina, umocňovanie, dvojkový logaritmus a zátvoriek napíšte ľubovoľné prirodzené číslo.

To je zadanie úlohy, ktoré mi pred pár dňami poslal Ondrej Budáč. Vzhľadom na to, že na prvý (aj druhý, aj tretí...) pohľad vzbudzuje úloha dojem neriešiteľnosti, uvediem tiež vlastné, trochu podrobnejšie, "informaticky ladené" znenie:

Nájdite spôsob ako konštruovať výrazy v₁, v₂, ... (v nejakom hypotetickom programovacom jazyku, ktorý počíta úplne presne s reálnymi číslami a má neobmedzenú dĺžku výrazov) také, že hodnota výrazu v_i je i. Každý z výrazov v_i môže obsahovať maximálne raz každú z cifier 1,2,..,9 a ľubovoľnekrát operátory +,-,*,/,^, funkcie sqrt,log2 a zátvorky (,). (Funkcia sqrt počíta druhú odmocninu a log2 dvojkový logaritmus.) Cifra 0 ani žiadne iné operátory a funkcie (ani premenné a konštanty) nie sú dovolené.

Ja som sa s týmto problémom trápil najprv asi pol hodiny, ale po dlhšej pauze ma napadlo riešenie už veľmi rýchlo. Naozaj to ide, nie je v tom žiadny chyták!

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.

Päť rovnakých cifier

Pre každú cifru c=1,...,9 nájdite matematický výraz, ktorého výsledná hodnota je 100, pričom treba dodržať tieto podmienky: Daný výraz musí obsahovať práve 5 cifier c, ale žiadnu inú cifru. Okrem týchto piatich cifier sa v ňom môžu vyskytovať štandardné aritmetické operátory (+,-,*,/) symbol faktoriálu (!), umocňovania (^), druhej odmocniny a zátvorky. Napríklad pre cifru 1 platí 111-11=100 a pre cifru 2 máme ((22-2)/2)^2=100.

Týmto oddychovým problémom nás na Probastate pobavil Guillaume Sagnol. Postupne sme našli riešenia pre všetky cifry okrem 7 a 8. Túto úlohu údajne kedysi publikoval istý francúzsky časopis a riešenie pre sedmičku sa nepodarilo nájsť žiadnemu z tisícov čitateľov. Takže držím palce...

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

Tri sochy

Kto nám do komentárov ako prvý napíše správne riešenie nasledovnej úlohy, dostane odo mňa knihu "Professor Stewart's Cabinet of Mathematical Curiosities" od Iana Stewarta (to aby som Vás motivoval túto úlohu aspoň dočítať do konca). Zadanie pochádza od Braňa Novotného (ďakujeme) a sponzorom tejto súťaže je, hoci o tom nevie, Thomas Klein (tiež ďakujeme; keď ma bol navštíviť, doniesol mi knižku, ktorú už vlastním :).

  Na ceste za pokladom je chrám, z ktorého vedú dve cesty - vľavo a vpravo. Jedna vedie k pokladu a jedna do záhuby. V chráme sú tri sochy. Jedna vždy hovorí pravdu, jedna vždy klame (hovorí nepravdu - tj. nesnaží sa zavádzať), a jedna odpovedá náhodne.

  O sochy sa starajú dvojičky, ktoré môžu položiť sochám dve otázky denne, vždy sa musí pýtať práve jeden z nich práve jednej sochy a tá odpovie podľa svojej prirodzenosti, ale keďže sú to iba sochy, tak zvládnu iba A a O, jedno znamená áno, druhé nie. Sochy majú dosť informácií: tj. rozoznajú bratov, vedia ktoré dvere sú správne, majú rozumný prehľad o svojom okolí a ak sa ich niekto spýta otázku, na ktorú nevedia korektne odpovedať A, alebo O, tak odpovedia náhodne.

  Hľadačovi pokladu vysvetlia bratia pravidlá a za dostatočnú odmenu sú ochotní spýtať sa sôch dve pútnikove otázky a to tak, že (hľadačom) vybraný brat otázku presne zopakuje vybranej soche a vypočuje si odpoveď a tú povie hľadačovi, lenže starší brat odpoveď vždy zmení na opačnú. Samozrejme bratia neprezradia ktorý z nich je starší, ktoré z A a O je áno a ktoré nie a sochu, ktorej sa budú pýtať, môže hľadač určiť iba ako vľavo, vpravo a v strede.

Aké dve otázky sa má hľadač spýtať, aby sa dozvedel ktorá cesta vedie k pokladu?

Šesť ostrovanov

  Pred pár dňami som si konečne našiel čas na moju novú knižku Satan, Cantor a nekonečno od Raymonda Smullyana. Veľmi Vám ju odporúčam, ak sa Vám zdá, že Váš mozgový sval chátra. (Pripúšťam, že takéto pocity sú na matfyze počas skúškového obdobia dosť zriedkavé.) Ako veľmi ľahkú rozcvičku na príklady v knižke som pre Vás poprivymyslel túto úlohu:

  Minule som bol na dovolenke na ostrove s veľmi zvláštnymi obyvateľmi. Delia sa na pravdovravných, ktorí hovoria vždy len pravdu, a klamárov, ktorí výlučne klamú. Všetci ostrovania o sebe vedia, kto z nich je pravdovravný a kto z nich je klamár, takže medzi sebou si celkom dobre rozumejú. No cudzinca, ako som ja, dokážu riadne pomýliť.
  Na prechádzke týmto ostrovom som stretol skupinku šiestich ostrovanov, očividne dobrých priateľov. Náhodne som si vybral jedného z nich a dal som sa s ním do reči. Počas rozhovoru vyslovil o svojich priateľoch v skupinke nasledovné tri vety: Priateľ s klobúkom a tmavomodrými nohavicami je klamár. Priateľ v tmavohnedých nohaviciach je klamár. Priateľ v tmavosivých nohaviciach je klamár.
  Poďakoval som mu za rozhovor a dal som sa do reči s jediným spomedzi týchto šiestich ostrovanov, ktorý mal klobúk. Tento ostrovan sa tiež rozhovoril o svojich piatich priateľoch a postupne vyslovil tieto tri vety: Priateľ vo svetlooranžovej košeli je klamár. Priateľ vo svetložltej košeli je klamár. Priateľ vo svetloružovej košeli je klamár.
  Bohužiaľ, keďže som farboslepý, veľa som sa od týchto dvoch ostrovanov nedozvedel. Viem určiť aspoň to, koľko je v tejto skupinke ostrovanov klamárov?

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.

How long will it take Marie to saw a board into 3 pieces?

K napísaniu tejto rekreačnej úlohy ma inšpiroval príspevok Math teacher fail na blogu TYWKIWDBI (credits: Lenka Filová). Za normálnych okolností, t.j. ak pod slovom "board" rozumieme obdĺžnikovú dosku, je odpoveď učiteľa nesprávna. Ale... :)

Márii trvá 1 minútu, kým rozpíli drevený útvar konštantnej hrúbky na 2 rovnaké časti. Ako dlho bude trvať Márii, kým rozpíli tento útvar na 3 rovnaké časti? Aké sú všetky možné "správne" odpovede v závislosti od tvaru tohto útvaru?

Uvažujeme len také útvary, ktoré je možné rozpíliť na dve aj na tri rovnaké časti a tiež predpokladáme, že Mária píli daný útvar najkratším možným rezom (alebo najkratším možným súčtom dĺžok rezov), po ktorom sa rozpadne na dve, resp. tri rovnaké časti. Na to, aby sme dve časti považovali za "rovnaké", nestačí, aby boli "zrkadlovo rovnaké" (povedzme, že strany dosky sú ofarbené rôznymi farbami, čo umožní rozlíšiť zrkadlovú podobnosť od skutočnej zhodnosti).

Ekvidištantné permutácie

  Nech σ=(σ₁,σ₂,...,σ_n) je permutácia čísiel 1,2,...,n. Ak v rovine postupne spojíme body (σ₁,σ₂), (σ₂,σ₃),...,(σ_n-1,σ_n), (σ_n,σ₁) a (σ₁,σ₂), dostaneme euklidovský graf, ktorý permutáciu σ plne charakterizuje. Na nasledovnom obrázku sú znázornené grafy permutácií (1,3,4,2) a (1,2,5,6,3,4).

Všimnite si, že grafy na obrázkoch majú jednu zaujímavú vlastnosť: rovnakú dĺžku všetkých hrán. Otázka znie:

Existuje permutácia čísiel 1,2,...,n, kde n>6, ktorej graf má všetky hrany rovnakej dĺžky?