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

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!

Timothyho úloha

V úvodnej časti knihy Princeton Companion to Mathematics uviedol Timothy Gowers ako príklad kombinatorickej úlohy nasledovné zadanie:

Koľko existuje nula-jednotkových matíc rozmeru n × n, ktoré majú v každom riadku aj v každom stĺpci maximálne dve jednotky?

Timothy sa neunúva dať na túto otázku odpoveď (zrejme je to pre neho príliš triviálne), ale normálnych smrteľníkov ako my môže takáto úloha celkom potrápiť. Priznám sa, že som nad ňou uvažoval skoro pol hodiny a nepodarilo sa mi odvodiť všeobecný vzorček; niekedy to človeku skrátka nezapne. Ale Vy budete možno úspešnejší...

Ako hrať proti telepatovi

Koncom minulého týždňa mi poslal peknú úlohu môj bývalý študent Lukáš Poláček. Ďakujem(e)! Pre náš blog ju formulujem nasledovne:

Hráči A a B budú hrať takúto hru: Obaja pošlú rozhodcovi obálku s lístkom, na ktorom je číslo od 1 po 16; je len na ich vlastnom rozhodnutí akým spôsobom toto číslo hráči zvolia. Po obdržaní oboch obálok ich rozhodca otvorí a ak sa budú čísla na lístkoch líšiť práve o 1, tak vyhráva hráč A, inak vyhráva hráč B. Problém je v tom, že hráč B je telepat a čokoľvek vie hráč A, vie ihneď aj hráč B. Hráč A sa preto rozhodol, že bude svoje číslo voliť nasledovne: Najprv si pripraví viacero lístkov, na ktoré napíše čísla v rozmedzí od 1 do 16. Z týchto lístkov potom náhodne vyberie jeden, bez pozretia ho vloží do obálky a pošle ho rozhodcovi. Poraďte hráčovi A koľko lístkov si má pripraviť a aké čísla má na ne napísať, aby maximalizoval svoju šancu na výhru.

(Pochopiteľne, ilustračný obrázok vľavo hore nemusí korešpondovať s najlepším riešením.)

Päť klubov

Predchádzajúcu úlohu sme zatiaľ vyriešili pre n ktoré je nanajvýš štyri a keďže všeobecné riešenie sa zdá byť pomerne komplikované, pokúsme sa rozlúsknuť aspoň špeciálny prípad n=5. Nasledovnú úlohu formulujem bez použitia pravdepodobnosti, len pomocou elementárnych pojmov.

V istom meste existuje päť klubov: literárny, golfový, šachový, rybársky a bowlingový. Tieto kluby majú spolu m členov, pričom každý z týchto klubov má presne m/2 členov (vieme, že m je párne, ale inak o m nevieme nič). Dvojice klubov pravidelne organizujú spoločné stretnutia, na ktoré pozvú všetkých tých ľudí, ktorí sú členmi súčasne oboch klubov. Napríklad býva stretnutie ľudí, ktorí sú súčasne členmi rybárskeho aj šachového klubu, býva tiež stretnutie ľudí, ktorí sú súčasne členmi literárneho aj bowlingového klubu a tak ďalej (spolu 10 druhov stretnutí). Každého z týchto stretnutí sa vždy zúčastnia všetci pozvaní hostia. Tvrdíme, že na niektoré stretnutie určite príde aspoň p percent z daných m ľudí. Aké je maximálne p, označme ho p₅, pre ktoré je toto tvrdenie zaručene pravdivé?

Z komentáru k predchádzajúcej úlohe vieme, že p₅ je aspoň 15% a nie je ťažké sa presvedčiť, že p₅ je najviac 25%. (Viete prečo?) Kto nájde hodnotu p₅ presne (a presvedčivo túto hodnotu zdôvodní), má u mňa čokoládu. Nie je to vôbec až také ľahké, ale ani nemožné.

Binárny kruh

