Q.E.D.

Opica

2012-02-07T10:49:00.001+01:00

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. Spomínaná opica je šimpanz.

Veže

2012-01-25T23:52:00.000+01:00

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

2012-01-20T10:38:00.000+01:00

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

2012-01-05T17:35:00.005+01:00

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

2012-01-04T15:03:00.001+01:00

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

2011-12-18T21:09:00.001+01:00

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

2011-09-23T22:44:00.003+02:00

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

2011-09-07T00:28:00.004+02:00

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

2011-08-25T22:14:00.006+02:00

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ť s "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

2011-08-07T19:53:00.001+02:00

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

2011-07-27T23:51:00.003+02:00

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

Moja habilitačná prednáška

2011-04-28T11:56:00.006+02:00

V pondelok 2.5. o 14:00 budem mať v C-čku na matfyze habilitačnú prednášku a po krátkej prestávke obhajobu habilitačnej práce. Budem veľmi rád, keď si ma prídete vypočuť!

Téma habilitačnej prednášky je "Pátranie po informáciách skrytých v mnohorozmerných dátach", čiže hovoriť budem o mnohorozmerných štatistických metódach. Ukážem zjednocujúci pohľad na viacero zdanlivo nesúvisiacich metód a niektoré z nich vysvetlím podrobnejšie (metódu hlavných komponentov, analýzu zhlukov, klasifikačné metódy), avšak skôr intuitívne a s viacerými obrázkami. V tejto téme nie som nejaký extra expert a navyše je táto téma extrémne široká a pomerne málo "matematická" (radšej by som bol, keby mi boli vybrali napríklad stochastické simulačné metódy), ale verím, že Vás aj napriek tomu dokážem zaujať.
V obhajobe habilitačnej práce veľmi stručne spomeniem moje kľúčové výsledky z oblasti optimálneho navrhovania experimentov. Prednáška aj obhajoba bude po anglicky.

2.5.: Ďakujem Vám všetkým, ktorí ste si ma prišli vypočuť. Pre záujemcov dávam k dispozícii moje slidy (aj keď bez slovného komentára to je veľmi nekompletné a možno aj ťažko zrozumiteľné).

Ak by ste na týchto slidoch našli nejaké chyby, dajte mi o nich vedieť, ja ich opravím a budem sa tváriť, že to bolo od začiatku dobre :)

Ťažisko rezu

2011-02-25T11:02:00.004+01:00

Metóda "alias" používaná na simulačné generovanie diskrétnych náhodných premenných sa opiera o vetu, ktorej špeciálny prípad je možné pekne geometricky interpretovať:

Akýkoľvek bod C vo vnútri štvorstena je ťažiskom nejakého trojuholníka, ktorého vrcholy ležia na hranách tohto štvorstena.

Vedeli by ste túto vetu dokázať? Napadajú Vás nejaké zovšeobecnenia tejto vety?

(Ospravedlňujem sa všetkým riešiteľom, ktorí sa trápili s pôvodnou nesprávnou formuláciou vety.)

Tri sochy

2011-02-05T17:29:00.002+01:00

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

2011-01-16T00:12:00.010+01:00

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?

Tanec molekúl

2010-12-12T19:38:00.002+01:00

Keď som na Akadémii Trojstenu spomínal súvis Gaussovej krivky a objemov rezov mnohorozmerných kociek, napadlo ma, že by som rád vedel ako asi vyzerá "typická" množina ich vrcholov v dvojrozmernej projekcii. Včera večer som si teda v rámci oddychu napísal jednoduchý program, ktorý zobrazuje dvojrozmerné súradnice vrcholov pomaly rotujúcej mnohorozmernej kocky s farbami určenými súradnicami v ďalších troch rozmeroch.

Najprv som si myslel, že pre Vás vyrobím pomocou môjho programíku video, ale to by bolo nutne krátke a nemenné. Rozhodol som sa preto dať Vám k dispozícii priamo zdrojový kód programu; stačí, keď si ho prekopírujete do R-ka a spustíte. Takto sa s ním môžete zabávať, vylepšiť ho podľa vlastných predstáv a pri sledovaní komplexného "tanca molekúl" možno aj trochu premýšľať... :)

Prednáška na Akadémii Trojstenu

2010-12-08T13:36:00.006+01:00

Ďakujem všetkým, ktorí ste sa zúčastnili mojej prednášky na Akadémii Trojstenu! Slidy k mojej tohtoročnej prednáške nájdete tu a slidy k mojej prednáške v roku 2007 nájdete tu. Boužiaľ, z prednášky nie je záznam a slidy sú len veľmi stručným náznakom toho o čom som rozprával, ale nevadí. Ak máte akékoľvek otázky, rád Vám na ne odpoviem.

Pôvodný text: Tento piatok (10.12.2010) bude na našej fakulte Akadémia Trojstenu; program si môžete pozrieť tu. Ak ste si klikli na odkaz, asi ste si všimli, že jednu prednášku mám ja. Trochu ma mrzí, že paralelne bude mať veľmi atraktívnu prezentáciu misof, pretože tú som si chcel pozrieť aj ja a to mi asi teraz nedovolia :). Predpokladám tiež, že o moju prednášku o Gaussovej krivke až taký veľký záujem nebude, takže ak ste sa aj na toto podujatie neregistrovali, ku mne do B-čka sa o 11:15 určite zmestíte...

Náhodný rez kocky

2010-12-02T23:26:00.006+01:00

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

2010-11-10T22:55:00.005+01:00

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

Koľko matematikov, toľko dôkazov

2010-11-02T19:21:00.002+01:00

Nasledovná jednoduchá, ale celkom pekná dôkazová úloha sa nám objavila pri písaní článku o optimálnom navrhovaní experimentov pre náhodné procesy. Spomenuli sme ju viacerým kolegom a každý prišiel po nejakom čase so svojim vlastným dôkazom. Som zvedavý, koľko rôznych dôkazov sa podarí nájsť Vám.

Ukážte, že ak hladká funkcia f:R→R spĺňa rovnicu

pre všetky reálne čísla x a všetky kladné reálne čísla δ, potom je f kvadratická funkcia.

Kvadratickou funkciu rozumieme aj lineárnu a konštantnú funkciu (s niektorými koeficientmi nulovými). Ako obvykle, symbol f ' označuje deriváciu funkcie f.

Konvexné smery II

2010-10-30T11:49:00.007+02:00

V predchádzajúcom príspevku sme zistili, že existujú funkcie dvoch premenných, ktoré samotné nie sú konvexné, no napriek tomu sú konvexné v nekonečne veľa smeroch. Pripomeňme, že konvexnosťou funkcie f v smere jednotkového vektora (u,v) myslíme konvexnosť rezov funkcie f po všetkých priamkach rovnobežných s vektorom (u,v). Takou je napríklad Ivanova funkcia f(x,y)=x²-y²:

Takýchto príkladov existuje veľa, avšak každý, ktorý ma napadol, má "podobné" smery konvexnosti. V prípade Ivanovej funkcie sú všetky smery koncentrované do dvoch protiľahlých kvadrantov roviny. Zaujímala by ma teda odpoveď na otázku, či môže existovať nekonvexná funkcia, ktorá je konvexná v aspoň troch "veľmi nepodobných" smeroch:

Existuje nekonvexná reálna funkcia dvoch reálnych premenných, ktorá je konvexná v smeroch vrcholov rovnostranného trojuholníka s ťažiskom v bode (0,0), čiže v smeroch troch jednotkových vektorov, ktorých vzájomné skalárne súčiny sú -1/2?

Nepresnejšia, ale ľudskejšia formulácia úlohy :) Obyvatelia istej nekonečne rozľahlej krajiny majú len tri svetové strany - A,B,C, a to v smere šípok na ilustratívnom obrázku vyššie. Táto krajina má nasledovnú zaujímavú vlastnosť: Ak stoja dvaja obyvatelia voči sebe presne v smere niektorej svetovej strany, tak na seba vidia. Súčasne však existuje také postavenie dvoch obyvateľov tejto krajiny, pri ktorom na seba nevidia; prekáža im vo výhľade kopček. Môže, alebo nemôže existovať taká krajina?

Uvedomte si, že Ivanova funkcia ukazuje príklad takej krajiny v prípade, že obyvatelia majú štyri svetové strany, tak ako u nás. Ďalší príspevok už bude oddychovejší. :)

Konvexné smery

2010-10-28T22:40:00.004+02:00

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

2010-10-17T18:06:00.004+02:00

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?

2010-10-10T20:00:00.011+02:00

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

Kedy sa obsah rovná dĺžke

2010-08-14T12:16:00.010+02:00

Nasledovná úloha ma napadla keď sme dnes s Vladom písali zovšeobecnenie nášho článku o generovaní náhodných bodov na mnohorozmerných sférach.

Množinu M v rovine nazývame hviezdicovo konvexnou, ak v nej existuje "centrálny" bod O, z ktorého je "vidieť" všetky body množiny M, čiže ak pre každý bod A množiny M platí, že úsečka OA je celá v množine M. Pre jednoduchosť budeme uvažovať len tie hviezdicovo konvexné množiny, ktoré sú ohraničené, a pre ktoré je centrálnym bodom bod O=(0,0).

Výsekom hviezdicovej množiny M určeným bodmi X,Y ležiacimi na hranici M nazveme útvar ohraničený úsečkami OX, OY a krivkou, ktorá tvorí hranicu množiny M medzi bodmi X a Y. (Na tomto mieste a aj ďalej predpokladáme, že sa pohybujeme od bodu X k bodu Y po hranici množiny M v "smere hodinových ručičiek"). Na ilustračnom obrázku je množina M modrá a výsek určený bodmi X,Y je červený:

Všimnime si, že kruh v rovine so stredom v O a polomerom 2 má nasledovnú vlastnosť: obsah výseku určeného hraničnými bodmi X,Y je presne rovný vzdialenosti bodov X a Y po hraničnej kružnici.

Otázka znie: Existujú aj iné hviezdicovo konvexné množiny M s vlastnosťou, že obsah výseku množiny M určeného hraničnými bodmi X a Y je rovný vzdialenosti bodov X,Y po hranici množiny M?

Poznámka: Nedefinovali sme síce presne, čo je to hranica množiny M a čo je to vzdialenosť hraničných bodov X,Y "po hranici", ale tieto pojmy by mali byť intuitívne dostatočne jasné na pochopenia jadra zadania, bez rozptyľovania sa exaktnými, no komplikovanými formálnymi definíciami.

16.8.: Riešenie úlohy nám do komentárov napísal Ivan. Stručne, množín s danou vlastnosťou je nekonečne veľa, napríklad ak dotyčnice ku hranici, všade tam, kde jednoznačné dotyčnice existujú, sú priamky vo vzdialenosti 2 od bodu O. Taká je aj nasledovná "hviezda" :)

Pochopiteľne, existuje mnoho ďalších otázok, ktoré by sme sa mohli spýtať, napríklad: 1) Je každá množina s uvedenou vlastnosťou prienikom a zjednotením systému polrovín určených priamkami vzdialenými o 2 od bodu O? 2) Aké množiny "s oblými hranicami", t.j. nie polygóny, majú túto vlastnosť? 3) Aké je zovšeobecnenie tejto úlohy do viacrozmerného priestoru?

Nočná pyramída o pravdepodobnosti a logike

2010-05-28T17:59:00.006+02:00

Zajtra (v sobotu 29.5.) o 22:30 budem spolu s profesorom Anatolijom Dvurečenskim hosťom relácie "Nočná pyramída" Slovenského rozhlasu. Takže ak máte čas, budem veľmi rád, keď si nás vypočujete.

Pred pár hodinami som dostal scenár a je skutočne zaujímavý. Základné témy sú "teória pravdepodobnosti", "vzťah medzi matematikou a logikou", "možné svety" a "náhoda a nutnosť". Trochu je problém v tom, že väčšina (predbežných) otázok má buď komplikované, alebo dosiaľ neznáme odpovede, prípadne na ne odpoveď asi vôbec ani neexistuje... Ale o to väčšia zábava bude na ne odpovedať, takže sa na to veľmi teším :)

30.5.: Kompletný záznam relácie vo formáte mp3 si môžete stiahnuť na tejto adrese. Veľmi rád Vám odpoviem na akékoľvek (ďalšie) otázky k téme.

Éter v štvorrozmernom priestore

2010-05-22T22:02:00.002+02:00

Minulý týždeň som konečne odovzdal habilitačnú prácu, odoslal som náš najnovší článok a navyše sa skončilo vyučovanie, takže sa opäť s radosťou vraciam k môjmu blogu :) Mali sme tu už viaceré úlohy z geometrie v rovine aj v priestore. Čo by ste ale povedali na úlohu z geometrie v hyperpriestore?

Predstavme si dvojrozmerných obyvateľov povrchu sférickej planéty, ktorá rotuje okolo svojej osi v nehybnom éteri. Títo obyvatelia síce nevedia vnímať tretí rozmer, ale pohyb povrchu svojej planéty voči éteru odmerať vedia. To znamená, že na istej do seba uzavretej priamke (z nášho pohľadu na rovníku planéty) pozorujú najvyššiu rýchlosť pohybu éteru a v dvoch špeciálnych bodoch (z nášho pohľadu na póloch) pozorujú nulovú rýchlosť pohybu éteru.

Moja otázka znie: Ak by náš trojrozmerný vesmír bol povrchom štvorrozmernej gule rotujúcej v nehybnom štvorrozmernom éteri a vedeli by sme odmerať relatívnu rýchlosť tohto éteru voči nám, ako by sme vnímali oblasti najrýchlejšieho pohybu éteru (čiže akýsi švorrozmerný rovník) a ako by sme vnímali oblasti nulovej rýchlosti pohybu éteru (čiže štvorrozmerné póly)?

Osobnosti slovenskej matematiky: Andrej Pázman (pozvánka na prednášku)

2010-04-22T07:19:00.000+02:00

(Po kliknutí na obrázok sa oznam zobrazí v plnom rozlíšení.)

Mnohí z nás si neuvedomujú, že viacerí slovenskí matematici sú medzinárodne uznávanými osobnosťami a ich výsledky sa stali v matematike pojmami. Rovnako ako národ by mal poznať svoju históriu, tak aj my, študenti matematiky a matematici ako takí, by sme mali poznať, čo svetu dala slovenská matematika.

