zanimljiva matematika

[Al-Khwarizmi]

Oznacimo npr. ucenike indeksima od 1 do n, krenuvsi sa profesorove desne strane, suprotno smeru kazalje na satu.Sa P_k oznacimo verovatnocu da ucenik k pobedi. Ocigledno je zbog simetrije P₁ = P_n, P₂=P_n-1, ... Dokazacemo da je P_n = 1/n:Sa P_n,k oznacimo verovatnocu da ucenik n pobedi kada je lopta kod ucenika k (tako da u medjuvremenu nije bila kod ucenika n, naravno). Vazi sledece: P_n = 1/2*P_n,1 P_n,1 = 1/2 *P_n + 1/2*P_n,2 (ako se lopta vrati profesoru, verovatnoca da n pobedi je opet P_n) P_n,2 = 1/2*P_n,1 + 1/2*P_n,3 ... P_n,k = 1/2*P_n,k-1 + 1/2*P_n,k+1Odavde se lako da dokazati da vazi: P_n = 1/(k+1)*P_n,kAko je lopta stigla do ucenika n-1 (tako da nije nijednom bila kod n), ucenik n je pobedio. Znaci: P_n,n-1 = 1Odatle je: P_n = 1/(n-1+1)*P_n,n-1 = 1/nZnaci da je uvek P₁ = P_n = 1/n. Zbir svih P_k verovatnoca je 1, a vazi i simetrija, pa je lako videti npr. da su i za n=3 i za n=4 preostale verovatnoce jednake 1/n. Ostaje jos da se dokaze da to vazi i u opstem slucaju, sto ne bi trebalo da je mnogo tesko... ajd da razmislim pa cu, nadam se, dovrsiti i taj deo dokaza.edit: dodao sub tagove radi čitljivosti

Edited June 1, 2008 by Al-Khwarizmi

[Kudravi Gaucos]

:D nisam jos racunao al cim videh kudravog pomislih nema sanse...

Nije lepo sprdati se sa laicima. I mi bi malo da se igramo, a vi da ste pravi drugari, bacali bi vise ovih programerskih, a manje statistickih

[Al-Khwarizmi]

Ostao sam dužan deo dokaza. Sad imam malo vremena za to.Dokazali smo da je verovatnoća da pobedi neki učenik pored profesora: P₁ = P_n = 1/nTo su učenici na rastojanju 1 od profesora (t.j. njegovi susedi). Ostaje da vidimo kolika je verovatnoća da pobedi učenik na rastojanju k od profesora. Označimo je sa R_k. Tada je:R₁ = P_n = P₁ = 1/nZa R₂ važi - ako je lopta prvo dodata učeniku pored onog za kojeg tražimo verovatnoću, sveli smo na slučaj iz prethodnog posta - situacija je identična kao da je lopta krenula od tog mesta, odnostno da je tu profesor umesto učenika; ako je poslata na suprotnu stranu, važi isto - svodi se na slučaj kada lopta kreće od tog mesta. Ovo sigurno važi kad oko učenika za kog tražimo verovatnoću još niko nije dobio loptu, pošto se učenici ne mogu preskakati (jedino gde nisam bio siguran da možda verovatnoća nije ipak veća, jeste situacija u kojoj je lopta već došla do suseda posmatranog učenika sa jedne strane, ali nije još sa druge - zato sam posebno obradio slučajeve u prethodnom postu, gde profesor stoji odmah pored posmatranog učenika):R₂ = 1/2 * P_n + 1/2 * R₃ = 1/2 * R₁ + 1/2 * R₃ = 1/(2n) + 1/2 * R₃R₃ = 1/2 * R₂ + 1/2 * R₄...R_k = 1/2 * R_k-1 + 1/2 * R_k+1 (*)Odavde se lako izvodi da je:R_k = 1/(k*n) + (k-1)/k * R_k+1Opet zbog simetrije važi da je:R_n = R₁ = 1/nOdakle je:R_n-1 = 1/(n*(n-1)) + (n-2)/(n*(n-1)) = 1/nOdnosno, zamenom kroz sve gornje formule:R_k = 1/n (za svako k od 1 do n)Ovde sam R uveo samo radi preglednosti, da bi smo razdvojili verovatnoću računatu za pozicije od verovatnoće računate za rastojanje od profesora. Ali je očigledno da je P_k = R_k, čime se dobija:P_k = 1/nTakođe, ovo znači da se (*) može napisati kao:P_k = 1/2 * P_k-1 + 1/2 * P_k+1Što je kurdijeva formula.

Edited June 2, 2008 by Al-Khwarizmi

[MayDay]