Nasledovný problém je modifikáciou istej úlohy, ktorú vymyslel môj bývalý spolupracovník a v súčasnosti jeden z najbystrejších dôchodcov v širokom okolí, docent Juraj Pavlásek. O tejto úlohe sa neskôr ukázalo, že ju ľudia riešili už pred desiatkami rokov (samozrejme pod iným názvom), ale to nám nebráni vyskúšať si na nej naše kombinatorické, prípadne programátorské schopnosti.

Binárnym kruhom stupňa m nazveme reťazec 2^m núl a jednotiek zapísaný do kruhu, v ktorom je každý podreťazec dĺžky m iný (všetky podreťazce čítame v smere hodinových ručičiek) alebo, ekvivalentne, ktorý ako podreťazce obsahuje všetky binárne postupnosti dĺžky m. Nájdite binárny kruh pre čo najväčšie m.

Na obrázku je zakreslený jeden z viacerých možných binárnych kruhov stupňa 3, pretože ako podreťazce obsahuje samé rôzne trojice binárnych cifier: 111, 110, 101, 010, 100, 000, 001 a 011 (t.j. obsahuje všetky možné trojice binárnych cifier).

PS: Ak by som sa už najbližšie dni na blogu neozval, tak Vám všetkým želám príjemné veľkonočné sviatky.

Poznámka 14.4.: Pre tých, ktorých úloha zaujala, ale nevedia ako ju riešiť, mám pomôcku: hoci sa to možno nezdá, binárnych kruhov je pomerne veľa a pre stupne 4, prípadne aj 5, je možné nájsť aspoň jeden binárny kruh na počítači skúšaním náhodne vygenerovaných binárnych očíslovaní.

Biliardové gule (súťažná úloha č.12)

Poslednú, dvanástu úlohu do našej súťaže vymyslel môj študent a súčasne spolupracovník Vladimír Lacko:

Na biliardovom stole v dokonalom svete matematických modelov máme položené tri gule A, B a C, všetky s polomerom r. Stredy gulí B a C sú navzájom vzdialené d cm a stred gule A má vzdialenosť h cm od priamky p spájajúcej stredy gulí B a C (pozri obrázok). Do gule A udrieme tágom tak, aby sa pohybovala rovnobežne s priamkou p. Aká môže byť maximálna vzdialenosť h, aby guľa A odrazila guľu B tak, že guľa B (bez odrazu od mantinela biliardového stola) následne narazí do gule C?

Onedlho napíšem príspevok ohľadom spôsobu určenia víťaza súťaže; tipnúť si víťaza netrúfam, pretože sme na moje veľké potešenie dostali množstvo naozaj super úloh. :-)

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

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

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.

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?

Buffonov rez sféry II

Keďže Ruziklan už predchádzajúcu úlohu vyriešil, môžem formulovať zamýšľané zťaženie. Kto príde ako prvý so správnym riešením, ten má u mňa fľašu whisky. (A to je už iné kafe ako pivo, nie?)



Na povrchu jednotkovej sféry S máme tri body A,B,C, pričom vzdialenosť AB označme c, vzdialenosť AC označme b a vzdialenosť BC označme a (samozrejme, vzdialenosti opäť berieme po povrchu sféry). Sféru S náhodne rozpolíme rovinným rezom na dve rovnako veľké hemisféry. V závislosti od vzdialeností a,b,c, aká je pravdepodobnosť, že po vykonaní tohto rezu sa budú všetky tri body nachádzať na spoločnej hemisfére?

Buffonov rez sféry

Dnes som pre Vás vymyslel trochu ťažšiu úlohu, ktorá pripomína problém o Buffonovej ihle. Riešenie je celkom pekné a naviac táto úloha je môj vlastný nápad. Doslova sa čudujem, ako je možné, že som sa s ňou ešte nestretol v žiadnej z tých desiatok kníh z teórie pravdepodobnosti, ktoré používam. Kto príde ako prvý so správnym riešením (aj s odôvodnením; napíšte ho do komentárov, alebo mi pošlite mail), ten má u mňa pivo. Alebo aj tri.


