zanimljiva matematika

[kurdi]

ma znaaammm. sala je bila. ja preuzela sa WSJ bloga i prevela original.samo jedna mala napomena: kad su ti takmicari malo manje glupi, pa se podele da prvih 50 otvara prvih 50 koverti...verovatnoca pobede je 50/100 * 49/99 * 48/98 *...*1/51=(50!^2)/100!a mozda i gresim.

pa jeste, jeste, ne gresis, ali to je isto. mislim ako prihvatimo da je 50 veliki broj.u svakom slucaju za veliko N je [(N/2)!]^2/N! = (1/2)^N. (uz neku malu polinomijalnu korekciju).al da, moja nepaznja u izrazavanju.@al

pa moze da se zakomplikuje redosledom pitanja i semantikom, tipa ako pitas nekoga kako mu se zove cerka, a on ima dve, onda sta on treba da odgovori...ali ako neko kaze "imam dvoje dece, marija radi u genexu..." u tom trenutku je verovatnoca da ima dve cerke 1/2, bez obzira na to koje je ime rekao.mislim to i jeste lepota zadatka.da bi izveo formalno bayes-a mozes recimo da pretpostavis da ima recimo N jednako verovatnih imena.ilista god, u svakom slucaju mozes da ukljucis eksplicitno verovatnocu da se zensko dete zove marija. ta verovatnoca se na kraju skrati.recimo da je ta verovatnca imena p(M).verovatnoca da covek sa dvije dece ima cerku mariju je1/4*2*p(M) + 1/2*p(M).u prvom ciniocu imamo 1/4 verovatnocu da ima dve cerke, ali je onda uslovna verovatnoca da se jedna od njih zove marija 2*p(M) jer ima dva nacina da se jedna od njih tako zove. zbog ovog faktora 2 je bitno da zanemarimo mogucnost da se obe zovu isto, u kom slucaju bi umesto 2*p(M) imali 1 - (1-P(M))^2 = 2*p(M) - p(M)^2 i na kraju se p(M) ne bi skratilo.u drugom ciniocu je 1/2 verovatnoca da ima jednu cerku i jednog sina, u kom slucaju je verovatnoca da se jedina cerka zove marija prosto p(M).elem poanta je da su zbog te dvojke ova dva cinioca jednaka, pa ako znas da ima cerku mariju podejdnaka je verovtnoca da je to zato sto ima dve cerke i jedna se zove marija, i zato sto ima smao jednu crku koja se zove marija.ime (bilo koje!) je bitno zato sto uvodi taj dodatni faktor 2.u tvom slucaju gde se unapred pita ko ima mariju je verovatnoca narno isto 1/2 ali iz trivijalnijeg razloga.edit: jebiga ne znam da li je jasno... to sto ne znamo unapred koje ce ime reci samo uvodi mali broj p(M), ali se on skrati i poanta je u tome da je jedan cinioc u uobicajenom zbiru za ukupnu verovatnocu da ima cerku (1/4 + 1/2) pomnozen sa malim brojem 2*p(M), a drugi sa malim brojem p(M).

edit: editovao spoiler.

Edited June 2, 2008 by kurdi

[Al-Khwarizmi]

@kurdi

edit: jebiga ne znam da li je jasno... to sto ne znamo unapred koje ce ime reci samo uvodi mali broj p(M), ali se on skrati i poanta je u tome da je jedan cinioc u uobicajenom zbiru za ukupnu verovatnocu da ima cerku (1/4 + 1/2) pomnozen sa malim brojem 2*p(M), a drugi sa malim brojem p(M).

