Jedenástu súťažnú úlohu nám poslal Jozef Gábik, študent 4. ročníka FMFI UK:V kruhu je rozostavených n ľudí. Na povel si každý z nich úplne náhodne zvolí jedného človeka, ktorému sa pozrie do očí. Označme ako p(n) pravdepodobnosť, že sa nejaké pohľady stretnú. Aká je limita pravdepodobností p(n) pre n idúce do nekonečna? (T.j. aká je pravdepodobnosť p(n) pre "veľmi veľký" počet ľudí n?)
Táto pekná úloha je Jozefov vlastný nápad; inšpiráciou mu bola skutočná hra skautov v jeho zbore. Vzorové riešenie nemáme, takže som zvedavý, kto z Vás vypočíta správny výsledok ako prvý.
Hovoris, ze uplne nahodne? Ze pohlavie a pripadna pritazlivost nehraju ziadnu rolu? ;-)
OdpovedaťOdstrániť:-) To, že si každý vyberá na koho sa pozrie úplne náhodne, je skutočne značne nerealistický predpoklad v každej "normálnej" skupinke ľudí. To by bolo splnené len vtedy, ak by si ľudia nejako losovali na koho sa pozrú.
OdpovedaťOdstrániťAk by mal nejaký echt matfyzák nejasnosti, uvediem pre neho "zrozumiteľnejšie" ekvivalentné zadanie úlohy:
Nech M_n je množina {1,...,n} a nech H_n je systém všetkých takých funkcií f:M_n->M_n, že pre každé x z M_n platí f(x)!=x. Nech F_n je náhodná funkcia s rovnomerným rozdelením na množine H_n a nech p_n je pravdepodobnosť udalosti, že F_n(F_n(x))=x pre nejaké x z M_n. Nájdite limitu postupnosti p_n pre n idúce do nekonečna. :-)
jaj, taaaak. uz chapem.... :-D
OdpovedaťOdstrániťTipol by som, že tá pravdepodobnosť ide k nule.
OdpovedaťOdstrániťrasťo: Keď sa človek zameria na fakt, že pre konkrétneho človeka je pravdepodobnosť opätovania pohľadu 1/(n-1), tak sa môže zdať, že p(n) pôjde k nule. Avšak tomu, kto si uvedomí len to, že zvyšujúci počet ľudí zvyšuje počet potenciálnych dvojíc, sa môže zdať naopak, že p(n) pôjde k jednej. Správny výpočet musí zohľadňovať obe tieto "tendecie" a na prvý pohľad je podľa mňa vyložene nejasné, či niektorá z nich preváži, alebo či sa nejako vykompenzujú a limitná pravdepodobnosť bude niekde medzi nulou a jednotkou.
OdpovedaťOdstrániťJa výsledok poznám a nie je až také triviálne sa k nemu dopracovať.
No ja som sa na to pozrel asi príliš zľahka - keď zrátame uhlopriečky a strany v n-uholníku zistíme, že je to spolu n(n-1)/2 úsečiek. Každá taká úsečka by mohla byť "dvojica" ľudí, ktorých pohľady sa stretli.
OdpovedaťOdstrániťTakže kým počet ľudí rastie lineárne, počet možných "dvojíc" rastie kvadraticky. Pre tých n ľudí je preto stále ťažšie "trafiť sa".
Preto som tipoval, že v limite sa pravdepodobnosť bude rovnať nule...
rasťo: Moja intuícia hovorí skôr toto: Počet potenciálnych dvojíc ľudí, ktorí sa môžu stretnúť pohľadom, rastie kvadraticky. Na druhej strane pravdepodobnosť, že sa konkrétna dvojica pohľadov stretne, klesá kvadraticky. Je to niečo také ako keby si hádzal rádovo n^2 krát kockou, pre ktorú je pravdepodobnosť padnutia šestky rádovo 1/n^2. Takže čo sa deje s pravdepodobnosťou, že niektorá dvojica ľudí sa pozrie na seba (resp. že padne aspoň raz šestka), je bez podrobnejšej analýzy vyložene nejasné.
OdpovedaťOdstrániťIntuícia je veľmi užitočná aj v matematike, ale niekedy nás skôr pomýli. (Typický prípad, v ktorom sa intuícia väčšiny ľudí a pravda úplne rozchádzajú, je Banachov-Tarskeho paradox.)
Napísal som si program a celkom to bolelo. Mám výsledky do 140 (pravdepodobnosť, že sa pohľady nestretnú je p(50) = 0.594004, p(100) = 0.600368, p(140) = 0.602149). Zdá sa, že to konverguje k tomu 0.60... Ďalšie výsledky budú, keď program zrýchlim a niektoré vzorce prepíšem na numericky stabilnejšie. Postup aj program pošlem neskôr, teraz musím ísť hrať stolný futbal.
OdpovedaťOdstrániťLukáš: Tie numerické výsledky sú už dosť blízko riešeniu. (Až na to, že v zadaní je p(n) pravdepodobnosť, že sa nejaké pohľady stretnú a Tvoje p(n) je pravdepodobnosť, že sa žiadne nestretnú, ale to je prakticky jedno).
OdpovedaťOdstrániťTým som vlastne prezradil, že výsledok nie je ani 0 ani 1.
Ako som sľúbil, moj program je tu: http://paste2.org/p/164311
OdpovedaťOdstrániťPodarilo sa mi dorátať až k hodnote pre 800 a bolo to 0.605771 (resp. komplement 0.394229).
Najprv zrátam počet ofarbení cyklov v grafe a potom zrátam počet ofarbení stromov, ktoré sú na týchto cykloch nalepené. Pri riešení využívam Cayleyho vzorec http://en.wikipedia.org/wiki/Cayley%27s_formula a zdravý rozum. Ono celý ten program sú len vnorené sumy, ktoré sa asi dajú zjednodušiť a niečo rozumné z toho vyjde. Neviem, či je toto správna cesta k riešeniu, ale tipujem, že nie :)
Napísal by som k tomu viac, ale treba mi diplomovku písať.
Lukáš: To číslo, ktoré si dostal, je už veľmi blízko k hodnote 1-riešenie. Tú presnú hodnotu nebudem prezrádzať, no dá sa vyjadriť v celkom peknom tvare obsahujúcom 2 konštanty, 1 základnú aritmetickú operáciu a jednu bežnú funkciu :)
OdpovedaťOdstrániťHmm, mne to vychadza 1/3.
OdpovedaťOdstrániťNajprv musim poznamenat to ze zo skoly som uz dost davno a preto predpokladam nejaku blaznivu chybu :)
Moja uvaha je asi taka - mam permutaciu ktora urcuje F_n - teda pohlady. Potrebujem zistit kolko je moznosti ze x_i a x_j sa na seba pozera -> to znamena ze F( j) = i a F( i) = j. Takze "zafixujem" si i a j. Vsetkych moznych permutacii ked mam zafixovane dane cisla je (n-2)! Vsetkych kombinacii i a j je (n nad 2). Takze ( n nad 2) * ( n - 2)! co je ( n * ( n - 1) * ( n - 2)!) / 2 = n!/2. Inak je uzasne pisat v texmode matematiku :) Teraz pristupi cast ktora si nepamatam ako sa vola - a dufam ze si jej princip pamatam dobre. Teda teraz potrebujem odpocitat pripad ked su dve dvojice, pripocitat ked su tri dvojice, odpocitat ked su styry dvojice, ... pre dve dvojice ( n nad 2) * ( ( n -2) nad 2) * ( n - 4)! = n!/4. Zaroven ak chcem pravdepodobnost tak potrebujem to vydelit poctom vsetkych moznosti - poctom vsetkych permutacii n - teda n!. Takto dostavam nekonecnu postupnost (ak n ide do nekonecna) 1/2 - 1/2^2 + 1/2^3 - 1/2^4 ... co sa da upravit na geometricku postupnost 1/4 + 1/4^2 + 1/4^3 ... To po dosadeni do vzorca dava 1/3.
Ale podla Vasho posledneho prispevku "dá sa vyjadriť v celkom peknom tvare obsahujúcom 2 konštanty, 1 základnú aritmetickú operáciu a jednu bežnú funkciu" - tak to mam asi zle :) kde je moja uvaha zla?
Hmm (standardny uvod odo mna :) )
OdpovedaťOdstrániťteraz mi doslo ze vsetkych moznosti nie je n! musim odpocitat vsetky take kde sa F(i) = i pre nejake i (teda clovek sa asi nemoze pozerat sam na seba :) Ale ked sa pozeram na Vas druhy prispevok tak to tam aj mate napisane :)
Rori: Tvoj postup je veľmi rozumný a sľubný, hoci je v ňom chybička, ako si správne poznamenal. Ten princíp, ktorý nevieš ako sa volá, je princíp zapojenia-vypojenia (inklúzie-exklúzie).
OdpovedaťOdstrániťDufam, ze nebudem plavat v temnych vodach :) ale skusim to takto - viem ze dismutácia, ci ako sa to vola po slovensky (teda ze v permutacii nie je ani jedno cislo na svojom mieste), ked ide do nekonecna ma pravdepodobnost 1/e. Potom mi ale vyplyva ze vysledok by mal byt e/3... (pocet moznosti ktorym som delil bol n! a teraz by mal byt n!/e)
OdpovedaťOdstrániťHmm :)
OdpovedaťOdstrániťPreco si uvedomim chybu az ked to odoslem ... Problem je ze v tom mojom poslednom rieseni zas neuvazujem o dismutaciach uz priamo pri fixovani. Lenze to potom mi ale vypadne e z vysledku (stale sme pri nekonecnach takze si to myslim mozem dovolit pouzivat to 1/e aj tam) a som spat pri 1/3. Len mam tusenie, ze to nie je az take lahke (delim dve nekonecna a tvarim sa ze to je 1).