zanimljiva matematika

[MayDay]

pisem za sat vremena.

[MayDay]

Neka bude da ih ima cetvorica i da mogu da otvaraju koverte po dva puta svaki. Ako bi se podelili na onaj nacin tako da prva dvojica otvaraju prve dve, verovatnoca pobede bi bila 2/4*1/3=1/6.Dodelicemo svakom takmicaru broj i=1,..,4. Takmicar i treba da otvori koveru pod rednim brojem i. Ako nadje svoju dobro je (posle ce se pokazati da i nije), a ako nadje u koverti ime j-tog takmicara (j<>i) onda otvara kovertu sa rednim brojem j.Posto je simetrican zadatak, krenucu od prvog takmicara.Verovatnoca pobede:1/4*(1/3+2/3*1/2) /takmicar 1 je odmah nasao svoju i drugi je odmah zatim nasao svoju u koverti 2 ili je u koverti 2 nasao ime ciji je redni broj tacno redni broj koverte u kojoj je ime takmicara 2 i koje ce on naci u drugom pokusaju pa se lanac zatvara/+ 3/4*1/3 /takmicar nije nasao svoje ime, ali je nasao ime ciji je redni broj tacno redni broj koverte u kojoj ime prvog takmicara, pa se lanac zatvara/=1/6+1/4=5/12.postoji 24 permutacijeu 10 slucajeva strategija radi1234 *1243 *1324 *1342 14231432 *2134 *2143 *2314234124132431312431423214 *32413412 *34214123413242134231 *43124321 *edit: nepismenost

Edited June 3, 2008 by MayDay

[kurdi]

:) i ja upravo racunam istu strategiju.(prethodna gluplja strategija mi je bila da prosto prvi otvara 1-50. drugi 2-51 etc.)

Edited June 3, 2008 by kurdi

[kurdi]

jebiga mora da je (nesto tipa) 1/e, al nemam dokaz.

[kurdi]

o, mozda imam i dokaz, al nije sredjen i nemam sad bas vremena, pa cu malo iz delova...za pocetak uocite iz mayday primera da ako prvi igrac pogodi iz drugog pokusaja onda sigurno pobedjuju.aj mozda ce nekome ovo biti zanimljivo kao hint, pa necu sad dalje...

[kurdi]

ok, mislim da sam mu jebao kevu.tacan rezultat (mislim) nije 1/e, al je damn close.hintovi kada budete trazili.edit: ne samo sto nije tacno 1/e, nego ono sto sada mislim da je najtacniji pristup/rezultat nije tog funkcionalnog oblika.ali aproksimacija koju sam prvo probao daje (otprilike) taj rezultat, plus moze malo da se koriguje, i u par % se slaze sa (mislim, jos nista nije 100% sigurno...) tacnim rezultatom, mada su ta dva pristupa matematicki potpuno razlicita.

Edited June 3, 2008 by kurdi

[MayDay]

ja cu da prestanem da zadajem zadatke koji ce da oduzimaju vise od 15 minuta. sad me pece savest.edit: ja sam planirala da prosirim na 6 koverti sa 3 pokusaja, da zadrzim taj odnos x:n=1:2, pa da vidim sta ce indukcija da izbaci. ali sad bih radije da to izbegnem i da ti lepo ispises svoj dokaz. ovo 1/e je verovatno granicni slucaj, ne?

Edited June 3, 2008 by MayDay

[kurdi]

ovaj... ovi moji komentari, 1/e, jebanje keve i to.... se odnose na 100 koverata :Dtaj se radi bez komjutera i sam racun na krju nije tezak, al zadatak nije lak. zapravo do jaja je sve zajedno.

Edited June 3, 2008 by kurdi

[kurdi]

edit: ja sam planirala da prosirim na 6 koverti sa 3 pokusaja, da zadrzim taj odnos x:n=1:2, pa da vidim sta ce indukcija da izbaci. ali sad bih radije da to izbegnem i da ti lepo ispises svoj dokaz. ovo 1/e je verovatno granicni slucaj, ne?

1/e je (otprilike) granicni slucaj u pristup koji je aproksimativan, algebarski tezi, i u stratu da bi bio izracunljiv mora da se primeni na veliki broj koverata... ali je meni bio prvi intuitivan...tacan pristup je takav da rezultat moze da se napise za bilo koji broj koverata... za veliki broj se uvodi trivijalna i odlicna aproksimacija da bi se rezultat napisoa u zatvorenom obliku...evo kucam... prvo koncept pa posle dve matematike... koncepte cu javno, matis u spojlere malo kasnije.

[MayDay]

ma ne moras veceras. nekom zgodnom prilikom u buducnosti, ako ne zaboravis racun. ja obicno zaboravim. :)

[kurdi]