O Al, svaka cast!!!kurdi, vidi na sta sam naletela.

[kurdi]

Nije lepo sprdati se sa laicima. I mi bi malo da se igramo, a vi da ste pravi drugari, bacali bi vise ovih programerskih, a manje statistickih

:Dma nisam mislio zato sto si ti u pitanju, nego samo da nema sanse da je n/2 najbolje, to nekako deluje krajnje prosecno.doduse ispostavilo se da je prosek ujedno i najbolje (i najgore) cemu se mozmeo nadati.

...što je kurdijeva formula.

sto ti je osecaj i ja sam se u medjuvremenu rukomlatom (ponovo) uverio u tacnost ove konjekture, i cini mi se da mogu da formulisem dokaz recima tako da nije potrebno nikakvo znanje matematike za razumevanje, al nije bas neka korist da sad na brzinu spetljano predstavljam. ako lepo srocim napisacu.a ako se krene od te formule kao date, onda dalje isto nije potrebna nikakva matematika. ocigledno je da profesorovi prvi susedi imaju istu verovatnocu (ma sta ona bila), a ujedno su i susedi u formuli.onda njihovi prvi susedi (oni spoljni, broj 2 i n-1) po formuli moraju imati istu verovatnocu kao i oni sami itd.cim imas dva suseda sa istom verovatnocom, svi moraju imati istu. btw, cini mi se da moze i indukcijom da se dokaze, al ni to nisam do kraja srocio.

kurdi, vidi na sta sam naletela.

:) (gvirno smao, nemam sad vremena)

[kurdi]

Ispada da bih polozio prijemni za banku na osnovu sveske iz srednje skole :) Dajte bre neki koji nisam video, ovi su vam skolski.

pa jeste, to se i testira, skola ne pomaze mnogo. i ja sve sto znam znao bih i onda cini mi se.(a prijemni za faks, ono sa otpornicima, jos ocigednije da se ocekuje da se polozi sa znanjem iz srednje skole...)ajde evo za ove kurcevite pravog zadatka... al molim da se ako neko resi stavlja u spoiler, ja jos nisam resio. odnosno konacan rezultat moze i javno, al metodu u spoiler.daklem imamo 3 sobe A, B, C (mada C nije bitna).u sobi A je N=100 ljudi koji su obelzeni brojevima 1 - 100.u sobi B je sto koverata u kojima se nalaze nasumicno rasporedjeni brojevi 1-100 (po jedan u svakom kovertu). koverti su spolja recimo isto obelezeni brojevima 1-100 da bi moglo da se prati resavanje (ili prosto stoje nekim fiksnim redom na stolu, nije bitno), ali onaj broj kojim je obelezena koverta nije broj koji je unutra naravno.u sobi C su grickalice i sokovi.ljudi jedan po jedan idu iz A u B, tamo imaju pravo da otvore (i ponovo zatvore) 50 koverata. gleda se da li su pritom uspeli da nadju svoj broj u jednom od otvorenih koverta.onda odlaze u C, grickaju, pijuckaju, i cekaju kraj igre.takmicari su kolektivno pobedili ako SVI nadju svoj broj.zadatak je naci optimalnu strategiju (koju su unapred dogovorili) i verovatnocu da pobede.nema naravno glupih fora, obelezavanja koverata i sl.par napomena/hintova (ono sto ja znam, a sto nije mnogo):prvi ocigldno ima 1/2 sanse da nadje svoj broj.ako su uzasno glupi i svako nasumicno otvara po 50 koverata verovatnoca je (1/2)^100.ako su malo manje glupi verovatnoca je (1/2)^50, ali ni to nije odgovor.ovaj rezultat se dobija ako se dogovore da prvih 50 otvara prvih 50 koverata a drugih 50 drugih 50 koverata. onda prva polovina ima (1/2)^50 sanse da su stvarni svi njihovi brojevi u prvih 50 koverata, ali je uslovna verovatnoca da i druga polovina nadje svoje brojeve onda automatski 100%.ovo je jos ociglednije u slucaju dva igraca. ako se dogovore da otvore razlicite koverte onda ako prvi pogodi, pogadja automatski i drugi, pa je ukupna vrovatnoca 1/2, naspram 1/4 ako otvaraju nasumicno bez dogovora.(naravno 1/2 je i sansa da obojica promase, umsto 1/4 u nsumicnom otvaranju, ali to sto obojica promase nije nista gore nego da promasi samo jedan)ja ne znam odgovor. odnosno po simetriji mislim da znam strategiju, al nikako da stignem da sednem da izracunam koju verovatnocu daje.ispravan pristup vrlo verovatno podrazumeva da je 100 veliki broj. znaci moze da se racuna i za neko veliko N, i mozda je i bolje tako razmisljati nego hvatati se za konkretne primere.navodno je (just about) moguce izracunati u krevetu, bez papira i olovke. ne znam kolki je ovo hint, al tako je meni receno. al taj sto je rekao je mnogo pametan. ja za svoju strategiju ne mogu da izracunam, sto znaci da ili je strtegija pogresna, ili ja ne vidim kako se racuna najefikasnije, ili on prosto bolje racuna od mene (posto ovo poslednje jeste tacno, vrednost hinta je dubiozna).al kako god, tvrdnja je da "ako ne mozes da izracunas, verovatno je strategija pogresna".ja sam prilicno siguran da tacno resenje ne skalira eksponencijalno sa N.kako skalira ne znam.moguce je da cak ne zavisi od N (mada to zvuci malo neverovatno), ili eventualno logaritamski.al posto ne znam(o) resenje, i polinomijalnu zavisnost cemo morati da prihvatimo kao mnogo bolju od eksponencijalne.ma zapravo i exp(\sqrt{N}) cemo morati da prihvatimo kao impresivno, al ne verujem da je tako nesto.ja onda kad neko nadje neku stratgiju mogu da pitam jel moze bolje pa da javim...