Hm... jasno je. "Ćerka" potencijalno može da se odnosi na bilo koje od dva deteta, a "Marija" (ili bilo koje ime) se uvek odnosi na samo jedno dete. Ok, prihvatam.Ipak... npr. znaš samo da tvoj prijatelj Pera ima dvoje dece, a onda dođe vaš zajednički prijatelj iz mladosti Mika i kaže ti - "tek nedavno sam saznao za jednu koleginicu da je Perina ćerka!" Ako znaš da Mika zna imena svih svojih koleginica i kolega, da li to znači da sama činjenica da ti je rekao ili nije rekao njeno ime može uticati na verovatnoću da Pera ima dve ćerke? :D Zvuči sumanuto. Jedino što mi pada na pamet kao izlaz iz ove situacije jeste da zaključak iz Mikine izjave nije "Pera ima ćerku" => verovatnoća da ima dve ćerke je 1/3, već "Pera ima ćerku koju-je-Mika-upoznao-tad-i-tad" => verovatnoća da ima dve ćerke je 1/2.Jebite se, zabole me glava. :P

Edited June 2, 2008 by Al-Khwarizmi

[MayDay]

da ne ispadne da potcenjujem..Sultan ima 100 cerki. Cerke donose u miraz razliciti broj zlatnika, pri cemu BG ne zna rasppodelu miraza niti max vrednost. Sultan je dozvolio BG-u da ozeni jednu od cerki. Cerke ce mu biti predstavljane jedna po jedna i on mora da se odluci da li prihvata tu koja mu je predstavljena ili ne, pri cemu mu se u trenutku predstavljanja saopstava koliki miraz donosi ta cerka. BG nema pravo da u nekom trenutku kaze da zeli da ozeni cerku koja mu je bila ranije predstavljena, vec samo onu koja je u tom trenutku aktuelna. Koju strategiju BG treba da odradi, tako da sa najvecom verovatnocom izabere cerku sa najvecim mirazom. I da, kolika je ta verovatnoca?ako je bilo ranije, ja se izvinjavam.al, obrisi taj quote da me ne diskredituju for good. debil sam potpuni, vrisnuo mi mozak na visesatnom dezurstvu na 30 stepeni.

Edited June 2, 2008 by MayDay

[Al-Khwarizmi]

al, obrisi taj quote

:sealedlips: -_- Edited June 2, 2008 by Al-Khwarizmi

[kurdi]

Sultan ima 100 cerki.

uh, nemam predstavu. (bg ne bi birao po mirazu nego po nacitanosti, al da ne ulazimo sada u to.)a idem sada od kompa pa ako neko resi, molim vas u spojler, deluje jako znaimljivo.@al

da, tu je opet 1/2 (zanemarivsi mogucnost da i druga cerka radi sa mikom).manje su a priori sanse da pera ima dve cerke nego jednu (1/4 vs 1/2), ali je zato uslovna verovatnoca da pera ima cerku u toj firmi dva puta veca ako ih ima dve koje bi se mogle tamo zaposliti, pa se taj faktor dva potre.ali generalno ta osnvna ideja da su sanse da se iz dva pokusaja nesto nabode (neko ime ili posao u nekoj konkretnoj firmi) prosto dva puta vece nego iz jednog pokusaja stoji samo ako su u pitanju malo verovatni dogadjaji.kod imena smo pretpostavili da je striktno nemoguce da neko nazove dva deteta isto, ali cak i da nismo mogli bi reci da je svakako p(M) << 1 i stoga zanmeariti p(M)^2 << p(M).ali recimo ako mika kaze "bio sam na svadbi perine cerke" onda ne radi, posto verovatnoca da se zena uda nije dovoljno mala da bi se moze reci da dve zene imaju dva puta vece sanse da se jedna od njih uda nego jedna zena sama. makar je nekada tako bilo.

Edited June 2, 2008 by kurdi

[Al-Khwarizmi]

@kurdi

da, tu je opet 1/2 (zanemarivsi mogucnost da i druga cerka radi sa mikom).