Cyklus prednášok Osobnosti slovenskej matematiky je organizovaný študentmi Fakulty matematiky, fyziky a informatiky Univerzity Komenského v Bratislave. Jej cieľom je priblížiť študentom ako aj odbornej verejnosti najväčšie prínosy slovenských matematikov. Každá prednáška je zameraná na dielo jednej osobnosti slovenskej matematiky, ktorá prednášku aj vedie. Dôvodom takej to formy je možnosť týchto ľudí spoznať aj osobne. Prednášky majú populárnu formu a sú koncipované tak, aby im porozumeli aj študenti a širšia odborná verejnosť.

Študenti Fakulty matematiky, fyziky a informatiky UK

Ekvidištantné permutácie

2010-03-28T18:35:00.004+02:00

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?

Reťaze z mincí

2010-03-14T21:25:00.004+01:00

Pri príležitosti dňa čísla π som pre Vás vymyslel nasledovnú úlohu (tento krát pomerne jednoduchú :).

Na obrázkoch sú dve reťaze vytvorené z mincí. Ktorá z nich má väčší vnútorný obvod?

Pod vnútorným obvodom myslíme dĺžku hranice "mláčky", ktorá by vznikla, ak by sme medzi mince naliali vodu (samozrejme za predpokladu, že by tá voda pomedzi mince nepretiekla). Teším sa na Vaše riešenia.

Poznámka 16.3.: Túto úlohu je možné vyriešiť matematicky; nejde o skúšku Vášho vizuálneho odhadu.

Pozoruhodná potvora

2010-03-02T10:44:00.004+01:00

Matematické funkcie môžu mať veľmi komplikované vlastnosti, a to aj v prípade, keď sú definované jednoduchým predpisom. Včera mi pri riešení jedného príkladu vyskočila takáto pozoruhodná potvora:

kde λ je reálna konštanta. Čo všetko sa o nej dá povedať?

Po prvé si uvedomíme, že táto funkcia je dobre definovaná, pretože členy uvedeného nekonečného súčinu sú pre každé x od istého n v intervale (0,1), takže limita, ktorá určuje tento nekonečný súčin, existuje a je konečná. Tiež si hneď všimneme, že pre celé čísla x rôzne od nuly platí f(x)=0. Avšak prakticky akákoľvek ďalšia vlastnosť tejto funkcie je už netriviálna, ako naznačuje aj jej graf pre λ=1.5365:

Ak si niekto z Vás myslí, že je naozaj dobrý v matematickej analýze, môže sa pokúsiť zodpovedať napríklad nasledovné otázky:

Je hodnota f(x) nenulová pre každé kladné neceločíselné x?
Aká je množina tých hodnôt λ, pre ktoré je funkcia f ohraničená na celom R?
Je derivácia tejto funkcie nenulová v každom bode x=2^k, kde k je celé nezáporné číslo?

A ak sa niekomu z Vás podarí zodpovedať na všetky tri tieto otázky do týždňa (samozrejme s rigoróznym dôkazom), tak mu darujem svoj The Princeton Companion to Mathematics, lebo tak bude pravdepodobne v lepších rukách ;-)

Timothyho úloha

2010-02-15T15:32:00.004+01:00

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ší...

Food for thought 1/2010

2010-02-11T20:55:00.005+01:00

Diabolský diktátor

2010-02-05T18:26:00.001+01:00

Koľko výhier za sebou sa Vám podarí dosiahnuť v hre, ktorú si na Vás vymyslel diabolský diktátor? Akú stratégiu ste používali? (Na túto zaujímavú hru ma upozornila Erika Hönschová; ďakujem(e).)

Agátkina teória čísel

2010-02-03T19:41:00.002+01:00

Dnes som s dcérkou (4,5 r.) absolvoval nasledovný rozhovor.

Agátka: Ako sa volá najväčšie číslo?
Ja: Najväčšie číslo neexistuje.
Agátka: Ty tomu nerozumieš tata. Najväčšie číslo existuje.
Ja: Áno? A aké je veľké?
Agátka: Ako milión takýchto skríň popísaných číslami.
Ja: Hm. A čo ak by si toto číslo zvačšila o jedna?
Agátka: Tak by som predsa dostala najmenšie číslo.
Ja: Najmenšie číslo?
Agátka: Áno. Jednotku. Čísla musia byť do kruhu.
Ja. Aha. A ak by niekto mal toľko koruniek, koľko je to najvačšie číslo a ja by som mu dal ešte jednu korunku, tak by mal koľko koruniek? Jednu?
Agátka: Ale tata. Keby mal niekto toľko koruniek, tak by bol nimi úplne zasypaný a nemohol by si mu dať už žiadnu korunku...

Nedosiahnuteľné body

2010-02-02T23:08:00.003+01:00

Vo vnútri kruhu máme zakreslený bod A. Na hranici tohto kruhu zvolíme bod B, spojíme ho s bodom A úsečkou a stredom úsečky AB budeme kolmo viesť tetivu t. Uvažujme množinu tých bodov kruhu, ktorými tetiva t určite nemôže prechádzať, nech by sme B zvolili kdekoľvek na hranici kruhu. Čo všetko vieme o tejto množine bodov povedať?

Poznámka 3.2.: Úlohu už prakticky vyčerpávajúco vyriešil Peťo a to dokonca vo všeobecnej, mnohorozmernej verzii; viď jeho blog.

Zbierka úloh z pravdepodobnosti je na svete

2010-01-20T20:53:00.004+01:00

Po dlhom čase vymýšľania zadaní, počítania riešení, kontrol a editovania nám vyšla naša prvá kniha: Zbierka úloh zo základov teórie pravdepodobnosti. Hurá!

Zbierka obsahuje 519 úloh, z ktorých každá má uvedený aspoň číselný výsledok, a väčšina dokonca podrobný postup riešenia. Okrem rôznych príkladov na cvičenia, domáce úlohy a písomky, zaradili sme do nej aj viacero komplexnejších a zábavných úloh, napríklad klasiky ako Buffonovu ihlu a Buffonovo vlákno, úlohu o ruinovaní, Monty Hall problem, problém zberateľa kupónov, Banachove zápalky, dvojrozmernú náhodnú prechádzku a podobne, ale aj vlastné úlohy, ako napríklad úlohu o kurzoch stávkových kancelárií, nové úlohy o lámaní úsečiek, problémy počtov cyklov v náhodných permutáciách, úlohy týkajúce sa rozdelenia IQ v populácii a mnohé iné. Dúfame, že zaujmú.

Bohužiaľ, väzba knihy je dosť nevhodne zvolená a nekvalitne urobená (kniha sa dá len veľmi ťažko úplne roztvoriť a nebude sa z nej dať dobre kopírovať), ale za to už my, autori, nemôžeme. Každopádne, zbierka sa čítať dá a teraz nás už čaká len rozhodovanie, ako budeme našu zbierku rozdeľovať medzi ľudí a najmä akým spôsobom získame čo najväčšiu spätnú väzbu, aby sme vychytali chyby, lepšie vyvážili zadania a pripravili druhé vydanie :-)

Poznámka: Úlohy z prvej kapitoly si môžete pozrieť tu.

Fermatova množina

2010-01-12T19:52:00.006+01:00

Dnes uplynulo presne 345 rokov od smrti slávneho Fermata a pri tejto príležitosti vyšiel na SME celkom pekný a čitateľsky úspešný článok. Diskusie k podobným článkom sú síce zaujímavé viac z psychologického, než z matematického hľadiska, avšak občas sa v nich vyskytne komentár, nad ktorým sa oplatí zamyslieť. V diskusii k článku o Fermatovi bola pre mňa takou nasledovná otázka čitateľa "toerotik":

"Ak mocnina 2 je Pytagorova veta, a pre [mocninu] 3 vraj mal [Fermat] dôkaz [veľkej Fermatovej vety], ako je to s mocninou napríklad 2,2?"

Teória čísiel nie je mojou silnou stránkou, ale tipol by som si, že táto otázka môže byť netriviálna aj pre špecialistu. Formulujme si preto nasledovnú, podstatne všeobecnejšiu úlohu:

Fermatovou množinou nazvime množinu všetkých reálnych čísiel r, pre ktoré existujú prirodzené čísla x,y,z spĺňajúce x^r+y^r=z^r. Čo všetko vieme povedať o Fermatovej množine?

Jedna z vlastností Fermatovej množiny je tá, že obsahuje čísla 1 a 2, ale neobsahuje žiadne väčšie prirodzené číslo (to je vlastne veľká Fermatova veta). Vieme povedať o nejakých ďalších reálnych číslach, že patria, alebo nepatria do Fermatovej množiny? Vieme povedať, či Fermatova množina obsahuje nekonečne veľa reálnych čísiel? ... Teším sa na Vaše postrehy.

13.1.: V komentároch sa nám podarilo dokázať, že Fermatova množina je hustá v reálnych číslach, čiže pri akomkoľvek reálnom čísle vieme nájsť ľubovoľne blízko nejaké číslo z Fermatovej množiny. Peťo tiež našiel pomerne nedávny článok, z ktorého plynie, že kladné čísla z Fermatovej množiny sú iracionálne, s výnimkou čísiel tvaru 1/n a 2/n, kde n je prirodzené číslo.

Napadlo ma, že by mohlo byť zaujímavé zobraziť grafy funkcií x^r+y^r-z^r reálnej premennej r pre niekoľko "malých" trojíc prirodzených čísiel x,y,z. Tu je výsledok pre všetky trojice prirodzených čisiel x,y,z, ktoré nepresahujú 8:

Červenou bodkou som zaznačil čísla r, v ktorých platí x^r+y^r-z^r=0, čiže čísla z Fermatovej množiny. Keď som zväčšoval počet trojíc x,y,z, červené bodky skutočne čím ďalej, tým hustejšie pokrývali množinu reálnych čísiel...

Membrána medzi obručami

2009-12-22T21:29:00.003+01:00

Dve rovnaké kruhové obruče namočíme do mydlovej vody a opatrne ich od seba vzdialime. Aký tvar bude mať membrána, ktorá sa medzi nimi vytvorí?

Intuitívne sa zdá zrejmé, že membrána bude mať tvar plášťa valca, ako je to zobrazené na ilustračnom obrázku vľavo. Ale je to tak naozaj?

Túto peknú úlohu mám od otca, ktorého silnou stránkou je to, že veľmi dobre rozumie fyzike (na rozdiel od mnohých iných matematikov) a za vzorcami vidí reálny svet. Možno aj preto je taký obľúbený pedagóg :-)

3.1.2010: Ako ste už správne napísali v komentároch, membrána medzi obručami nebude mať tvar plášťa valca; tu je dôkaz:

Vzhľadom na to, že mydlová membrána je extrémne tenká, je gravitačné pôsobenie zanedbateľne malé a jej tvar bude takmer presne zodpovedať plášťu rotačného telesa s minimálnym možným povrchom. Ako správne odhadol Vlado, úloha nájsť také teleso patrí do obasti variačného počtu a ako napísal Rasťo, výsledkom je teleso nazývané catenoid, ktoré vznikne rotáciou "reťazovky", čiže vlastne hyperbolického kosínu.

PS: Želám Vám šťastný nový rok a okrem iného veľa potešenia z nového poznania :-)

Delenie hranatého koláča II

2009-12-15T12:16:00.003+01:00

Traja matfyzáci napiekli koláč v tvare nepravidelného konvexného šesťuholníka a teraz špekulujú nad tým, ako si ho podeliť spravodlivo, čiže tak, aby každý z nich dostal rovnakú časť koláča. Základný nápad je jednoduchý: vo vnútri koláča zvolia "centrálny" bod a od tohoto bodu budú viesť priame rezy smerom k vrcholom šesťuholníka. Poraďte im ako majú tento centrálny bod zvoliť, aby si mohli výsledných šesť trojuholníkových kúskov medzi sebou spravodlivo podeliť.

Na ilustračnom obrázku je príklad voľby takéhoto bodu a príslušného delenia: červené kúsky dostane jeden, žlté druhý a hnedé tretí. Táto úloha je už trochu náročnejšia ako predchádzajúca; pokúsme sa najprv zodpovedať otázku, či také delenie vôbec vo všeobecnosti existuje, čiže či je vôbec základná myšlienka delenia správna.

Delenie hranatého koláča.

2009-12-12T23:08:00.002+01:00

Zábavný článok v časopise New Scientist o krájaní pizze ma inšpiroval k formulovaniu nasledovnej, podobnej, ale omnoho ľahšej úlohy:

Koláč v tvare pravidelného n-uholníka (pričom n je párne) rozkrájame na n trojuholníkových kúskov tým spôsobom, že vedieme rezy od vrcholov koláča k náhodne zvolenému bodu vo vnútri koláča. Kúsky si potom medzi sebou striedavo rozdelia dvaja ľudia. Dostanú obaja rovnakú časť koláča?

Na ilustratívnom obrázku máme znázornenú situáciu pre n=6 a n=8. Jeden človek dostane kúsky vyznačené žltou farbou a druhý človek kúsky vyznačené hnedou farbou.

Superprvočísla

2009-12-09T09:31:00.002+01:00

Na pondelkovej prednáške doc. Haviara bol uvedený aj pojem superprvočísla, čo je také prvočíslo, ktorého každá cifra je prvočíslom, čiže ktorého cifry sú 2,3,5, alebo 7. Zdá sa, že superprvočísiel je nekonečne veľa a taktiež sa zdá, že nekonečne veľa je aj tých superprvočísiel, ktorých každá dvojica za sebou nasledujúcich čísiel tvorí prvočíslo, ako napríklad 57373. Prirodzene vzniká nasledovná otázka:

Je nekonečne veľa takých superprvočísiel, ktorých ľubovoľná dvojica aj ľubovoľná trojica za sebou nasledujúcich cifier tvorí tiež prvočíslo?

Všimnite si, že prvočíslo 57373 také nie je, pretože napríklad 573 nie je prvočíslo.

Prvočísla a ich číselní príbuzní (pozvánka na prednášku)

2009-12-04T10:01:00.003+01:00

V pondelok 7. 12. 2009 o 14:00 sa v miestnosti F1-326 na FMFI UK uskutoční prednáška doc. RNDr. Miroslava Haviara, PhD. s názvom "Prvočísla a ich číselní príbuzní". Prednáška bude určite veľmi zaujímavá, pretože sa týka problémov, ktoré je veľmi ľahké pochopiť, avšak často extrémne ťažké vyriešiť. Dovolil som si sem skopírovať abstrakt prednášky obohatený o hypertextové odkazy na príslušné pojmy:

Abstrakt

Spomenieme Euklidov dôkaz nekonečného počtu prvočísel cez pojem primoriálneho čísla a otvorený problém nekonečného počtu primoriálnych prvočísel. Na podporu toho, že prvočísla majú „častý výskyt,” uvedieme Dirichletovu vetu, Hypotézu prvočíselných dvojčiat a Goldbachovu hypotézu, a na podporu toho, že majú „zriedkavý výskyt,” argumentujeme ľubovoľne veľkými prime gaps a spomenieme jumping champions. Názor, že o prvočíslach vieme stále málo, podporuje aj 13 otvorených problémov, ktoré počas prednášky spomenieme. Z problémov nedávno zodpovedaných spomenieme Erdösov problém vyriešený Terencom Taom, týkajúci sa existencie n prvočísel v aritmetickej postupnosti pre ľubovoľné n [Terence Tao spolu s ďalším veľmi mladým matematikom Benom Greenom vyriešili dôležitý špeciálny prípad Erdösovho problému, čo sa dnes nazýva Greenova-Taova veta. Pozn. RH]. Názor, že o prvočíslach vieme relatívne dosť podporíme Gandiho vzorcom (rekurzívnou formulou) pre n-té prvočíslo a vysvetlíme, prečo funguje. Spomenieme pseudoprvočísla a AKS algoritmus a tiež Fermatove čísla a Eisensteinovu hypotézu o nekonečnom počte Fermatových prvočísel. Zmienime sa o Eulerovom i Goldbachovom argumente pre nekonečnosť počtu prvočísel, pričom ukážeme, ako ten druhý využíva Fermatove čísla. Záverom spomenieme aj vlastné skúmanie (s P. Maličkým) pojmu superprvočísel ako špeciálnych prvočísel a niektoré súvisiace hypotézy. Napokon sa zmienime o hypotéze zovšeobecnenia Dirichletovej vety, z ktorej vyplývajú aj známe hypotézy ohľadne nekonečného počtu Fermatových a Mersennových prvočísel.

Planéta X

2009-12-01T14:13:00.009+01:00

Planéta X má tvar gule, pričom jej obývateľná zóna tvorí pás okolo rovníka, ktorého šírka je jedna šestina obvodu planéty. (Čiže najkratšia cesta od jedného kraja tohoto pásu po druhý kraj, samozrejme po povrchu planéty, má dĺžku šestinu obvodu tejto planéty.) Koľko percent povrchu tejto planéty je obývateľných? Koľko percent povrchu planéty X by bolo obývateľných, ak by bola nie troj, ale štyridsaťdvarozmerná?

Poznámka: V prípade 42 rozmernej planéty je úloha dosť náročná; už len formulovať ju matematicky presne nie je jednoduché. Ak chcete, môžeme o tom samozrejme podiskutovať a vyriešiť túto úlohu aspoň numericky...

Poznámka 3.12.: No, "dosť náročná" je pre ten 42 rozmerný prípad asi eufemizmus. "Pekelná" je asi lepší prívlastok a to napriek tomu, že riešenie je len dávno známy špeciálny prípad tvrdení z článku, ktoré sme s Vladom Lackom prednedávnom zaslali do časopisu. Ale nič to. Môžeme tu mať aj takúto úlohu. Ak by sa niekto cítil byť veľký frajer...

Osobnosti slovenskej matematiky: Lev Bukovský (pozvánka na prednášku)

2009-11-23T14:32:00.002+01:00

(Po kliknutí na obrázok sa oznam zobrazí v plnom rozlíšení.)

Počítame semienka

2009-11-18T22:25:00.007+01:00

To, čo je nasypané do sklenenej kocky na fotografii sú, predstavte si, sézamové semienka. Pokúste sa odhadnúť ich počet. (Kocka má hranu dĺžky približne 1 meter.)

Rozuzlenie 29.11.:

(Obrázok sa kliknutím zväčší.)

Väčšina z Vás tipovala niekoľkonásobne vyšší počet semienok, hoci rádovo správne. Zďaleka najlepšia sa však ukázala metóda odhadu počtu semienok na základe výšky Kofoly v pohári, ktorej aplikáciou vyšlo gooberovi 110 524 267.

Ja by som postupoval nasledovne: Zaplnená časť kocky semienok má rozmery zhruba 1000 × 1000 × 700 milimetrov. Aké veľké je sezamové semienko možno odhadnúť napríklad pomocou stránky "cells size and scale", ktorá je mimochodom zaujímavá aj sama o sebe. Sezamové semienko má nepravidelný tvar, ale podľa obrázka je jeho objem približne rovnaký, aký má guľôčka o polomere 1 milimeter. Guľôčky (a ani semienka) sa samozrejme nedajú naukladať tak, aby medzi nimi nebol žiadny voľný priestor; ich ideálne naukladanie necháva približne 25 percent priestoru voľného, takže odhadnime, že medzi semienkami je v skutočnosti voľného približne 28 percent objemu. Výsledkom je odhad 120 321 137. :-)

Ešte dodám, že fotografie pochádzajú z vedeckej exhibície Universum v Brémach.

Pomôžte Agátke s výzdobou

2009-11-09T18:19:00.007+01:00

Moja dcérka Agátka dostala včera kolekciu 16 nálepiek, ktoré zodpovedajú symbolom 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, +, -, ×, /, = (v skutočnosti táto sada obsahuje aj kvietky s číslami, ale tie ignorujme). Pomôžte Agátke z týchto symbolov poskladať platnú rovnicu. Čím viac nálepiek v nej bude využitých, tým lepšie.

Napríklad rovnosť 8/4=2 je zostavená z 5 nálepiek, rovnosť 60/3=2×10 sa skladá z 8 nálepiek, ale možno (ehm) existujú aj rovnosti, ktoré používajú ešte viac týchto nálepiek...

Takáto úloha je síce trochu infantilná, ale 1. nájsť najlepšie riešenie nie je vôbec jednoduché a 2. vážnych úloh máme dosť na vyučovaní, nie? ;-)

29.11.: Ďakujeme za všetky návrhy! Agátka si vybrala a nalepila nasledovnú rovnicu:

Ako navigovať robota II

2009-11-06T10:59:00.007+01:00

Predchádzajúca úloha sa ukázala byť celkom úspešná; viacerí z Vás našli pekné riešenia logickou úvahou a Rori dokonca našiel riešenie optimálne v tom zmysle, že je najkratšie možné. Pomocou peknej myšlienky Rori tiež vygeneroval množstvo "ťažkých" diagramov, ktoré som si trochu poprezeral a jeden z nich som modifikoval do nasledovnej podoby:

Tak ako v predchádzajúcej úlohe, cieľom je nájsť postupnosť príkazov M/C, ktorá dovedie robota do miestnosti A z akejkoľvek ~~inej~~* miestnosti.

Kto nájde optimálne riešenie len v hlave, je génius. A kto nájde riešenie pomocou počítača, je schopný programátor. Možno keby som bol zamestnávateľ a chcel by som zistiť, či vie niekto naozaj programovať a algoritmicky myslieť (čo si dnes o sebe myslí skoro každý), tak by som mu dal počítač a požiadal ho, nech mi do hodiny povie riešenie tejto úlohy :-)

* Pôvodne som formuloval úlohu so slovom "inej" a takáto úloha je zmysluplná a tiež pomerne obtiažna, pričom ju vyriešil Nanyk (pozri komentáre). Pôvodný zámer bol však taký, že dané riešenie musí dostať robota do miestnosti A aj ak ten robot začína v priamo v A. Pri riešení tohto pôvodne zamýšľaného problému sa však možno dajú Nanykove myšlienky použiť ...

Ako navigovať robota I

2009-11-02T18:38:00.011+01:00

Máme labyrint piatich miestností znázornený na ilustračnom obrázku. Medzi každými dvomi miestnosťami je práve jedna jednosmerná cesta, ktorá je buď modrá, alebo červená. V niektorej (neznámej) miestnosti tohto labyrintu je robot, ktorého síce nevidíme, ale môžeme mu posielať príkazy typu M (prejdi modrou cestou) a C (prejdi červenou cestou). Je možné vyslať robotovi takú postupnosť príkazov M/C, aby po jej vykonaní s istotou skončil v miestnosti A?

Tento príklad je motivovaný istou úlohou z knihy Ivan Moscovich: The Big Book of Brain Games.

Poznámka 3.11.: V kometároch ma upozornil misof na to, že táto úloha je príbuzná jednému otvorenému problému, ktorý súvisí s Československom. Tak som sa na to trochu pozrel a naozaj! Jedným z najznámejších otvorených problémov teórie konečných automatov je takzvaná Černého domnienka, ktorá vychádza z článku Jána Černého publikovaného priamo v slovenčine! Ako je možné, že to nepatrí ku "common knowledge" aspoň medzi slovenskými matematikmi?

Ak chcete o tomto probléme vedieť viac, tak si môžete prečítať tento pekný článok. Ale v zásade sa jedná o nasledovné: Predpokladdajme, že máme podobný diagram ako v našej úlohe, pričom miestností je n a existuje nejaká pevná postupnosť príkazov, ktorá pošle robota do danej miestnosti z akejkoľvek inej miestnosti. Potom existuje aj postupnosť príkazov, ktorá toto spĺňa a jej dĺžka nepresahuje (n-1)². Černého diagram stupňa 5, v ktorom je najkratšie riešenie dĺžky 16, je znázornený na nasledovnom obrázku. (Viete to riešenie nájsť?)

Ako hrať proti telepatovi

2009-10-30T08:59:00.007+01:00

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

2009-10-22T11:05:00.007+02:00

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

Samé polovice

2009-10-19T21:16:00.016+02:00

Nech n>=2 je prirodzené číslo. Nájdite najväčšie číslo p_n s nasledovnou vlastnosťou: Ak každá z udalostí A₁,...,A_n má pravdepodobnosť 1/2, potom existujú rôzne indexy i,j také, že pravdepodobnosť súčasného nastatia udalostí A_i a A_j je aspoň p_n.

Formulujme túto úlohu aj bez použitia pravdepodobnosti (hoci máličko menej všeobecne): Pre n>=2 nájdite najväčšie také číslo p_n, že ak zjednotenie n množín plochy 1/2 má plochu nanajvýš 1, tak plocha prieniku niektorej dvojice z týchto množín je aspoň p_n.

Je zrejmé, že p₂=0 a z ilustračného obrázku sa zdá, že p₃=1/6. Viete to dokázať? Viete nájsť hodnotu p_n pre niektoré (alebo aj všetky) čísla n>=4?

Poznámka 23.10.: Dnes ráno ma napadlo pomerne jednoduché trikové riešenie využívajúce niektoré základné poznatky z pravdepodobnosti. Hodnota p_n je prekvapivo jednoduchou funkciou počtu udalostí n, hoci výsledný vzorček je trochu odlišný pre párne a pre nepárne n.

Beta verzia "Zbierky úloh z pravdepodobnosti" je live

2009-09-28T11:04:00.009+02:00

Ešte pred dokončením našej zbierky úloh z pravdepodobnosti sme sa rozhodli, že urobíme malý experiment: jej odľahčenú internetovú verziu. Zatiaľ sme uverejnili zadania prvých štyroch podkapitol (asi 50 úloh; celkovo ich je v zbierke vyše 400) a budeme čakať, čo na to študenti. Využijú možnosť pýtať sa nás na detaily zadaní a diskutovať o riešeniach medzi sebou? Uvidíme a podľa toho sa zariadime v budúcnosti.

Každopádne, ak máte chvíľku čas, mohli by ste sa na našu zbierku pozrieť aj Vy a prípadne nám poradiť, čo by sa na nej podľa Vás dalo zlepšiť. Budeme veľmi povďační!

Ilustračný obrázok vľavo je môj návrh na obálku tlačenej verzie zbierky. Ak k nemu máte výhrady, sem s nimi. Ešte stále je čas všetko zmeniť :-)

PS: Ak by ste aj Vy chceli vyriešiť nejakú úlohu v zbierke, ale nepoznáte pravdepodobnostnú formalizáciu z našich prednášok, vyskúšajte napríklad takú úlohu 55. Ďalšie neformálne a nie celkom triviálne úlohy prídu neskôr.

Kombinatorická identita

2009-09-26T22:49:00.005+02:00

Už takmer 12 hodín bez väčšej prestávky pracujem na zbierke príkladov z pravdepodobnosti. (Neverili by ste, koľko je s jej napísaním roboty; ale čím ďalej, tým viac sa ma zmocňuje pocit, že keď bude naša zbierka na svete, tak z nej budeme mať radosť.)

Práve som písal riešenie jedného príkladu, v ktorom som použil nasledovnú kombinatorickú identitu:

Hľadím na ňu už asi dvadsať minút a nenapadá ma, ako by som ju dokázal. Vedeli by ste mi pomôcť?

Ďalšia zapeklitá úloha z pravdepodobnosti

2009-09-10T20:22:00.014+02:00

Už sa teším na obdobie, keď odovzdáme do tlače našu zbierku úloh z teórie pravdepodobnosti a budem sa môcť rozpísať napríklad o nedávnej návšteve "Univerza" v Brémach, alebo o množstve zaujímavých nových odkazov. Dovtedy však zo mňa nedostanete nič viac, ako len ďalšiu zapeklitú úlohu z pravdepodobnosti. Tentokrát je podľa mňa celkom pozoruhodná a ak sa ju niekomu podarí do týždňa vyriešiť nejakým jednoduchým trikom bez použitia náhodných premenných, má u mňa dve odmeny: jeho meno sa objaví v našej zbierke a darujem mu jeden exemplár zbierky aj s podpismi autorov :-)

Dokážte, že ak súčet pravdepodobností n-tice udalostí je viac ako k-1 (pre akékoľvek k od 1 do n), tak sa s nenulovou pravdepodobnosťou realizuje aspoň k spomedzi týchto udalostí.

Napríklad ak by sme mali skupinku piatich ľudí, pričom (pravdepodobnosť, že prvý z nich spraví skúšku) + (pravdepodobnosť, že druhý z nich spraví skúšku) + ... + (pravdepodobnosť, že piaty z nich spraví skúšku) > 3, tak potom s nenulovou pravdepodobnosťou sa stane to, že skúšku spravia aspoň štyria z týchto piatich ľudí. Pritom nepredpokladáme, že udalosti urobenia skúšky sú nezávislé. (Nakoniec, predpokladať úplnú nezávislosť vypracovávania písomnej časti skúšky by naozaj bolo značne naivné.)