[Al-Khwarizmi]

a ako se krene od te formule kao date, onda dalje isto nije potrebna nikakva matematika. ocigledno je da profesorovi prvi susedi imaju istu verovatnocu (ma sta ona bila), a ujedno su i susedi u formuli.onda njihovi prvi susedi (oni spoljni, broj 2 i n-1) po formuli moraju imati istu verovatnocu kao i oni sami itd.

Tačno je da je ova formula dovoljna da pokaže da svi imaju istu verovatnoću, bez potezanja matematike, ali nisam siguran da to možemo zaključiti na osnovu boldovanog dela (ili bar meni to nije očigledno, zbog profesora koji stoji između i može da pošalje loptu i natrag).Ali ako krenemo na suprotnu stranu, putem kojim je MayDay ranije pošla, i pogledamo učenike koji su najudaljeniji od profesora, možemo razlikovati dva slučaja:1) ako je broj učenika neparan, učenik najudaljeniji od profesora ima dva suseda sa međusobno jednakim verovatnoćama (zbog simetrije), pa po formuli on ima istu verovatnoću.2) ako je broj učenika paran, dva učenika najudaljenija od profesora imaju istu verovatnoću (zbog simetrije).U oba slučaja imamo susede sa istom verovatnoćom, a važi ovo tvoje zapažanje:

cim imas dva suseda sa istom verovatnocom, svi moraju imati istu.

Ovim se zaista dokaz dosta pojednostavljuje. :) Edited June 2, 2008 by Al-Khwarizmi

[MayDay]

evo za bigeja dajem dva zadatka koji idu u paru da se sprema za intervju:1. znas da jedna porodica ima dvoje dece i da je najmanje jedno od njih zensko, ali ne mozes da se setis da li su oba deteta zenska. kolika je verovatnoca da su oba deteta devojcice?2. znas da jedna porodica ima dvoje dece i secas se da je najmanje jedno od njih devojcica sa vrlo neobicnim imenom (tipa, tako se zove jedna u milion devojcica), ali ne mozes da se setis da li su oba deteta zenska. kolika je verovatnoca da su oba deteta devojcice?

[MayDay]

lupetam

Edited June 2, 2008 by MayDay

[kurdi]

Tačno je da je ova formula dovoljna da pokaže da svi imaju istu verovatnoću, bez potezanja matematike, ali nisam siguran da to možemo zaključiti na osnovu boldovanog dela (ili bar meni to nije očigledno, zbog profesora koji stoji između i može da pošalje loptu i natrag).

nije ocigledno, al se ja naknadno ubedih (taj prazan hod, dok je kod ucitelja, tj da li se on 5 ili 100 puta dobaci vamo tamo sa istim, ne utice.)ali u svakom slucaju je mnogo bolje ovo sto ti kazes za taj deo dokaza.a konjekturnu formulu sam napisao zapravo dok je u postavci pisalo da ucitelj izadje iz kruga jednom kad ubaci loptu iz igru, pa onda usledise editi na obe strane...e a dokazati/videti formulu bez matematike... to ne mogu da procenim kolko je ocigledno... ali kapiram da je i progamerima janso kako je rekurzivno napisana.moram piciti.

[kurdi]