Ne mora se zanemariti, može i druga da radi sa Mikom... ako uvedemo vremensku dimenziju. Dakle Mika je u pomenuto vreme (ovde određeno fuzzy terminom "nedavno", što se za naše potrebe može prihvatiti) saznao za tačno određenu Perinu ćerku ko joj je otac. Iz semantike njegove rečenice se može sa velikom verovatnoćom uzeti da nije "nedavno" saznao za obe, pošto pominje samo jednu.

ali recimo ako mika kaze "bio sam na svadbi perine cerke" onda ne radi, posto verovatnoca da se zena uda nije dovoljno mala da bi se moze reci da dve zene imaju dva puta vece sanse da se jedna od njih uda nego jedna zena sama. makar je nekada tako bilo.

Da, onda je verovatnoća 1/3. Ali ako se i ovde uvede vreme, npr. "bio sam prošlog vikenda na svadbi kod perine cerke", onda je verovatnoća 1/2. Bitno je samo da postoji odrednica koja ukazuje na tačno određenu ćerku, t.j. ne može se primeniti na bilo koju od njih.

Edited June 2, 2008 by Al-Khwarizmi

[MayDay]

:sealedlips: -_-

zahvaljujem

[kurdi]

@ al

da, slazem se, bilo kakva malo verovatna specificnost je dovoljna.samo nije bas:

Da, onda je verovatnoća 1/3.

jer nije bas 100% da se svaka zena uda, tako da ima neke informacije ipak.generalno je verovatnoca (2-p)/(4-p)gde je p verovatnoca dodatne informacije koju smo saznali.za malo p je 1/2, za p=1 je 1/3

