27 júla 2009

Š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 En planét, ktoré sa takto zlikvidujú. Zaujíma nás najmä pomer En/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 En/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.

22 júla 2009

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

14 júla 2009

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 u1,...,un je ortonormálny systém vlastných vektorov matice H typu n × n a λ1,...,λ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!