Na ilustračnom obrázku sú štyri množiny (mesiačiky A,B,C a kruh D), pričom neexistuje prienik všetkých štyroch. To znamená, že ak by sme akokoľvek divoko hádzali šípkou do tohto obrázka, tak súčet pravdepodobností zasiahnutia jednotlivých oblastí nemôže byť väčší ako 3.

Telepat II

2009-08-27T08:44:00.007+02:00

Tentokrát nášmu telepatovi zaplatíme za každý uhádnutý symbol 1 euro. Telepat si postupne prikladá na čelo jednotlivé obálky, pričom vždy po chvíľke telepatovania danej obálky povie svoj tip, čo by sa v nej malo nachádzať. Vypočítajte strednú hodnotu jeho zisku, ak nemá žiadne telepatické schopnosti, avšak má dokonalú pamäť a pritom používa optimálnu stratégiu tipovania. Uvažujeme nasledovné spresnenia:

a) Počas tipovania nedostáva telepat žiadnu informáciu o obsahu obálok, t.j. všetky obálky sa otvoria až po ukončení jeho tipovania. b) Po každom tipe sa daná obálka otvorí a telepat sa dozvie, ktorý symbol v nej bol. c) Po každom tipe prezradíme telepatovi len to, či uhádol, alebo neuhádol, avšak nie to, ktorý konkrétny symbol sa v danej obálke nachádzal.

Riešenie ani jednej z týchto troch úloh nie je úplne triviálne (pokiaľ človek nenájde správny trik), preto sú veľmi vítané akékoľvek nápady, riešenia pre malé n, prípade simulačné výsledky.

Namiesto ilustračného obrázku mám dnes pre Vás link od Juraja.

Poznámka 27.8.: Ak som sa nepomýlil, tak tie stredné hodnoty zisku pri optimálnej stratégii vychádzajú vo všetkých troch prípadoch celkom pekne. Ak si s tým problémom neviete poradiť, pokúste sa aspoň odhadnúť, či pre rastúce n (n je počet rôznych symbolov, t.j. aj počet obálok) ide stredná hodnota zisku pri optimálnej stratégii do nekonečna, alebo naopak, či existuje hranica, ktorú stredná hodnota zisku nepresiahne pre žiadne n ani pri tej najlepšej stratégii. Čo hovorí Vaša intuícia?

Telepat

2009-08-21T12:58:00.007+02:00

Tieto dni je mojou hlavnou pracovnou náplňou dokončovanie zbierky príkladov z teórie pravdepodobnosti, ktorú musíme čoskoro odovzdať do tlače. Pri spisovaní riešenia jedného príkladu ma napadla takáto netechnická formulácia vhodná aj na náš blog:

Telepat bez akýchkoľvek telepatických schopností, ktorému bolo navyše nečakane znemožnené podvádzať, sa snaží určiť n rôznych symbolov nachádzajúcich sa na kartách v n nepriehľadných obálkach. (Telepat vopred vie, aké symboly boli náhodne rozdistribuované do obálok; nevie len to, v ktorej obálke je ktorý symbol. Telepat teda priradí obálkam n-ticu symbolov úplne náhodne a až potom sa všetky obálky otvoria, aby sa zistilo, koľko symbolov uhádol.) Čo je pravdepodobnejšie: to, že neuhádne ani jeden symbol, alebo to, že uhádne práve jeden symbol?

Na ilustratívnom obrázku sú takzvané Zenerove karty, ktoré sa často používajú na testovanie proklamovaných telepatických schopností. V našom zadaní je však počet kariet všeobecné n, t.j. nielen 5. Teším sa na Vaše riešenia.

7+7=12

2009-08-15T16:02:00.009+02:00

Ak sa Vám zdali posledné úlohy príliš matematicky technické, ponúkam Vám pre zmenu jeden detský hlavolam, ktorý však môže spôsobiť polhodinovú frustráciu aj učiteľovi na matfyze. Viem to z vlastnej skúsenosti :-) Na túto úlohu som natrafil v jednej z mojich nových kníh, ale jej názov uvediem až keď budeme mať riešenie.

Viete dokázať, že sedem je polovica z dvanástich?

Riešenie podobných hlavolamov sa zakladá na tom, že sa nájde nejaký nečakaný vysvetľujúci uhol pohľadu (ktorý by niekto mohol nazvať aj "podfuk"). Takýchto uhlov pohľadu existuje obvykle viac, avšak za správny sa považuje ten, o ktorom väčšina ľudí retrospektívne cíti, že je najjednoduchší, alebo najkrajší. V tomto zmysle nepovažujeme za správne riešenie ani to, čo som načrtol na ilustratívnom obrázku, ale ani odpovede typu "7+7=12 v dvanástkovej sústave". Správne riešenie je úplne iného typu.

Ondrova-Misofova rekurencia

2009-08-04T22:03:00.008+02:00

Predchádzajúcu zaujímavú úlohu od Ondra by sme mali vyriešenú, ak by sa nám podarilo dokázať jednu celkom pozoruhodnú domnienku, ktorú v komentároch formuloval misof a ktorú je možné zapísať v nasledovnom tvare:

Nech Q₁=0, Q₂=1/3 a pre n=3,4,5,... nech

Potom

Numericky táto domnienka sedí natoľko presne, že jej platnosť je prakticky istá. Ide len o jej formálny dôkaz...

Ja sa do rekurencií veľmi nevyznám, ale všimol som si, že Ondrova-Misofova rekurencia spĺňa jednu peknú vlastnosť: Člen Q_n je váženým priemerom členov Q₁, Q₂,...,Q_n-2. Z toho je napríklad okamžite jasné, že všetky členy postupnosti budú medzi číslami Q₁ a Q₂. Je ale možné toto pozorovanie použiť na dôkaz skutočnosti, že postupnosť hodnôt Q_n konverguje, prípadne dokonca toho, že konverguje práve k číslu e^-2? Vyzerá to byť pekná a netriviálna matematická úloha...

Šialení diktátori

2009-07-27T21:52:00.012+02:00

Nasledovnú úlohu nám poslal Ondro Budáč z letnej brigády v Oxforde, kde programuje simulácie istých fyzikálnych dejov. (Inak vy sa teda máte s takýmito fajnovými brigádami; ja som chodil kopať jamy na bazény.) Pôvodná Ondrova formulácia obsahuje len rad guličiek, tak som sa ju rozhodol trochu zdramatizovať.

Okolo istej hviezdy obieha na kruhovej obežnej dráhe rovnakou rýchlosťou n planét, pričom ich stredy tvoria vrcholy pravidelného n-uholníka. Každá z týchto planét vlastní atómovú bombu, ktorá je schopná zasiahnuť a zlikvidovať ktorúkoľvek z dvoch najbližších planét, nie však vzdialenejšie planéty. Z času na čas sa na niektorej z planét náhodne dostane k moci šialený diktátor, ktorý sa rozhodne zničiť niektorého zo susedov (samozrejme len ak ho ešte nezlikvidoval druhý sused). Avšak ešte skôr ako atómová bomba zasiahne napadnutú planétu, s istotou stihne aj ona vystreliť atómovú bombu na agresora a obe planéty sa tak zničia navzájom. (Pozn.: Predpokladáme, že od okamihu vystrelenia bomby na napadnutú planétu až po dopad druhej bomby na planétu agresora sa ostatné planéty zdržia konfliktov.)

Otázka znie, aká je stredná hodnota E_n planét, ktoré sa takto zlikvidujú. Zaujíma nás najmä pomer E_n/n pre n idúce do nekonečna.

Jeden možný priebeh atómových konfliktov, v ktorých sa zo 100 pôvodných planét navzájom eliminovalo 86, ilustruje nasledovné video.

Podotýkam, že tento problém je ťažký, pretože ani Ondrovi, ani mne sa ho zatiaľ nepodarilo vyriešiť (hoci je pravda, že príliš veľa času sme nad ním zatiaľ nestrávili). Kto nájde analytické vyjadrenie tajomnej konštanty, ku ktorej sa blíži E_n/n, ten má môj obdiv.

Poznámka: Ak Vám nie je zadanie úplne jasné, tak možno nájdete odpoveď na svoju otázku komentároch.

Čo najviac súkromia

2009-07-22T08:50:00.010+02:00

Krátko po tom ako som sa vrátil z konferencie spomenutej v predchádzajúcom príspevku, odcestoval som na ďalšiu konferenciu: Petersburg Workshop on Simulation. Samotná návšteva Petrohradu bola pre mňa dosť veľký zážitok (konečne som videl na vlastné oči napríklad Auroru a Zimný palác, ktoré nám ako pionierom toľko tlačili do hláv), ale tým Vás nebudem obťažovať; cestovateľských, prípadne politických blogov je veľa.

Určite viete, že v Petrohrade je jedna z najväčších galérií na svete - Ermitáž. Pri jej návšteve som mal dvojité šťastie. Po prvé, vybrali sme sa na prehliadku náhodou práve v jediný deň v mesiaci, počas ktorého je voľný vstup a po druhé bola s nami Anastasia Ivanova, ktorá si kedysi popri učení na univerzite privyrábala robením sprievodkyne práve v Ermitáži. Takže sme nielenže nezablúdili, ale dokonca sme videli výber z tých najzaujímavejších exponátov.

V jednej z miestností utrúsila Anastasia poznámku, že nechápe, ako mohla cárska rodina bývať v budove s takmer samými priechodnými miestnosťami; nepotrebovali väčšie súkromie? Nech už to bolo s cárskou rodinou akokoľvek, ak obmedzíme maximálny počet dverí v každej miestnosti, tak istý počet priechodných miestností je nutný. A máme nasledovný rekreačný problém na náš blog:

Predpokladajme, že každá z n (nie nutne štvorcových ani obdĺžnikových) miestností v budove má nanajvýš troje dverí, ktoré ju spájajú so susednými miestnosťami. Koľko maximálne môže byť v tejto budove miestností, ktoré majú len jedny dvere? Samozrejme predpokladáme, že z každej miestnosti sa dá prejsť do každej inej miestnosti.

Na obrázku je budova s 10 miestnosťami, z ktorých je až 6 "súkromných" a žiadna miestnosť nemá viac ako troje dverí. Vítané sú samozrejme nielen riešenia, ale akékoľvek postrehy a komentáre, prípadne zovšeobecnenia.

Problém profesora Zmyśloneho

2009-07-14T07:26:00.019+02:00

Po mesiaci skúšania, cestovania po konferenciách, iných povinností a krátkych dovoleniek som späť a hneď Vám prinášam možnosť nielen sa zabaviť, ale aj ... trochu si vylepšiť finančnú situáciu a najmä stať sa v istom kruhu matematikov slávnym. Celkom vážne. Ale jednoduché to nebude.

Na jednej z dvojice konferencií, ktoré som v poslednej dobe absolvoval (International Workshop on Matrices and Statistics) sa udiala pomerne nezvyklá vec: počas svojej prednášky vyhlásil profesor Roman Zmyślony cenu $100 za vyriešenie istého matematického problému. Na rozdiel od väčšiny príkladov na blogu QED, problém profesora Zmyśloneho si vyžaduje znalosti z vyššej matematiky, avšak napríklad druháci na matfyze, ktorí absolvovali teóriu matíc, sú určite schopní pochopiť zadanie, čo je v prípade súčasných nevyriešených problémov skôr výnimkou ako pravidlom.

Originálne zadanie si pozrite na nasledovnom zábere priamo z prednášky prof. Zmyśloneho (kliknutím sa fotografia zväčší) a potom sa o ňom porozprávame trochu podrobnejšie.

Skratka nnd znamená ''nezáporne definitné'', symbol tr znamená stopu matice a symbol H₊ je "pozitívne semidefinitná časť" symetrickej matice H. Presnejšie, ak u₁,...,u_n je ortonormálny systém vlastných vektorov matice H typu n × n a λ₁,...,λ_n sú prislúchajúce vlastné čísla, tak

(Ak žiadne z vlastných čísiel matice H nie je kladné, tak položíme H₊=0.) Dá sa ľahko ukázať, že aj ak existuje viac ortonormálnych systémov vlastných vektorov, tak H₊ je definovaná jednoznačne; t.j. nezávisí od výberu tohto systému vlastných vektorov.

Majte na pamäti, že tento problém je naozaj ťažký, takže vítané sú akékoľvek zmysluplné poznámky, ktoré by nám mohli pomôcť urobiť čo i len maličký krôčik k riešeniu.

Poznámka 1: Urobil som veľké množstvo testov tejto hypotézy s náhodne vygenerovanými pozitívne semidefinitnými maticami A a V a vo všetkých prípadoch bola Zmyśloneho domnienka splnená. Som si teda skoro istý, že platí, avšak je ju ťažké matematicky rigorózne dokázať.

Poznámka 2: Hypotéza je už dokázaná za podmienky AV=VA, t.j. ak matice A a V komutujú. (Zaujímavý je preto prípad, keď A a V nekomutujú.) Vytvoril som súbor, do ktorého budem zapisovať všetko čo zistíme (dôkaz pre komutujúce matice je už tam.) Pridajte sa tiež so svojimi nápadmi!

Medoid trojice bodov

2009-06-12T15:32:00.014+02:00

Narýchlo len jeden príkladík; nič mimoriadne, ale aspoň že je môj vlastný :-) Napadol ma dnes pri skúšaní analýzy zhlukov na predmete "Viacrozmerné štatistické analýzy 2".

Majme trojuholník ABC s navzájom rôznymi dĺžkami strán. Z trojice vrcholov A,B,C nazveme medoidom ten, ktorý má minimálny súčet vzdialeností od zvyšných dvoch vrcholov. Je nutne medoid bližšie k ťažisku trojuholníka ABC než zvyšné dva vrcholy?

Poznámka 13.6.: V komentároch nájdete Peťove riešenie pomocou súradnicového systému, ale skoro by som sa stavil, že existuje aj nejaké veľmi jednoduché tvrdenie založené na klasickej geometrii :-) Nájdete ho?

Poznámka 14.6.: Zdá sa, že môže platiť aj nasledovné tvrdenie; vedeli by ste nájsť dôkaz?

