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.

10 komentárov:

Rori povedal(a)...

Mam dve doplnujuce otazky :)

1. Nie som si isty ci spravne chapem uvod:
"Okolo istej hviezdy obieha na spoločnej obežnej dráhe n planét rovnakou rýchlosťou. 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."

Rozostavenie planet na kruznici je uplne nahodne?
"nie však vzdialenejšie planéty" - vzdialenejsie ako co?

2. Dalsia otazka potrebuje kontext :) Som uz daavno zo skoly a vasu stranku beriem ako moje v podstate jedine spojivko s matematikou ktora ma bavila a bavi - ale uz to bolo davno :) takze -
Co je to En? :)

Radoslav Harman povedal(a)...

Rori: Máš pravdu; moje zadanie treba upresniť. Myslel som to tak, že vzájomné vzdialenosti susedných planét sú rovnaké.

En je stredná hodnota počtu planét, ktoré sa navzájom zlikvidujú ak sa začína s n planétami (E je zaužívaný symbol pochádzajúci zo slova "expectation").

Bez väčšej matematiky si hodnotu En môžeš predstaviť takto: Povedzme, že nasimuluješ jeden priebeh, počas ktorého sa zlikviduje 88 planét. Potom opäť nasimuluješ a zlikviduje sa 82 planét, potom opäť a zničí sa 84 planét a tak ďalej. Priemer výsledných čísiel 88,82,84,... sa bude blížiť k nejakej konštante (podľa takzvaného zákona veľkých čísiel) a tá konštanta, to je práve En.

To, že nás zaujíma limita En/n sa dá približne formulovať tak, že chceme vedieť koľko percent planét sa "v priemere" vzájomne zlikviduje pre "obrovské" n.

Ruziklan povedal(a)...

Ako spravny hnidopich mam otazku: Co sa stane v pripade, ze na jednu planetu vystrelia dve jej vedlajsie planety v podstate naraz?
(Tusim vsak akosi, ze na limitny pripad toto nebude mat vplyv, takze picham len tak potichu...)

Pekny priklad.

Radoslav Harman povedal(a)...

Ruziklan: To je celkom dobrá otázka. Pre upresnenie by sme mali predpokladať, ž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.

Ondro Budac povedal(a)...

Co sa tyka tej brigady, uz vela neprogramujeme, ale skor zhrname co sme vymysleli do nejakeho paperu a este domyslame nejake "drobnosti" :)

Naspat k ulohe... Podarilo sa mi vyrobit nejaku postupnost "strednych hodnot" E_n, ktoru som asi neodvodil uplne formalne, ale limita E_n/n po numerickej stranke existovala a zhodovala sa so simulaciami.

Myslim, ze to bolo nejako takto:

E_{n+1}=2/n * (E_1+E_2+...+E_{n-1})

E_n znaci, kolko v priemere ostane planet, ked zaciname na zaciatku s n planetami. Potom pre n+1 planet, ktore su v rade mame n sposobov ako vybrat dvojicu, ktora sa zlikviduje. Ak sa zlikviduju planety i+1,i+2, tak zostane jeden rad planet dlzky i a druhy dlzky n-i-1, cize ostane v priemere E_i+E{n-i-1}. Nascitanim tychto priemernych hodnot a predelenim n dostaneme ten vzorec. Mozeme ho napisat aj v tvare

n*E_{n+1}=2*(E_1+E_2+...+E_{n-1})

Odcitanim tohoto vzorca pre n a n+1 (namiesto n vsade napiseme n+1) dostaneme

(n+1)*E_{n+2}-n*E_{n+1}=2*E_{n}

misof povedal(a)...

Hmm, bez toho aby som sa dlhsie zamyslal, mam otazku: ked sa robi ten vybuch, ako sa vybera ta dvojica ktoru odstranime?

Cakal by som, ze v povodnej Ondracovej verzii bolo ze vyberiem nahodnu susediacu dvojicu. Ale ta Radova verzia sa da chapat (aj) tak, ze vyberiem nahodneho diktatora a ten vyberie nahodneho ziveho suseda a napadne ho. Toto robi inu distribuciu -- totiz tie dvojice, kde uz jedna planeta ma len jedneho suseda budu pravdepodobnejsie ako tie dvojice ktore su este niekde v strede suvisleho useku.

Inak som pre tu prvu (uniformnu) verziu teda dospel k podobnemu ako uz Ondro napisal. Nech je prva znicena dvojica hociktora, vzdy dostaneme rad tvoreny N-2 planetami. No a ked si oznacime R_x ocakavany pocet toho co nam ostane z radu dlzky x, tak dostavame taku rekurenciu ze
R_x = \frac{1}{x-1} \cdot \sum_{l=0}^{x-2} ( R_l + R_{x-2-l} )
z coho upravou dostaneme nieco takmer rovnake ako ten prvy Ondrov vzorec. A potom riesenie E_n = R_{n-2}.

misof povedal(a)...

Inak vyzera to ze ta konstanta ku ktorej ide E_n/n = R_n / (n+2) je .13533528323661269189 = e^{-2} :)

Ondro Budac povedal(a)...

Fiha, to e^{-2} vyzera zakerne :) ako velmi to sedi?

misof povedal(a)...

uplne :)
http://paste2.org/p/357821

Radoslav Harman povedal(a)...

Ondro, misof: pekne chalani; formulujem tú domienku ohľadom konvergencie danej rekurencie k exp(-2) ako nový príklad.