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

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

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

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

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

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