evo za bigeja dajem dva zadatka koji idu u paru da se sprema za intervju:1. znas da jedna porodica ima dvoje dece i da je najmanje jedno od njih zensko, ali ne mozes da se setis da li su oba deteta zenska. kolika je verovatnoca da su oba deteta devojcice?2. znas da jedna porodica ima dvoje dece i secas se da je najmanje jedno od njih devojcica sa vrlo neobicnim imenom (tipa, tako se zove jedna u milion devojcica), ali ne mozes da se setis da li su oba deteta zenska. kolika je verovatnoca da su oba deteta devojcice?

ih, nije ovo za bg-a tesko. jos mu ti i olaksavas dodatnim naglasavanjima.ovo je vec bilo negde (ja kacio) u originalnoj/tezoj verziji:1. jovanovici imaju dvoje dece i znas da imaju cerku. kolika je verovatnoca da imaju dve cerke?2. jovanovici imaju dvoje dece i znas da imaju cerku mariju. kolika je verovatnoca da imaju dve cerke?(nije bitno da je ime retko, dovoljno je da oni nisu debili)

[MayDay]

@kurdi

jedan od profana sa pmf-a je svojim sinovima dao ista imena

[kurdi]

@kurdi

@mayday

pa to nije u kontradikciji sa mojom izjavom :Dno salu na stranu, tu opet ne pomaze da je ime retko. ako ista osoba daje i hoce isto, moze i retko da da dva puta. kapiram da se njemu nije slucajno deslilo zato sto je u pitanju neko cesto ime. osim ako jeste, u kom slucaju je simpaticno. jednom mom kolegi se dva puta desilo da u opstini ne moze da se seti sta se sa zenom dogovorio oko srednjeg imena deteta, pa je izmislio na licu mesta. mislim jebes srednje ime, ko ce sad da se vraca da pita. al zena mislim da nije bila facinirana.

[MayDay]

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.

Edited June 2, 2008 by MayDay

[Al-Khwarizmi]

evo za bigeja dajem dva zadatka koji idu u paru da se sprema za intervju:1. znas da jedna porodica ima dvoje dece i da je najmanje jedno od njih zensko, ali ne mozes da se setis da li su oba deteta zenska. kolika je verovatnoca da su oba deteta devojcice?2. znas da jedna porodica ima dvoje dece i secas se da je najmanje jedno od njih devojcica sa vrlo neobicnim imenom (tipa, tako se zove jedna u milion devojcica), ali ne mozes da se setis da li su oba deteta zenska. kolika je verovatnoca da su oba deteta devojcice?

1. jovanovici imaju dvoje dece i znas da imaju cerku. kolika je verovatnoca da imaju dve cerke?2. jovanovici imaju dvoje dece i znas da imaju cerku mariju. kolika je verovatnoca da imaju dve cerke?

Uh... znam da je namenjeno BG-u ali moram da prokomentarišem prilično upitnu postavku. Evo u spojleru.

Ovaj prvi zadatak je odličan, podseća me malo na onaj sa troja vrata i nagradom iza jednih od njih. Ali što se tiče drugog... ako je taj neko samo pomenuo ćerkino ime, koje god ono bilo, to naravno nikako ne može uticati na verovatnoću da je i drugo dete žensko, i ona mora ostati 1/3. Ali ako smo baš znali da se traži ime Marija, to menja stvar, i ona postaje 1/2.Mogu se postaviti sledeći eksperimenti:Odabere se uzorak tako što se na ulici anketiraju i sa strane izdvoje svi koji imaju dvoje dece. 1) Potom se od njih izdvoje svi koji imaju bar jednu ćerku. U približno 1/3 slučajeva će oni imati i drugo dete žensko. 2) Ako se pak izabere neko žensko ime (u našem slučaju Marija), pa se od one grupe roditelja sa dvoje dece izdvoje svi koji imaju dete koje se zove Marija, onda će približno 50% njih imati i drugo dete žensko.Međutim, problem je u tome što se vaš drugi zadatak može pre svesti pod eksperiment 1 nego 2, tako da je postavka vrlo problematična IMHO. Primer: ako poznanik za kojeg se sećate samo da ima dvoje dece u razgovoru pomene "Moja ćerka mi je rekla...", verovatnoća da ima dve ćerke je 1/3. Međutim, ako kaže "Moja ćerka Marija mi je rekla...", verovatnoća nije 1/2, već opet 1/3! Prosto zato što nismo unapred znali koje će ime pomenuti. Mogao je reći i Jovana (Eleonora, Ema, Ena... :D), tako da ovom slučaju odgovara prvi eksperiment, ne drugi.

Edited June 2, 2008 by Al-Khwarizmi