Nech S je jednotková sféra, čím rozumieme povrch trojrozmernej gule s polomerom 1. Na S sú vyznačené dva body A a B, ktorých vzdialenosť je h. (Vzdialenosť počítame po povrchu sféry S, t.j. h je dĺžka sférickej úsečky AB.) Sféru S náhodne rozpolíme rovinným rezom na dve rovnako veľké hemisféry. Aká je pravdepodobnosť, že body A a B sa po vykonaní tohto rezu budú nachádzať na spoločnej hemisfére?

Ako sťažiť odpisovanie

Dajú sa každému zo siedmich študentov priradiť na riešenie práve tri zo siedmich rôznych príkladov tak, aby každý príklad dostali práve traja študenti a aby žiadna dvojica študentov nemala viac než jeden spoločný príklad?

Valivá elipsa

Rovnako ako v úlohe "Valivá úsečka", predstavme si, že sa malá kružnica "valí" po vnútornej strane veľkej kružnice s dvojnásobným polomerom. Červenou farbou označme pevne zvolený bod na malej kružnici a modrou farbou pevne zvolený bod na úsečke spájajúcej tento bod so stredom malej kružnice. Je pravda, že modrý bod opisuje matematicky presnú elipsu? (Kliknutím na obrázok sa spustí animácia.)

Pytagorova pavučina

Na obrázku vľavo sú čiernymi bodkami zaznačené všetky usporiadané dvojice (x,y) prirodzených čísel menších ako 4000, pre ktoré je odmocnina z x²+y² celé číslo, čiže x a y sú celočíselné odvesny pravouhlých trojuholníkov s celočíselnou preponou. Vidíme, že tieto body nie sú rozmiestnené úplne chaoticky, ale majú určitú štruktúru.

Vedeli by ste vysvetliť pôvod "priamok", t.j. množín bodov (x,y), pre ktoré y=αx? Aké sú hodnoty konštanty α pre priamky, ktoré sú na obrázku najvýraznejšie? Menej viditeľná, ale pri pozornom pohľade nespochybniteľná je aj štruktúra rôznych "oblúkov". Vedeli by ste vysvetliť aj pôvod týchto oblúkov?

Pod vysvetlením nejakej "vizuálnej štruktúry" rozumiem matematické tvrdenie, na základe ktorého by matematik mohol vznik tejto štruktúry predvídať aj bez nakreslenia obrázku.

Poznámka: Prvé dve otázky sú samozrejme jednoduché, avšak ako vysvetliť pôvod oblúkov ma počas tých pár minút, ktoré som venoval rozmýšľaniu nad týmto problémom, nenapadlo. Ale Vy budete možno bystrejší. Alebo niečo nájdete na webe pod hlavičkou "Pythagorean triples".

Neporiadny cestujúci

Do lietadla, ktoré má 100 miest, nastupuje 100 cestujúcich s miestenkami, postupne od cestujúceho s miestenkou 1 až po cestujúceho s miestenkou 100. Prvý cestujúci si sadne úplne náhodne na akékoľvek zo sedadiel (bez ohľadu na to, že má miestenku 1). Každý ďalší cestujúci už dodržuje nasledovné pravidlo: Ak je miesto, na ktoré má miestenku, voľné, tak sa naň posadí. Ak je jeho miesto už obsadené, vyberie si náhodne jedno z voľných miest. Aká je pravdepodobnosť, že posledný, stý cestujúci bude sedieť na svojom mieste?

Toto je pomerne známy problém, v ktorom je ľahké uhádnuť, ale pomerne ťažké precízne zdôvodniť riešenie. Inak množstvo podobných zábavných obrázkov ako ten vľavo hore nájdete na http://www.sciencecartoonsplus.com/.