Majme trojuholník ABC s navzájom rôznymi dĺžkami strán. Z trojice vrcholov A,B,C nazveme antimedoidom ten, ktorý má maximálny súčet vzdialeností od zvyšných dvoch vrcholov. Je nutne antimedoid vzdialenejší od ťažiska trojuholníka ABC než zvyšné dva vrcholy?

Inak včera som sa dosť dlho zamýšľal nad tým, prečo sa našej študentskej ankety zúčastňuje tak málo študentov. Aký je na to Váš názor? Čo by mohlo pomôcť? Vedel by som napríklad vytvoriť myslím celkom rozumný spôsob ako na základe hodnotenia od študentov urobiť rebríček top 10 najobľúbenejších vyučujúcich (pochopiteľne, jednoduché porovnanie priemerov hodnotení nie je vyhovujúce). Mohlo by to podľa Vás anketu zatraktívniť?

Výsledky súťaže o najkrajšiu úlohu

2009-06-07T18:04:00.007+02:00

Chcel by som poďakovať všetkým deviatim účastníkom súťaže, ktorí nám poslali 12 super úloh, ako aj ôsmim "porotcom", ktorí sa spolupodieľali na určení nasledovného výsledného poradia:

1. miesto (57 bodov): úloha Sto väzňov od Ondreja Budáča; 2. miesto (39 bodov): úloha Mravce na tyči od Petra Richtárika; 3. miesto (31 bodov): úloha Zapadajúce množiny od Ondreja Budáča

Ďalšie poradie nebudem zverejňovať, ale aby ste si spravili predstavu o tom, aké boli výsledky tesné: úlohy, ktoré skončili od 4. do 8. miesta mali medzi 22 a 29 bodov. Zaujímavé je tiež, že porotcovia dávali veľmi odlišné hodnotenie; všetkých 8 najlepšie hodnotených úloh bolo takých, že niektorý porotca ich zaradil na jedno z prvých dvoch miest, zatiaľčo iný porotca im dal 0 bodov. Individuálna predstava čo je to "pekná úloha", je prekvapivo rôznorodá.

Takže gratulujem víťazom a Ondro odo mňa získava sľúbenú knihu.

Prsty

2009-05-26T18:12:00.018+02:00

Priebežné výsledky sú na konci príspevku. Ak neviete o čo ide, čítajte ďalej.

Skutočne je rozdiel medzi pomerom dĺžok ukazováka a prstenníka u mužov a u žien, alebo je tento takzvaný "fenomén 2D:4D" len výmysel na oživenie koktailových večierkov?

Napadlo ma, že toto tvrdenie by sme mohli spoločne overiť priamo tu na blogu QED. Stačí, ak si odmeriaš dĺžku ukazováka a prstenníka na pravej aj ľavej ruke a okrem týchto údajov uvedieš do komentára ešte informáciu o tom, či si žena, alebo muž. Ak budeš mať chvíľu čas a pri sebe priateľov, môžeš zmerať dĺžky týchto štyroch prstov aj im (inak pre nesmelých výborná metóda nadviazania kontaktu :-); čím viac údajov budeme mať, tým lepšie. Dĺžky meraj s presnosťou na 1 milimeter od konca prstov až po spodnú vrásku deliacu prst od dlane, tak ako je naznačené na fotografii mojej pravej ruky. Postupne budem robiť príslušné štatistické testy a uvidíme, či sa teória o rôznom pomere dĺžok prstov u žien a u mužov potvrdí.

Takže meranie číslo 1 bude zodpovedať mojim vlastným prstom (P znamená pravá ruka, L ľavá ruka, u ukazovák a p prstenník): Pu 7,6 mm; Pp 8,0 mm; Lu 7,4 mm; Lp 7,9 mm.

..............

Po údajoch od 17-tich ľudí zobrazuje nasledovný graf priebežné výsledky pomeru dĺžky ukazováka a prstenníka: jednotlivé hodnoty pomeru ako bodky a 95 percentné intervaly spoľahlivosti pre strednú hodnotu pomeru ako obdĺžniky. Vertikálna súradnica dát je mierne roztrasená, čo je bežný postup ako zamedziť "zliatiu" symbolov s takmer rovnakou horizontálnou súradnicou. Ako je očividné už z grafu, naše dáta zatiaľ nesvedčia o významnom rozdiele medzi mužmi a ženami. Formálne: nepárový dvojvýberový t-test pre rovnosť stredných hodnôt pre pravú ruku dáva zatiaľ p hodnotu približne 0,7 a pre ľavú ruku približne 0,9. Na zistenie signifikantného rozdielu (ak existuje) potrebujeme ešte pomerne veľa dát. Zapojte sa!

Každopádne už teraz je jasné, že rozdiel medzi mužmi a ženami je veľmi malý (aj keď možno zistiteľný pri veľkom súbore ľudí) a určovať pohlavie len na základe pomeru dĺžok prstov je skoro ako určovať ho hodením mincou.

Intervaly spoľahlivosti v prieskumoch verejnej mienky

2009-05-22T14:22:00.019+02:00

S potešením konštatujem, že agentúra FOCUS ku prieskumu momentálnej podpory politických strán uvádza okrem samotných percentuálnych odhadov aj intervaly spoľahlivosti. Rozhodol som sa preto, že stručne popíšem o čo ide.

Predstavme si, že máme škatuľu, v ktorej je veľmi veľký počet farebných guliek, pričom nás zaujíma pomer p, koľko z týchto guliek je červených. (Pre prieskumy môže "škatuľa" znamenať rozsiahly reprezentatívny zoznam oprávnených voličov a "červené guľky" môžu byť povedzme tí voliči, ktorí by momentálne volili stranu SMER.)

Pri obrovskom počte guliek nie je mysliteľné, aby sme preskúmali farbu každej z nich. Takže vykonáme len jednoduchý náhodný výber relatívne malého počtu guliek (tento počet, nazývaný tiež rozsah výberu, si označíme n), zistíme koľko je z nich červených (nech je to k) a výsledný pomer (t.j. hodnotu k/n) prehlásime za náš odhad neznámej hodnoty p. Interval spoľahlivosti (IS) vyjadruje rozsah, v ktorom "s veľkou mierou istoty" leží skutočný pomer p, ktorého je k/n len často nepresným odhadom. Pokúsme sa vysvetliť tento intuitívny popis IS matematicky presnejšie.

Približný 95 percentný interval spoľahlivosti pre hodnotu p vypočítame ako k/n plus mínus δ, kde

V predchádzajúcom vzorci je p so strieškou náš odhad hodnoty p, t.j. k/n a konštanta 1,96 je takzvaná kritická hodnota normálneho rozdelenia. Hodnota δ sa v angličtine nazýva "margin of error" a v slovenčine ju budem nazývať hraničná chyba.

Odhad k/n je teda stredom IS a čím je väčšie n, t.j. čím je väčší rozsah nášho náhodného výberu, tým je menšia hraničná chyba a užší výsledný interval. To súhlasí s našou intuíciou ako asi by sa mal IS správať. Ale prečo práve takýto vzorec? A čo vlastne znamená číslo 95?

Predstavme si, že náš experiment s vybratím n guliek zopakujeme mnohokrát a zakaždým použijeme hore uvedený vzorec pre konštrukciu IS. Potom približne v 95 percentách prípadov bude skonštruovaný interval obsahovať skutočný pomer p červených guliek v škatuli. Presvedčiť sa o platnosti predchádzajúcej vety si vyžaduje absolvovať základný kurz teórie pravdepodobnosti (aspoň po centrálnu limitnú vetu), ale pochopiť význam IS je možné aj bez toho. Ešte raz inými slovami: 95 percentný IS je interval vypočítaný metódou, ktorá dáva v 95 percentách prípadov jej použitia interval obsahujúci hodnotu p skutočného podielu.

Predpokladajme napríklad, že zo škatule sme vybrali presne 1000 guliek. Potom hraničná chyba v závislosti od odhadu k/n je zobrazená na nasledovnom grafe (všetko som vynásobil číslom 100, t.j. aj odhad neznámeho pomeru p aj hraničná chyba je na grafe uvedená v percentách):

Napríklad ak by v našom náhodnom výbere bolo presne 40 percent červených guliek, je hraničná chyba približne 3 percentá a 95 percentný interval spoľahlivosti pre skutočné percento červených guliek v šaktuli je 37 až 43. Ak by spomedzi vybratých guliek bolo 20 percent červených, bola by hraničná chyba približne 2,5 percenta a 95 percentný IS by bol 17,5 až 22,5.

Čo sa týka prieskumov verejnej mienky, tak je situácia samozrejme trochu zložitejšia. Po prvé, prieskumná agentúra môže použiť sofistikovanejší výber respondentov ako je len obyčajný náhodný výber; napríklad môže robiť takzvaný stratifikovaný náhodný výber, ktorý odhady spresní. A po druhé, je pravdepodobné, že intervaly spoľahlivosti bude agentúra počítať exaktnou metódou a nie len našim jednoduchým, avšak len približným vzorčekom.

Každopádne intervaly spoľahlivosti uvedené v správe agentúry FOCUS s počtom odpovedajúcich respondentov n=709 sú prakticky identické s tým, čo by sme dostali použitím našej metódy (okrem uvedeného intervalu spoľahlivosti pre Slobodné Fórum, kde agentúra zjavne urobila chybu).

Poznámka: Všimnite si, že krajná chyba, t.j. vlastne presnosť nášho odhadu, nezávisí od počtu všetkých guliek v škatuli, resp. od počtu všetkých potenciálnych voličov (kvôli vrtákom: predpokladáme náhodný výber s vrátením, čo je však prakticky identická situácia ako náhodný výber bez vrátenia ak je rozsah výberu o niekoľko rádov menší ako veľkosť základnej populácie). Takže aj ak by bolo potenciálnych voličov milión, aj sto miliónov, aj sto miliárd, náhodný výber rozsahu 1000 nám poskytne zakaždým rovnako presný odhad o podiele potenciálnych voličov strán.

Veľký a malý trojuholník

2009-05-19T10:44:00.007+02:00

Prednedávnom som natrafil na jeden príjemný a pomerne slávny príklad zo stredoškolskej geometrie, ktorý ma dosiaľ akosi obišiel. Možno ho nepoznáte a jeho riešenie Vás poteší tak ako potešilo mňa:

Majme "veľký" rovnostranný trojuholník ABC, pričom na stranách AB, BC, CA sú body D, E, F zakreslené tak, že |AD|/|AB|=|BE|/|BC|=|CF|/|CA|=1/3, kde symbol |.| označuje dĺžku úsečky. Prienik trojuholníkov ABF, BCD a CAE nazvime "malý" trojuholník. Aký je pomer plôch "malého" a "veľkého" trojuholníka?

Správna odpoveď je samozrejme len jediná, ale spôsobov ako sa k nej dopracovať je veľa. Som zvedavý, kto z Vás príde na ten najkrajší.

Odkazy 04/2009

2009-05-15T09:07:00.003+02:00

Posledné tri týždne boli pre mňa mimoriadne náročné. Okrem vyučovania som sa musel venovať napríklad príprave záverečných projektov a písomiek, diplomovkám, ŠVOČke, mal som prednášku na TU v Mníchove a zakrátko aj na UK v Prahe. Hneď po návrate zo zahraničia som dostal silný zápal priedušiek a nemal som veľkú chuť písať príspevky na blog; preto tá dlhá prestávka. Situácia sa však rýchlo mení k lepšiemu.

Čo sa týka internetu, v poslednej dobe som mal len málo času browsovať, ale napriek tomu som natrafil na jeden veľmi zaujímavý projekt: BigThink, ktorý prezentuje pozvaných hostí vo forme videozáznamov ich odpovedí na rozličné otázky, pričom tieto odpovede sú adresované priamo divákovi (a nie publiku ako je to napríklad v TED talks). Výsledkom je dojem neformálneho, skoro až osobného rozhovoru. Navyše, k väčšine videí je naeditovaný prepis, čo môže pomôcť tým, ktorí sú si nie vždy celkom istí pochopením hovorenej angličtiny. Ľudí prezentujúcich svoje názory na stránkach BigThink je pomerne veľa, takže som sa pokúsil o výber len tých, ktorí ma z rôznych dôvodov oslovili najviac (to samozrejme neznamená, že s nimi vo všetkom súhlasím. Inak všimnite si pod videami odkaz "Next idea", čo Vám umožní postupne si prezrieť všetky príspevky daného človeka.)

Stephen Pinker: Mediálne veľmi známy profesor psychológie na Harvarde a autor bestsellerov ako napríklad The Language Instinct, alebo How the Mind Works. Ak Vás Pinkerove názory zaujmú, môžem Vám požičať jeho knihy Words and Rules a The Stuff of Thought. (Mimochodom, Pinker je váženým členom klubu vedcov s bujnou hrivou.)

Daniel Gilbert: Ďalší profesor psychológie z Harvardu, ktorý sa stal širšej verejnosti známy ako autor knihy Stumbling on Happiness. Gilbert má pozoruhodnú kariéru; ešte ako teenager si založil rodinu a keďže túžil stať sa autorom science fiction, chcel na lokálnej škole navštevovať nejaký predmet vhodný pre začínajúcich spisovateľov. Jediný voľný kurz bol však už len z psychológie. A to bol začiatok jeho cesty až na vrchol toho, čo akademický psychológ môže dosiahnuť. (Gilbert nie je členom klubu vedcov s bujnou hrivou.)

Ray Kurzweil: Tak toto je naozaj veľmi zaujímavý chlapík. Vynálezca, milionár a futurista, držiteľ 16-tich čestných doktorátov a autor kníh ako The Age of Spiritual Machines, alebo The Singularity is Near, na motívy ktorej momentálne dokončujú film. Kurzweil verí, že sa môže dožiť obdobia, v ktorom budú stroje myslieť a ľudia budú takmer nesmrteľní; asi kvôli tomu prešiel na špeciálny program starostlivosti o svoje zdravie a okrem iného každý deň užíva 150 syntetických doplnkov výživy. Bohužiaľ, jeho technooptimizmus s ním zdieľa málokto.

Oliver Sacks: Mimoriadne príjemný pán s veľkým srdcom, povolaním neurológ, autor takých bestsellerov ako The Man Who Mistook His Wife for a Hat, alebo tiež Awakenings, podľa ktorého vznikol dokonca scenár filmu (podobne ako Kurzweil; Sacks má však len 11 čestných doktorátov). Jeho kniha An Anthropologist on Mars, ktorú Vám rád požičiam, je jednou z najlepších populárno-náučných kníh, aké som kedy čítal.