daklem prvo par komentara da objasnim ideju...aj prsirimo na 8 igraca i 4 pokusaja...i pretpostavimo da se prvi igrac jedva izvuce otvoricvsi koverte sa brojevima recimo 7, 4, 2, 1.znaci da je raspored:7, 1, x, 2, x, x, 4, xe sad prvo uocimo da ovo znaci da ce i igraci 2, 4, i 7 garant naci svoj broj. oni su vec "spaseni".ova 4 broja cine zatvoren skup/ciklus duzine 4, takav da su isto brojevi na i u kovertama, ali su pomesani tako da nijedan nije na svom mestu.jos - svakome od ovih igraca ce trebati tacno 4 pokusaja. igrac broj 2 ce redom naci brojeve 1,7,4,2.igrac broj 7 ce naci brojeve 4, 2,1,7. broj 4 ce naci 2,1,7,4.ovo su sve ciklicne permutacije onoga sto je video prvi igrac.i jos - ako pogledamo bolje, ne samo sto su ova trojica spaseni pretpostavljenim uspehom prvog igraca, nego su spaseni svi!za prostalu cetvroci ne znamo da li svi pripadaju istom ciklusu duzine 4, ili je svaki na svom mestu ili sta god, ali znamo da su spaseni sigurno.(ko ne veruje nek proba razne permutacije preostala 4 broja)da je pak prvi igrac nasao svoj broj iz treceg pokusaja, samo bi jos dva igraca istovremeno bila spasena, dok bi sudbina preostalih 5 bila neizvesna.ok, tolko o slikama, sledi matis... u spojlerima.

[Al-Khwarizmi]

Kad već pominješ 1/e...

...to mu izađe negde oko 0.37... što opasno liči na brojku koju je MayDay pomenula kao rešenje prethodnog zadatka (sa tetrebom i sisatim... pardon, bogatim ćerkama)! Možda ipak postoji elegantnije rešenje od numeričkog?

[kurdi]

dakle prvo resenje za 100 koverata, zajebaniji matis (i nije bastacno), al meni bilo lakse za shvatiti postavku...

pristup:u svakom trenutku za k-tog igraca racunamo uslovnu verovatnucu da uspe, ako je dato da su prethodnih k-1 uspeli.proizvod tih brojeva je onda odgovor.nek s eovo zove p(k)e sad, iz polaznih opservacija o ciklusima vidimo da da bi k-ti propao ne sme biti vec "spasen od strane nekog od prvih k-1.tj ne sme pripadati ni jednom od ciklusa kojima oni pripadaju.ovo znaci da on mora da izvuce 50 brojeva koji, osim sto ocigedno nisu k, su svi veci od k.moguce je da on izvuce k, bez da izvuce ijedan manji broj, ali nije moguce da izvuce neki mani a ne izvuce k.ok, tu pravimo malu gresku i racunamo verovatnocu da izvlaceci N od 2N brojeva (2N=100) svih N budu u gornjih 2N-k.(ovo pretpostavlja neke nezavisosti u izvlacenju kje sigurno nisu tacne, ali su korekcije male)ovo ispada prostim odabirom N od 2N i N od 2N-k:(2N-k)!*N!/[(2N)!*(N-k)!], sto je znaci jednako 1- p(k) (posto racunamo sansu da ne uspe)za N=k=2 se moze proveriti da ovo tacno daje verovatnocu da drugi najebe ako prvi nije od 1/6.ovo je mayday eksplicitno pokazala - za 4 igraca pobedjuju u 1/2 * 5/6 slucajeva.nije toliko tacno za vece brojeve ali su svi brojevi dovoljno mali da ne menja konvergenciju i konacni rezultat mnogo.i zadovoljava osnovnu ideju da je 0 za k>Nako prvih N uspe spaseni smo sigurno.elem, za veliko N, a malo k, ovaj gore izraz je jednak (1/2)^k. ovo je lako proveriti.kako se k priblizava N verovatnoca neuspeha opadajos brze od (1/2)^k (mora biti striktno nula za k>N), ali ionako je samo prvih par bitno, posle je 1-p(k) jako jako malo u svakom slucaju tako dane utice na rezultat i mozemo da zamenimo konacni proizvod po k beskonacnim.ok,znaci ukupna verovatnoca je otprilike:(1-1/2)*(1-1/4)*(1-1/8)*(1-1/16)*..... (1-1/2^k)...e sad kako ovo izracunati... zapravo jebiga ispostavlja se (naknadno) da je dovoljno izmnoziti prvih par cinioca...1/2*3/4*7/8*15/16*... vrlo brzo konvergira.s druge strane 1-x je priblizno e^(-x) za malo x.tako da ako bezobrazno kazemo da je i 1/2 <<1dobijemo e^ (-1/2-1/4-1/8....) = 1/e. sto je ono sto sam ja prvo uradio.ili mozemo samo prvih par cinioca da zamenimo pravim vrednostima (1/2 umesto e^-0.5, 3/4 umesto e^-0.25... dalje nije ni bitno, aproksimacija postane dobra) 1/e = 0.37, suma zapravo konvergira kolko se secam na nesto tipa 0.28, a tacan odgovor je 0.31. napomena: uslovna verovatnoca da drugi promasi zavisi od N... za 4 igraca je 1/6, ali za vise konvergira ka 1/4.

[kurdi]

Kad već pominješ 1/e...

e sad si mi jebao kevu :D... ok, to cemo da probamo drugi put.mada je ona rekla precizno 0.371, al svejedno bio bih zadovoljan tom aproksimacijom...

[Al-Khwarizmi]

mada je ona rekla precizno 0.371, al svejedno bio bih zadovoljan tom aproksimacijom...

Hm... a da je bilo 1000 ćerki? Ili milion? Kapiram da je opet u pitanju neki red (moraću da se nateram da malo obnovim to gradivo, ne bih li mogao da prepoznam "sumnjive" sume... <_< ), pa što je broj manji to je aproksimacija lošija, pa i odstupanje veće.Btw, i pozicija je bila 37 (100/e, za n=100). Slučajnost? Hm...