Dnes som pre Vás vymyslel trochu ťažšiu úlohu, ktorá pripomína problém o
Buffonovej ihle. Riešenie je celkom pekné a naviac táto úloha je môj vlastný nápad. Doslova sa čudujem, ako je možné, že som sa s ňou ešte nestretol v žiadnej z tých desiatok kníh z teórie pravdepodobnosti, ktoré používam. Kto príde ako prvý so správnym riešením (aj s odôvodnením; napíšte ho do komentárov, alebo mi pošlite mail), ten má u mňa pivo. Alebo aj tri.
Nech S je jednotková sféra, čím rozumieme povrch trojrozmernej gule s polomerom 1. Na S sú vyznačené dva body A a B, ktorých vzdialenosť je h. (Vzdialenosť počítame po povrchu sféry S, t.j. h je dĺžka sférickej úsečky AB.) Sféru S náhodne rozpolíme rovinným rezom na dve rovnako veľké hemisféry. Aká je pravdepodobnosť, že body A a B sa po vykonaní tohto rezu budú nachádzať na spoločnej hemisfére?
Bez ujmy na vseobecnosti A, B mozeme polozit na rovnik.
OdpovedaťOdstrániťRey iduce cez body A a B ignorujem, je ich malo.
Lubovolny poliaci rez gule okrem rezu cez rovnik pretina rovnik prave v dvoch bodoch. Zoberme ten leziaci na orientovanej polkruznici A->B.
Pravdepodobnost, ze takyto bod lezi na usecke AB je h/pi.
Neuniklo mi nieco? Ak nie, vies, ze pivo nepijem :-)
Ruziklan: Tak za zastav a pôjdeme na kofolu. Alebo aj tri. :-)
OdpovedaťOdstrániťTáto úloha je známa; dokonca veľmi známa vo vedeckých kruhoch v oblasti optimalizácie. Je to najmä kvôli článku Goemans-Williamson ['95]:
OdpovedaťOdstrániťhttp://www-math.mit.edu/~goemans/maxcut-jacm.pdf
V ňom autori (mimochodom Williamsonovi som robil TA na Cornelli, je to neskutočne skvelý chlapík) použijú techniku náhodnej nadroviny na dôkaz tvrdenia že problém MAX-CUT sa dá v polynomiálnom čase vyriešiť s aproximačným faktorom 0.87856 {tj efektívne sa dá vypočítať rez hranami grafu, ktorého hodnota, tj súčet váh rezaných hrán, je aspoň 87.8% maximálneho rezu}.
Pozrite si napr. slide č. 17 v tomto ppt súbore:
http://www.cs.tau.ac.il/~zwick/slides/SDP-UKCRC.ppt
Haha. Pozrel som ten článok aj slidy a našiel som tam formulky podozrivo podobné tým, ktoré mám napísané v práci na poznámkovom papieri :-) Som celkom prekvapený, že tieto moje uletené príklady majú nejaký súvis so súčasným výskumom v nejakej oblasti matematiky.
OdpovedaťOdstrániťKaždopádne, vyseparovať z tých materiálov riešenie (samozrejme aj s odvodením) druhej úlohy, o ktorú mi od začiatku išlo, by si od nezainteresovaného vyžadovalo zrejme viac námahy, ako nájsť to riešenie úplne samostatne. Takže Buffonov rez II je pre čitateľov QED stále aktuálny (a Jack Daniel's čaká :-)