Jonathan Haidt: Profesor na Univerzite vo Virginii; predstaviteľ takzvanej pozitívnej psychológie. Haidt verí v skupinovú selekciu a z tohto pohľadu študuje rôzne aspekty ľudskej morálky. Jeho kniha The Hapiness Hypothesis sa mi natoľko páčila, som jej venoval aj samostatný blogový príspevok. Prečítajte si prvú kapitolu z tejto knihy a ak sa Vám zapáči, zastavte sa u mňa a ja Vám tú knihu požičiam celú.

Dosť bolo filozofických úvah a vedy, dajme si na záver niečo ľahšie, napríklad toto krátke video o možno najkurióznejšom futbalovom zápase v histórii. (Dočítal som sa o ňom v peknej knihe J.D.Barrowa "100 essential things you didn't know you didn't know".) Video na YouTube je skrátené, takže sa pokúsim podrobnejšie vysvetliť, čo sa v danom zápase stalo: Na postup do ďalšej fázy súťaže potreboval Barbados vyhrať nad Grenadou o dva góly; v opačnom prípade by postúpila Grenada. Túto veľmi jednoduchú situáciu však značne skomplikovalo pravidlo, že v prípade remízy v normálnom hracom čase sa bude hrať predĺženie, v ktorom sa "zlatý gól" počíta za dva góly. Dlho vyhrával Barbados 2:0, avšak krátko pred koncom dala Grenada gól na 2:1. Hráči Barbadosu si uvedomili, že tretí gól už asi nestihnú dať a najlepším riešením je streliť si vlastný gól a potom sa pokúsiť vyhrať v predĺžení. Po vlastnom góle Barbadosu však hráčom Grenady rýchlo napadlo, že postup si zabezpečia tým, že si tiež strelia vlastný gól. To si však okamžite uvedomili aj hráči Barbadosu a do konca zápasu mali diváci možnosť sledovať veľmi kurióznu snahu Grenady dať si vlastný gól, čomu sa futbalisti Barbadosu snažili intenzívne brániť. Ak by si Grenada dala vlastný gól, museli by sa Barbadosania veľmi poponáhľať, aby si stihli dať ďalší vlastný gól, čo by sa im nemuselo podariť, lebo Grenada by im v tom zrejme bránila... Nakoniec však Barbados udržal v normálnom hracom čase remízu, v predĺžení dal zlatý dvojgól a postúpil. :-)

Osobnosti slovenskej matematiky: Pavel Brunovský

2009-04-23T08:00:00.005+02:00

(Po kliknutí na obrázok sa oznam zobrazí v plnom rozlíšení.)

Tip

2009-04-19T22:31:00.015+02:00

V rámci svojej prípravy na počítačovú štatistiku som práve dočítal veľmi poučnú pedagogickú knihu "Teaching statistics - a bag of tricks" od Andrewa Gelmana a Deborah Nolanovej. Z tejto a aj z iných kníh týkajúcich sa vyučovania som si uvedomil, že pre kvalitnú prednášku je najdôležitejší eminentný záujem na tom, aby si študenti z prednášky odniesli čo najviac a hlavne veľmi dôkladná pravidelná príprava. Keď som si pomyslel na niektorých vyučujúcich, ktorých som osobne poznal, musel som sa len trpko pousmiať. (Hovorím však skôr o výnimkách, aspoň teda u nás na matfyze.) Ale nie o tom som chcel písať. Jedna aktivita so študentami, ktorá sa v tejto knihe spomína, ma inšpirovala k nasledovnej úlohe:

Hodím súčasne dvadsiatimi jednoeurovými mincami. Ak sa Vám podarí vopred uhádnuť, na koľkých z týchto mincí padne znak, tak Vám všetky mince, na ktorých padol znak, darujem, len si po ne musíte ku mne domov prísť. Ak by som predchádzajúce dve vety myslel vážne (čo nemyslím :-), aký počet padnutých znakov by ste si zvolili ako svoj tip?

Táto úloha je síce veľmi ľahká, ale ak by sa Vám zdala až triviálna, tak ste asi nevzali do úvahy všetky jej "praktické" aspekty.

Odkazy 03/2009

2009-04-15T19:14:00.004+02:00

V treťom tohtoročnom vydaní odkazov na zaujímavé stránky by som Vás chcel upozorniť predovšetkým na spustenie portálu Tricky, ktorého zámerom je vybudovať encyklopédiu metód riešenia matematických úloh. Tento projekt by som za normálnych okolností považoval za nerealisticky ambiciózny, ak by za ním nestál sám Timothy Gowers. Pouvažujem, či aj ja niečo nepridám, napríklad o metódach riešenia úloh z pravdepodobnosti.

Prednáška Bonnie Basslerovej o komunikácií populácií baktérií bola na diggu označená za "najlepšiu akú ste kedy mali možnosť vidieť". Hoci je toto konštatovanie asi trochu prehnané, je naozaj pozoruhodné s akou zanietenosťou a citom pre vhodné metafory dokáže Bonnie Basslerová rozprávať o zdanlivo nudnej téme. Jednoznačne stojí za to vidieť. (Inak v poslednej dobe mávam pomerne často pocit, že keby som sa bol býval dal na genetiku, prípadne mikrobiológiu, tak by sa mi to tiež veľmi páčilo :-)

Krátky, ale zaujímavý článok o ilúzii ''dutej masky'' sa objavil na vedeckom blogu portálu Wired. Ilúzia dutej masky spočíva v tom, že keď sa pozriete na masku z ktorejkoľvek strany, zakaždým Vám bude pripadať akoby sa "pozerala" smerom na Vás a nikdy nie opačným smerom. Neviem ako Vy, ale ja nie som schopný túto ilúziu vedome potlačiť. Z istého hľadiska je to však dobre; podľa toho, čo píšu v článku, mám aspoň určitú záruku, že netrpím schizofréniou (a ani nie som naložený v liehu, ehm).

Binárny kruh

2009-04-09T15:33:00.018+02:00

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

Dysonovo číslo

2009-04-03T14:27:00.007+02:00

Pred niekoľkými dňami sa v The New York Times objavil obsiahly a zaujímavý článok o žijúcej legende teoretickej fyziky Freemanovi Dysonovi. Hoci samotný článok sa zameriava predovšetkým na Dysonove kontroverzné vyhlásenia týkajúce sa globálneho otepľovania, k napísaniu tohto blogového príspevku ma vyprovokovala jedna nasledovná krátka pasáž, ktorá s globálnym otepľovaním nemá nič spoločné:

... A group of scientists will be sitting around the cafeteria, and one will idly wonder if there is an integer where, if you take its last digit and move it to the front, turning, say, 112 to 211, it’s possible to exactly double the value. Dyson will immediately say, "Oh, that’s not difficult," allow two short beats to pass and then add, "but of course the smallest such number is 18 digits long." When this happened one day at lunch, William Press remembers, “the table fell silent; nobody had the slightest idea how Freeman could have known such a fact or, even more terrifying, could have derived it in his head in about two seconds."

Vedeli by ste toto číslo nájsť aj Vy?

Hlasujte za najkrajšiu úlohu!

2009-03-28T16:20:00.008+01:00

Hlasovanie o najkrajšiu úlohu je už ukončené; pozri výsledky. Nasleduje pôvodný text príspevku.

Nadišiel čas aby ste spomedzi našich 12 súťažných úloh vybrali tú najkrajšiu. Po istom čase zvažovania som sa rozhodol, že Vaše hlasovanie urobím prostredníctvom e-mailu. Tým sa vyrieši viacero problémov, napríklad sa zamedzí možnosti anketového vandalizmu, duplicitného hlasovania a okruh hlasujúcich sa zúži len na tých, ktorí majú o naše úlohy skutočný záujem, čo dáva záruku zodpovedného posudzovania. Naviac, od každého hlasujúceho môžem e-mailom dostať oveľa viac "bitov" informácie ako z bežnej ankety, ktorú poskytuje blogspot.

Ak Vás teda naša súťaž zaujala, pošlite mi prosím e-mail s usporiadaným zoznamom maximálne 8 úloh, ktoré sú podľa Vás z uverejnenej dvanástky najlepšie. Prvá úloha v zozname dostane od Vás 10 bodov, druhá 8 bodov, tretia 6 bodov, štvrtá 5 bodov, ..., až maximálne ôsma 1 bod, presne tak ako na pretekoch F1. Úlohy, ktoré nebudú vo Vašom zozname získavajú 0 bodov. Ten, koho úloha od Vás získa najvyšší bodový priemer*, stane sa víťazom našej súťaže (a odo mňa dostane knihou).

Samozrejme, nikto okrem mňa sa nedozvie ako ste ktorú úlohu zaradili; zverejním len celkové počty bodov prvých troch úloh. Hlasovanie ukončíme 30.5.2009, prípadne akonáhle dostanem 18 hlasovacích e-mailov (ako veľkých cien v F1-tke; takýto záujem o hlasovanie však nepredpokladám :-)

*Ak si Ty sám/sama autorom/autorkou niektorej z úloh, môžeš samozrejme hlasovať tiež. Po počiatočných pochybnostiach ohľadom objektívnosti ohodnotenia svojej vlastnej úlohy som sa rozhodol pristúpiť na Peťov návrh, totiž že autor z hlasovania vynechá svoju vlastnú úlohu, ale aby nebol znevýhodnený samotným faktom, že hlasoval, celkové hodnotenie úlohy budem počítať ako priemerné hodnotenie danej úlohy neautormi.

PS: Pre jednoduchosť uvediem kompletný zoznam úloh, ktorý si môžete napríklad skopírovať do vhodného programu a tam myškou usporiadať:

Sto väzňov

Zapadajúce množiny

Problém lámání stébla

Dve fľaše

Prieskumná expedícia

Ako si zašnurovať topánky

Všetky uhly sú rovnaké

Stěhovací problém

Mount & Blade

Mravce na tyči

Pohľady

Biliardové gule

Teším sa na Vaše hlasy!

Zauzlený problém

2009-03-26T07:57:00.007+01:00

V prvom rade by som chcel poďakovať všetkým, ktorí sa zúčastnili nedávnej ankety. Jej výsledky nebudem podrobnejšie rozoberať, avšak musím poznamenať, že ma povzbudili a dozvedel som sa z nich dôležité informácie ohľadom ďalšieho smerovania blogu. Poďme ale k úlohe, ktorá sa vykľula z mojej sobotňajšej zábavy s kreslením v R-ku.

Na obrázku vyššie (kliknutím sa zväčší) máme zobrazené slučky z gumy. Ktoré z nich sú rovnaké v tom zmysle, že je ich možné dostať jednu z druhej len naťahovaním a deformovaním, nie však pretrhnutím a zliepaním?

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

2009-03-20T07:57:00.010+01:00

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

Odkazy 02/2009

2009-03-17T20:00:00.009+01:00

Massachusetts Institute of Technology, slávne MIT, poskytuje pre verejnosť veľké množstvo svojich študijných materiálov. Zaujímavé by pre Vás mohli byť napríklad videozáznamy prednášok z lineárnej algebry, úvodu do teórie algoritmov, alebo klasickej mechaniky. Drobná poznámka: všimnite si, že ako na Stanforde (viď minulé odkazy), tak aj na MIT používajú vyučujúci aj na relatívne nedávno zaznamenaných prednáškach klasickú tabuľu.

Poznámka 12.4.: Ak Vás prednášky zaujali, môžete si pozrieť aj tento link.

Februárový Scientific American Mind prináša veľmi zaujímavý článok o účinkoch placeba, ktoré občas spomínam aj na vyučovaní v súvislosti s randomizáciou slepých klinických skúšok. Ukazuje sa, že placebo efekt je výslednicou najmenej dvoch procesov. Prvý z nich, podmienený, je možné vyvolať aj na zvieratách a má vplyv na biologické deje mimo vedomia. Druhý proces, "expektačný", priamo ovplyvňuje sekréciu endogénnych opioidov a môže napríklad výrazne znížiť naše vedomé pociťovanie bolesti.

Pri príležitosti 200. výročia narodenia Darwina vybral National Geographic 7 najvýznamnejších objavov fosílií prechodných článkov podporujúcich teóriu postupnej evolúcie človeka z nižších foriem živočíchov. Od Neila Shubina, spoluobjaviteľa Tiktaalika - prvej z uvedených fosílií - som prednedávnom čítal knihu "Your Inner Fish". Pozrite si prednášku Neila Shubina v Clevelandskom múzeu prírodnej histórie a ak Vás zaujme, môžem Vám požičať aj spomínanú knihu.

Pohľady (súťažná úloha č.11)

2009-03-10T22:11:00.006+01:00

Jedenástu súťažnú úlohu nám poslal Jozef Gábik, študent 4. ročníka FMFI UK:

V kruhu je rozostavených n ľudí. Na povel si každý z nich úplne náhodne zvolí jedného človeka, ktorému sa pozrie do očí. Označme ako p(n) pravdepodobnosť, že sa nejaké pohľady stretnú. Aká je limita pravdepodobností p(n) pre n idúce do nekonečna? (T.j. aká je pravdepodobnosť p(n) pre "veľmi veľký" počet ľudí n?)

Táto pekná úloha je Jozefov vlastný nápad; inšpiráciou mu bola skutočná hra skautov v jeho zbore. Vzorové riešenie nemáme, takže som zvedavý, kto z Vás vypočíta správny výsledok ako prvý.

Alino a piškóty

2009-02-28T12:50:00.009+01:00

Náš pes Alino má veľmi rád návštevy, no ešte radšej má piškóty. Keď príde návšteva, existuje len jediný spôsob ako sa ho aspoň na čas zbaviť: rozhádzať mu po zemi piškóty a kým ich všetky nepožerie, je od neho pokoj.

Avšak piškóty nám už zostali iba tri. Ako ich máme rozložiť do štvorcovej miestnosti s rohmi ABCD, aby trvalo Alinovi čo najdlhšie, kým ich všetky zožerie? Predpokladáme, že Alino začína svoju mlsnú prechádzku pri nás v rohu A a kráča konštantným tempom vždy priamou cestou k najbližšej piškóte. Ak sú dve piškóty rovnako vzdialené, vyberie si Alino úplne náhodne, za ktorou z nich sa vyberie. Zožratie piškóty mu trvá, samozrejme, zanedbateľne krátky čas. Keď už nie je čo jesť, vráti sa naspäť do rohu A, aby nás mohol opäť obšťastňovať.