@ mayday... i dalje nemam ideju :(nije 1/100?

[MayDay]

@ al

da, slazem se, bilo kakva malo verovatna specificnost je dovoljna.samo nije bas:jer nije bas 100% da se svaka zena uda, tako da ima neke informacije ipak.generalno je verovatnoca (2-p)/(4-p)gde je p verovatnoca dodatne informacije koju smo saznali.za malo p je 1/2, za p=1 je 1/3

@ mayday... i dalje nemam ideju :(nije 1/100?

mozes jako puno da poboljsas verovatnocu. resenje je u spojleru, a metod malo kasnije, ako zelis.

Bg ce cekati da se izredja 37 cerki, a onda ce izabrati prvu koja bude imala veci miraz od najveceg do sada ponudjenog.Ubosce najveci miraz sa verovatnocom od 0.371.

[kurdi]

ma necu da gledam, razmisljam jos, makar malo pred spavanje.edit: ok, pogledo sam ipak, mrtav sam, moram da spavam, a ne mogu ako ne resim.i dalje ne znam kako, al sad bar znam da nije neka jednostavna fora koja moze bez papira, pa se ne nerviram previse.mislio sma da je u toj formi, al nisam mogao da provalim kako da izracunam. probao sa 1 (ocigledan minimum) i 10 (kao koren, al to cisto na neki neodrdjeni osecaj).videcu sutra jel mogu da provalim metod.

Edited June 2, 2008 by kurdi

[Al-Khwarizmi]

Sultan ima 100 cerki. Cerke donose u miraz razliciti broj zlatnika, pri cemu BG ne zna rasppodelu miraza niti max vrednost. Sultan je dozvolio BG-u da ozeni jednu od cerki. Cerke ce mu biti predstavljane jedna po jedna i on mora da se odluci da li prihvata tu koja mu je predstavljena ili ne, pri cemu mu se u trenutku predstavljanja saopstava koliki miraz donosi ta cerka. BG nema pravo da u nekom trenutku kaze da zeli da ozeni cerku koja mu je bila ranije predstavljena, vec samo onu koja je u tom trenutku aktuelna. Koju strategiju BG treba da odradi, tako da sa najvecom verovatnocom izabere cerku sa najvecim mirazom. I da, kolika je ta verovatnoca?

Zadatak izgledao jednostavan na prvi pogled, ali izgleda da je dosta zavučeniji...Nisam rešio, ali evo da nabacam šta mi je padalo na pamet, možda nekom pomogne.Izaberemo neku poziciju x. Očigledno, uslovi su sledeći: najbogatija ćerka se mora pojaviti posle x (recimo na nekoj poziciji m), a između x i m se ne sme pojaviti nijedna ćerka bogatija od najbogatije od onih na pozicijama od 1 do x (inače bi ona bila odabrana). Cilj nam je da verovatnoću toga izrazimo kroz x u nekom kontinualnom obliku, izvod te funkcije izjednačimo sa 0, i odatle odredimo x. Ovo mi u opštem slučaju miriše na neke redove, a to sam uglavnom pozaboravljao... :( Straight forward pristupom dobijam neke užasno komplikovane formule, sa kojima ne znam šta da radim... Pade mi na pamet da pokušam drugim putem - da se igram sa pozicijom m u odnosu na x. Ako je m odmah iza x (m=x+1), pobeda je sigurna. Verovatnoća za to je 1/100. Ako je m=x+2 (opet verovatnoća 1/100), onda nam za pobedu treba još uslov da je od prethodnih x+1 lokalno najbogatija u prvih x (verovatnoća x/x+1)... što zajedno daje 1/100*x/x+1Itd, do pozicije m=100.Ako nešto gadno nisam prevideo, zbir ovih verovatnoća bi trebalo da da našu traženu funkciju, koju potom treba diferencirati, i naći max...

[MayDay]

Zadatak izgledao jednostavan na prvi pogled, ali izgleda da je dosta zavučeniji...Nisam rešio, ali evo da nabacam šta mi je padalo na pamet, možda nekom pomogne.Izaberemo neku poziciju x. Očigledno, uslovi su sledeći: najbogatija ćerka se mora pojaviti posle x (recimo na nekoj poziciji m), a između x i m se ne sme pojaviti nijedna ćerka bogatija od najbogatije od onih na pozicijama od 1 do x (inače bi ona bila odabrana). Cilj nam je da verovatnoću toga izrazimo kroz x u nekom kontinualnom obliku, izvod te funkcije izjednačimo sa 0, i odatle odredimo x. Ovo mi u opštem slučaju miriše na neke redove, a to sam uglavnom pozaboravljao... :( Straight forward pristupom dobijam neke užasno komplikovane formule, sa kojima ne znam šta da radim... Pade mi na pamet da pokušam drugim putem - da se igram sa pozicijom m u odnosu na x. Ako je m odmah iza x (m=x+1), pobeda je sigurna. Verovatnoća za to je 1/100. Ako je m=x+2 (opet verovatnoća 1/100), onda nam za pobedu treba još uslov da je od prethodnih x+1 lokalno najbogatija u prvih x (verovatnoća x/x+1)... što zajedno daje 1/100*x/x+1Itd, do pozicije m=100.Ako nešto gadno nisam prevideo, zbir ovih verovatnoća bi trebalo da da našu traženu funkciju, koju potom treba diferencirati, i naći max...

ja nisam umela da ga resim. gledala sam u resenje i dobra su ti oba pristupa. naravno, diferenciranje je zajebano i resava se numericki.

[kurdi]

resava se numericki.

e do jaja. mogu ubuduce upozorenja za takve stvari? ja koristim samo ovaj windows calculator.

[MayDay]

e do jaja. mogu ubuduce upozorenja za takve stvari? ja koristim samo ovaj windows calculator.

bitan je pristup. samo to. mislila sam da moze u zatvorenom obliku, ali jbg. nece se ponoviti.edit: hocu li se izvaditi ako ispisem ideju za zadatak sa 100 takmicara i 100 koverti? s tim sto sam trenutno sposobna samo za 4 takmicara koji mogu da otvaraju po 2. Edited June 3, 2008 by MayDay

[kurdi]

aj daj, sve moze da pomogne.ja u medjuvremenu pocinjem da odstajem od svoje originlne strategije....