Telepat II

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

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

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

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

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

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

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

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?