Možno mi neuveríte, ale moji rodičia majú naozaj psa s menom Alino (bordeauxka doga na obrázkoch) a metódu rozhadzovania piškót skutočne občas používajú. Jedná sa teda o problém aplikovanej matematiky. :-)

Magická hviezda

2009-02-25T19:10:00.007+01:00

Nemám už dnes síl seriózne pracovať a preto som sa rozhodol, že k rybám pridám ešte jednu matematickú úlohu úplne iného charakteru; na jej vyriešenie stačí vedieť sčitovať čísla od 1 do 12 :-). Mám ju z príjemnej a čerstvej knihy "Cabinet of Mathematical Curiosities" od známeho profesora z Warwicku Iana Stewarta.

Do krúžkov na obrázku doplňte čísla od 1 do 12 (každé z týchto dvanástich čísel je potrebné použiť práve raz), aby bol súčet každej štvorice čísel spojených úsečkou a taktiež šestice čísel na vonkajšej kružnici práve 26.

Poznámka 3.3.: V komentároch nájdete viaceré možné riešenia a iné zaujímavosti týkajúce sa tejto a podobných úloh.

Ryby II

2009-02-25T06:58:00.008+01:00

Predpokladajme, že hmotnosť ulovených rýb má rovnomerné náhodné rozdelenie na intervale 0kg až 1kg, rovnako ako v prvom príklade o rybách. Tentoraz však pozmeníme pravidlo ukončenia rybačky:

Budem chytať ryby až dovtedy, kým neulovím prvú rybu, ktorá je ľahšia ako predchádzajúca ulovená ryba. (Domov si odnesiem aj túto ľahšiu rybu.) Aká je stredná hodnota počtu rýb, ktoré takto ulovím? Aká je stredná hodnota celkovej hmotnosti rýb, ktoré si odnesiem domov?

S úlohami o strednej hodnote počtu ulovených rýb som sa prvýkrát stretol vo veľmi peknej knihe "Matematika náhody" od profesora Jiřího Anděla z MFF UK v Prahe. Otázky týkajúce sa strednej hodnoty celkovej hmotnosti ulovených rýb sa však v tejto knihe neriešia, zrejme z toho dôvodu, že sú ťažšie. Ja sám ich neviem presvedčivo zodpovedať bez použitia dosť pokročilého aparátu teórie pravdepodobnosti. Kto ich zodpovie pomocou elementárnej matematiky, má môj obdiv.

Nové ankety

2009-02-21T11:17:00.011+01:00

Poznámka 26.3.: Anketu sme už uzavreli. Jej výsledky si môžete pozrieť na tomto odkaze.

Na blogu QED je návštevníkov pomerne veľa; pred rokom som mal v priemere tak 50 návštev denne, posledné mesiace je to už približne 80. Zdá sa však, že väčšina ľudí sem zavíta jednorázovo, alebo dokonca tak trochu omylom. (Minule sa niekto dostal na QED po tom, čo si dal vyhľadávať slová blázon+matfyz. Ale toto práve omyl ani veľmi nebol. Omylom sa sem dostali skôr tí, ktorí vyhľadávali napríklad guličky+do+jazyka, alebo najnovšie+správy+z+bulváru.)

Rozhodol som sa preto urobiť malý prieskum Vašich názorov, ktorý by mohol pomôcť tento blog pre Vás trochu zatraktívniť.

V prvom formulári (pozri vpravo hore pod upútavkou na súťaž) sa Vás pýtam, ako často blog QED navštevujete. Ak ste tu už boli viackrát, vyplňte prosím aj druhý formulár, v ktorom sa Vás pýtam na Vaše celkové hodnotenie od A po Fx, ako na skúške. Prosím, nedávajte mi Fx len kvôli tomu, že nemáte radi matematiku. Hodnoťte skôr to, ako dobrý je tento blog pre tých, ktorí matematiku radi majú.

Najviac informácie môže priniesť tretí formulár; všimnite si, že v ňom môžete označiť viacero možností súčasne. Nezabudnite, že počet príspevkov mesačne z časových dôvodov nemôžem veľmi zvýšiť. (Nakoniec, keby som nerobil predovšetkým niečo iné ako písanie blogu, nemal by som veľmi o čom písať.) Takže napríklad nemá zmysel zaškrtnúť súčasne veľa políčok; ideálne tak okolo polovice.

Samozrejme, najlepšie ma usmerníte priamo komentárom k tomuto príspevku.

PS: Ak ste študentom matfyzu, vyplňte prosím aj anketu FMFI UK. Vám samotným, Vašim mladším spolužiakom a aj väčšine vyučujúcich Vaše hodnotenie, najmä to slovné, pomôže. Ale nezabudnite. Najúčinnejšia kritika je tá, ktorá je napísaná slušne a kultivovane. Urážlivé vyjadrenia ohľadom vyučujúcich môžu byť práve vodou na mlyn pre tých, ktorí by boli najradšej, keby sa Vaša (naša) anketa úplne zrušila.

Ryby

2009-02-17T14:23:00.012+01:00

Do ukončenia súťaže nám chýbajú už len dve úlohy, takže neváhajte a niečo pošlite; veď pekných matematických úloh je približne nekonečne veľa. Napríklad táto:

Rozhodol som sa, že budem chytať ryby (po jednej) až dovtedy, kým ich celková hmotnosť neprekročí 1kg. Aká je stredná hodnota počtu rýb, ktoré ulovím? Viem, že v mojom rybárskom revíre má hmotnosť ulovených rýb rovnomerné náhodné rozdelenie medzi 0 kg a 1 kg.

Poznámka 1: Stredná hodnota je "asymptotický priemer", t.j. to číslo, ku ktorému by sa blížil aritmetický priemer chyteného počtu rýb v prípade, že by som takýmto spôsobom a za rovnakých podmienok rybačku neustále opakoval. Rovnomerné náhodné rozdelenie medzi 0 kg a 1 kg znamená to, že pravdepodobnosť, že ulovená ryba bude mať menej ako m kg, je rovná presne m (pre m medzi nulou a jednotkou). Mal by som však dodať, že náš príklad nie je úplne triviálny a ak ste sa so základmi pravdepodobnosti a matematickej analýzy dosiaľ nestretli, tak sa Vám bude riešiť dosť ťažko. Simulačne sa však výsledok dá celkom spoľahlivo "uhádnuť".

Poznámka 2: Túto úlohu už údajne poznal Laplace, hoci formulácia s rybami je novšieho dáta.

Poznámka 3: Keď ukončíme súťaž o najkrajšiu matematickú úlohu, zorganizujem súťaž o najkrajší matematický obrázok. Čo vy na to?

Glimpse into the hyperspace

2009-02-13T18:25:00.010+01:00

... tak som nazval sériu obrázkov vygenerovaných krátkym programíkom v jazyku R, ktorého základnou myšlienkou je priemet špeciálnych kriviek v mnohorozmernom priestore do zvoleného dvojrozmerného podpriestoru. Sám som bol prekvapený, aké rôznorodé útvary je možné takouto technikou vytvoriť. Na YouTube som uploadol detailné video, ktoré si v nižšom rozlíšení môžete pozrieť aj tu:

Ak by mal niekto z Vás záujem implementovať program na vytváranie takýchto obrázkov ako samostatnú aplikáciu, zastavte sa za mnou a rád Vám použitý matematický princíp vysvetlím podrobnejšie.

Exponenciálna funkcia v komplexnej rovine

2009-02-06T21:23:00.010+01:00

Nasledovné video je animáciou funkcie

pričom t je čas v rozmedzí 0 až 2π. Všimnite si, že pre t=0 máme obyčajnú komplexnú exponenciálnu funkciu, zatiaľčo pre t=π sa jedná o funkciu exp(1/z), keďže exp(iπ)=-1.

Farbu som pre toto video volil tak, že reálna zložka zodpovedá "dimenzii h", čiže hue a komplexná zložka "dimenzii s", čiže saturation, v hsv parametrizácii farieb.

Prednáška na sústredení KMS

2009-02-04T08:14:00.004+01:00

Len veľmi stručne: Včera som bol spolu s kolegom Martinom Nieplom urobiť prednášku na sústredení KMS v škole v prírode "Patrovec" pri Trenčianskom Jastrabí. Na našom katedrovom serveri je voľne dostupná moja prezentácia. Je písaná pre stredoškolákov, čiže formálne nie celkom presne, ale napriek tomu Vás možno zaujme.

Mravce na tyči (súťažná úloha č.10)

2009-01-31T06:55:00.012+01:00

Desiatu súťažnú úlohu nám poslal Peťo Richtárik; pekné je na nej to, že riešenie môže napadnúť aj žiačika na základnej škole, no nemusí napadnúť ani profesora na univerzite. (Úloha má neznámy pôvod; Peťo sa ju dozvedel od kolegu.)

Na tyč dĺžky 10 metrov sme súčasne rozmiestnili 100 mravcov. Každý mravec sa pohybuje vpred rýchlosťou 1 meter za minútu. Ak dôjde mravec na niektorý z dvoch koncov tyče tak z nej spadne, avšak ak sa dva mravce zrazia, tak sa oba v okamihu otočia a pokračujú svojim konštantným tempom v opačnom smere. Otázka znie: Vedeli by ste určiť po akom čase spadne z tyče posledný mravec v závislosti od počiatočného smeru pohybu a umiestnenia mravcov?

Poznámka 1: Mravce považujeme za "body", t.j. akoby mali nulovú dĺžku. Tyč nemá žiadnu šírku (považujeme ju za idealizovanú úsečku), t.j. proti sebe idúce mravce sa nemôžu obísť, ale nutne sa musia po čase zraziť.

Poznámka 2: Predpokladáme, že na začiatku je každý mravec v inom bode tyče.

Odkazy 01/2009

2009-01-29T11:59:00.006+01:00

Prednedávnom ma upozornil Tomáš Bosák na stránku veľmi pekného projektu: verejne dostupné videozáznamy niekoľkých kompletných celosemestrálnych prednášok na Stanford School of Engineering, napríklad z programovania, robotiky, či Fourierovej transformácie. Okrem toho, že sa pri nich môžete veľa naučiť, je zaujímavé vidieť aj samotnú atmosféru výuky na jednej z najlepších vysokých školách sveta. Ja osobne som si pozrel pár prednášok Stephena Boyda, ktorého poznajú snáď všetci matematici pracujúci v oblasti konvexnej optimalizácie.

Skúškové obdobie sa pomaly končí a začína sa nový semester, v ktorom viacerí z Vás budú musieť dopísať svoje dosiaľ najväčšie dielo: bakalársku alebo diplomovú prácu. Ak sa Vám náhodou zazdá, že sa pri písaní práce riadite Twainovym heslom "Never put off till tomorrow, what you can do the day after tomorrow", nemusí sa jednať o lenivosť, ale o psychologicky komplikovaný fenomén prokrastinácie. Ak sa chcete o tomto potenciálne veľmi škodlivom probléme dozvedieť viac, najmä ako sa ho zbaviť, môžete začať s pekne napísaným článkom, ktorý uverejnil Scientific American.

Časopis Edge kladie každoročne jednu hĺbavú otázku približne stovke známych intelektuálov, najmä vedcov, ktorí sa neboja špekulácií o budúcnosti. Tento rok bola zvolená otázka "What will change everything" a odpovede, aspoň niektoré, naozaj stoja za prečítanie. Ak napíšete ako komentár vlastnú odpoveď, veľmi rád Vám v diskusii prezradím svoj názor.

A keďže na záver zvyknem dávať niečo odľahčujúce a odpovede na otázku časopisu Edge sú všetko iné len nie odľahčujúce, pridávam ešte odkaz na unikátnu fotografiu "fraktálnej" brokolice. Ako vlastne môže vzniknúť prirodzeným spôsobom objekt, ktorý je do takej miery sebepodobný?

Mount & Blade (Súťažná úloha č.9)

2009-01-24T13:45:00.006+01:00

Mount and Blade je názov počítačovej hry a súčasne 9. úlohy do našej súťaže, ktorú nám zaslal doktorand na matematickom ústave SAV Branislav Novotný. (To by človek nepovedal, čím všetkým sa Braňo ešte zaoberá okrem matematickej topológie a vyparovania čiernych dier :-)

Táto úloha je síce pomerne jednoduchá, ale pekné na nej je to, že je to úplne reálny problém, ktorý možno trápi viacerých hráčov hry Mount&Blade. Nie som si však vedomý toho, že by ju už niekto v nasledovnom znení formuloval.

Pri hraní M&B hráte za hrdinu, ktorý môže mať v partii okrem bežných vojakov aj tzv. hrdinov, ktorí sú mimo iného nesmrteľní ( hrdinovia predsa neumierajú :-), teda sa ich oplatí mať v partii čo najviac. Ich základným problémom však je, že majú medzi sebou spory a dokážu sa tak pohádať, že opustia partiu. Nasleduje tabuľka mien (ženy majú hviezdičku, lebo z mena je to ťažko poznať) a zoznam kto koho má, či nemá rád.

Ľahko si všimneme, že všetky vzťahy sú vzájomné. Definujme konflikt ako dvojicu, čo sa nemá rada a priateľstvo ako dvojicu čo sa má rada. Povedzme, že parta je maximálna, ak za daných podmienok má maximálny počet členov a medzi partiami s max. počtom členov má max. počet priateľstiev. Povedzme, že partia je bezkonfliktná, ak neobsahuje konflikt. Nech je udržateľná ak ľubovoľný člen je účastníkom najviac takého počtu konfliktov ako priateľstiev.

Treba nájsť všetky:
a) maximálne bezkonfliktné partie,
b) maximálne udržateľné partie,
c) maximálne udržateľné partie obsahujúce všetky ženy.

Stěhovací problém (Súťažná úloha č.8)

2009-01-19T08:21:00.005+01:00

Príspevok číslo 8 nám do súťaže poslal šachový skladateľ Ivan Skoba. Táto zaujímavá úloha sa na blogu QED už síce kedysi dávno objavila, avšak nevyvolala väčší záujem a riešenie nám dosiaľ chýba.

Jaké plošně největší těleso lze přestěhovat chodbou s pravoúhlým zalomením o jednotkové šířce? Projde čtverec (plocha = 1), dále půlkruh (1,57), ale stále to není největší těleso. Zdá se, že to bude část mezikruží (viz obrázek). Je to pravda? Jakou největší plochu můžeme chodbou přemístit?

Komentár I. Skoba: Úloha je převzatá – Technický magazín („Téčko“) někdy z přelomu 70.–80. let. V „Téčku“ vycházela na pokračování rubrika Matematické rekreace, ve které byly předkládány k řešení zajímavé úlohy, jejichž řešení bývalo uveřejňováno později. Tato je jednou z nich (je formulována po paměti).

Komentár R. Harman: Ja som sa s touto úlohou stretol prvýkrát predminulý rok v jednej peknej knihe o optimalizácii. Uvedené riešenie bolo označené ako "najlepšie známe", takže tento problém je dosiaľ nevyriešený. Zadanie úlohy teda môžeme chápať ako súťaž, kto nájde útvar s čo najväčšou plochou.

Slnečné kolektory: riešenie

2009-01-12T15:32:00.016+01:00

Problém "slnečné kolektory", ktorý som pre Vás vymyslel pred pár dňami, sa so silným ohlasom veru nestretol. Nuž, čím bližšie majú úlohy k praktickým aplikáciám, tým je obvykle ťažšie vyriešiť ich len pomocou dôvtipu; nie sú to už tie elegantné matematické hlavolamy z Gardnerovych kníh. Hľadanie riešenia "inžinierskych" úloh však má tiež svoje čaro a práve o tom by som Vás chcel tak trochu presvedčiť v tomto príspevku. Takže ako riešiť úlohu o optimálnej konfigurácii kolektorov?

Je zrejmé, že prvoradou úlohou je vedieť pre zadanú konfiguráciu a pre zadaný smer lúčov slnka vypočítať úhrnnú šírku kolektorov, na ktorú dopadá svetlo, t.j. veľkosť tieňa, ktorý by vrhala sústava štyroch kruhov s priemermi 1 meter a so stredmi v osiach kolektorov:

Napísať analytický predpis pre veľkosť tieňa v závislosti od polohy slnka je veľmi ťažké, avšak programík (napríklad pre prostredie R) na numerický výpočet je raz dva (procedúry, ako tá nasledujúca, môžete úplne kľudne preskočiť; sú tu len pre tých, ktorí by chceli vedieť podrobnosti):

shadow<-function (x,b){
# x ... uhol smeru kolmeho slnecne luce
# b ... suradnice osi v poradi x1,x2,x3,x4,y1,y2,y3,y4
h<-b[1:4]*cos(x)+b[5:8]*sin(x)
h<-sort(h); L<-h[4]-h[1]+1
for(i in 2:4) if(h[i]-h[i-1]>1){L<-L-(h[i]-h[i-1]-1)}
L }

Minimálnu veľkosť tieňa počas dňa potom určíme pomocou jednorozmernej minimalizačnej procedúry, ktorú nám poskytuje používaný software; v prípade programu R je to funkcia optimize. Treba si dať samozrejme pozor na to, že naša minimalizovaná funkcia môže obsahovať lokálne minimá; lepšie je preto rozbiť množinu smerov na viacero podintervalov, napríklad takto:

minshadow<-function(b) {
# b ... suradnice osi v poradi x1,x2,x3,x4,y1,y2,y3,y4
s<-seq(0,pi,length=11); res<-rep(Inf,10)
for(i in 1:10){
  res[i]<-optimize(f=shadow,interval=c(s[i],s[i+1]),b=b)$objective}
-min(res) }

Teraz už máme program, ktorým môžeme testovať "podozrivé" konfigurácie. Napríklad ak odskúšame konfiguráciu, ktorú navrhol Lev v komentári k predošlému príspevku, t.j. takú, v ktorej osi kolektorov ležia vo vrcholoch a v ťažisku najväčšieho rovnostranného trojuholníka, ktorý sa daného štvorca zmestí, dostaneme hodnotu minimálneho tieňa približne 2598 mm.

Je Levova konfigurácia optimálna? Aby som zodpovedal túto otázku, urobil som si krátky programík na maximalizáciu samotnej funkcie minshadow, ktorý je v zásade genetický algoritmus bez rekombinácie, čiže jednotlivé konfigurácie, čoby "jedinci populácie", produkujú potomkov "asexuálne", výlučne náhodnými mutáciami svojich vlastných polôh osí, aka "chromozómov". Všimnite si, aký je tento program doslova triviálny:

function(k,s,N) {
# k ... velkost populacie (volil som 500)
# s ... inicialna velkost mutacii (0.4)
# N ... pocet generacii (35)
cents.mut<-cents<-matrix(2*runif(k*8)-1,ncol=k,nrow=8)
vals<-rep(0,k)
for(i in 1:N){
  for(j in 1:k){vals[j]<-minshadow(cents[,j])}
  o<-order(vals); cents<-cents[,o]
  for(r in 1:k){
   cents.mut[,r]<-pmax(pmin(cents[,sample(1:k,1,prob=(k:1)^5)]
     +(s/i)*rnorm(8),1),-1)}
  cents<-cents.mut}
}

Polohy osí jednotlivých konfigurácií kolektorov som nechal vykreslovať červenými bodkami a spojnice medzi osami jednotlivých konfigurácií modrými spojnicami. Najlepšiu konfiguráciu v každej generácii som vyznačil čiernymi spojnicami a celý priebeh "vývoja" som zachytil na nasledovnom videu:

Iniciálna populácia je vygenerovaná úplne náhodne (rovnomerne na celom štvorci). Po úvodnej fáze divokého experimentovania sa vytvoria zhluky chromozómov podieľajúcich sa na "úspešných" konfiguráciách. Neskôr sa vytvoria oddelené "subpopulácie", z ktorých predposledná úplne vymizne až v 26. generácii. Ako vidíme, výsledná konfigurácia pôsobí akoby bola navrhnutá "inteligentne" a naviac je dostatočná na splnenie zadania našej pôvodnej úlohy; jej minimálna veľkosť je 2617 mm.

Všimnime si výslednú konfiguráciu bližšie. Tri body, označme si ich A,B,C, ležia veľmi blízko pri okraji štvorca a štvrtý bod, D, niekde vo vnútri. Ak by bola optimálna poloha bodu A presne (-1,-1), bodu B presne (1,0) a bodu C presne (-1,1), aká bude optimálna poloha bodu D? Netreba dlho uvažovať, kým si človek uvedomí, že minimálna veľkosť tieňa bude maximalizovaná vtedy, keď vzdialenosť bodu D od všetkých troch strán trojuholníka ABC bude rovnaká. To znamená, že bod D bude stredom do ABC vpísanej kružnice. Je už záležitosťou elementárnej matematiky dopočítať presnú polohu bodu D a výslednú hodnotu d minimálnej veľkosti tieňa:

Pochopiteľne, všetky štyri "rotácie" tohto riešenia sú takisto optimálne. Ak Vás tento problém zaujal, môžete sa ešte pokúsiť zodpovedať nasledovnú otázku: Existuje aj optimálna konfigurácia, ktorá nie je len rotáciou tej našej? ;-)

Slnečné kolektory

2009-01-07T22:29:00.009+01:00

Náš vesmírny koráb stroskotal na púštnej planéte X a to práve na takom mieste, na ktorom je neustále jasno a (tamojšie) slnko sa celý (tamojší) deň pohybuje tesne nad obzorom. K dispozícii máme 4 rovnaké slnečné kolektory širky 1 meter, ktoré z technických dôvodov musíme umiestniť všetky v rovnakej výške a naviac tak, aby osi týchto kolektorov boli na hranici, alebo vo vnútri štvorca 2 krát 2 metre. Po inštalácii sa budú kolektory otáčať za slnkom okolo svojej osi, no samotné osi už musia byť nehybné.

Nanešťastie, na vyslanie signálu SOS potrebujeme trvale dostatočne vysoký výkon kolektorov, ktorý dosiahneme len vtedy, keď počas celého dňa bude dopadať svetlo aspoň na 2,61 metra šírky kolektorov. To znamená, že štandardné postavenie kolektorov zobrazené na ilustračnom obrázku je nevyhovujúce, pretože dokonca až štyrikrát počas dňa si kolektory navzájom príliš tienia a svetlo dopadá spolu len na 2 metre šírky kolektorov.

Dá sa vôbec nájsť také rozmiestnenie kolektorov, aby sa trvale dosahoval požadovaný výkon?

Prechádzka po mriežke

2009-01-05T21:13:00.007+01:00

Do ukončenia našej súťaže chýba ešte 5 úloh. Neváhajte poslať aj niečo jednoduchšie (najmä vlastných nápadov tu zatiaľ veľa nemáme); napríklad také, ako je úloha, ktorá ma napadla dnes:

Máme pravouhlú mriežku zostavenú z n × m úsečiek, kde n aj m sú nepárne čísla. Ukážte, že nie je možné po nej prejsť všetkými uzlovými bodmi tak, aby sme každý z nich navštívili práve raz a nakoniec sa vrátili do toho uzlového bodu, v ktorom sme začali. T.j. chceme dokázať, že v príslušnom grafe neexistuje hamiltonovská kružnica.

Jeden neúspešný pokus o uzavretú hamiltonovskú prechádzku na mriežke 5 × 5 je znázornený na ilustračnom obrázku vľavo hore.

Poznámka 6.1.: V komentári nám misof formuloval zaujímavú úlohu s trochu podobným námetom (aj keď ťažšiu); neprehliadnite!

Všetky uhly sú rovnaké (súťažná úloha č.7)

2009-01-02T15:15:00.006+01:00

Prvý tohtoročný príspevok na blog QED a súčasne siedmu úlohu do našej súťaže napísal Mišo 'mišof' Forišek. Táto úloha je, ako píše Michal, "matematický folklór" a autor nie je známy.

Ak by ste to nevedeli, všetky uhly sú rovnaké a matematika nefunguje. Aby sme si to dokázali, ukážeme, že 90° uhol je rovnako veľký ako 100°. Začneme tým, že si zostrojíme štvorec ABCD. Teraz zvolíme bod E mimo štvorca tak, aby mal uhol DAE 10 stupňov a aby platilo |AE|=|AB|. Teraz zostrojíme osi úsečiek AB a CE, nazveme ich p a q. Tie sa zjavne pretínajú, ich priesečník označíme F.

Celá situácia vyzerá nasledovne:

Všimnime si teraz trojuholníky FAE a FBC. Zjavne platí |FA|=|FB|, lebo F leží na osi AB. Tiež zjavne platí |FC|=|FE|, lebo F leží na osi CE. No a platí aj |AE|=|BC|, lebo E sme zvolili tak, aby jeho vzdialenosť od A bola rovná strane štvorca. Teda podľa "vety SSS" sú tieto dva trojuholníky zhodné.

Keďže sú trojuholníky FAE a FBC zhodné, sú uhly FAE a FBC rovnaké. Pre veľkosti uhlov FAE a FBC platí: |∠FAE|=|∠FAB|+100, |∠FBC|=|∠FBA|+90. Keďže |∠FAE|=|∠FBC|, tak |∠FAB|+100°=|∠FBA|+90°.

Lenže, ako sme už povedali, |FA|=|FB|, a teda trojuholník FAB je rovnoramenný. Potom ale |∠FAB|=|∠FBA|, a preto 100°=90°, q.e.d.

Kde, ak vôbec niekde, je chyba?

Decembrové odkazy

2008-12-31T22:07:00.003+01:00

Aj v decembri sa do výberu pre mňa najzaujímavejších odkazov dostalo najnovšie číslo SciAm-u, ktoré je tentokrát zamerané na evolučnú teóriu. Rok 2009 sa bude niesť v znamení 150. výročia publikovania Darwinovho prevratného diela "On the Origin of Species" a preto sa s článkami a diskusiami ohľadom evolučnej teórie budeme asi stretávať častejšie.

Keď som na Wikipedii uvidel fotografiu neupraveného Terryho Taa v sivom tričku, spod ktorého vykúka biele tielko, ihneď mi bol veľmi sympatický :-) Na stránkach Sydney Morning Herald si môžete prečítať článok, ktorý sa sústredí na Terryho predovšetkým ako na supergeniálne dieťa. Pozoruhodné je, že jeden z jeho bratov má autizmus, s čím podľa mňa môžu súvisieť Terryho extrémne predpoklady na matematiku. V súčasnosti je už Terence Tao jedným z najslávnejších matematikov sveta, no napriek tomu venuje svoj čas aj písaniu blogu. To je pre mňa nepriamym, ale veľmi silným argumentom, že má zmysel keď vedec píše nielen pre veľmi úzku skupinu špecialistov, ale aj pre širšie spektrum čitateľov.

Počet galaxií vo vesmíre sa odhaduje na minimálne 100 miliárd, z ktorých každá obsahuje milióny až miliardy hviezd. Plne intuitívne uchopiť veľkosť týchto čísiel nám môže pomôcť veľmi pekný dokument s názvom "Najdôležitejšia fotografia, aká bola kedy urobená". Predstava takto obrovského vesmíru aspoň mňa samého napĺňa komplikovaným pocitom, aká malá je naša planéta svojim rozmerom, no aká je dôležitá svojim významom, aspoň teda v prípade, ak je v celom vesmíre jedinou planétou, na ktorej sa zrodil vedomý život, čo zatiaľ nemôžeme úplne vylúčiť.

Uvažovanie nad najhlbšími vedeckými otázkami vedie človeka nutne k určitej forme spirituality, či už teistickej, alebo ateistickej. Carl Sagan, ktorému je uvedený dokument venovaný, to vyjadril nasledovne:

When we recognize our place in an immensity of light years and in the passage of ages, when we grasp the intricacy, beauty, and subtlety of life, then the soaring feeling, that sense of elation and humility, is surely spiritual.

A keďže je dnes zhodou okolností Silvester, tak tento príspevok využijem na to, aby som Vám všetkým poprial úspešný nový rok, plný zážitkov z poznania, aký úžasný je svet v ktorom žijeme.

Úlohy pod stromček

2008-12-25T09:55:00.008+01:00

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)

2008-12-11T16:19:00.010+01:00

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)

2008-12-07T23:09:00.010+01:00

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)

2008-12-04T07:51:00.007+01:00

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

2008-12-01T12:31:00.008+01:00

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.