[Zadatak]: Tri kockara sa novčićima

[Zadatak]: Tri kockara sa novčićima 09.03.2006. u 01:32 · pre 251 mesec #1

Tri kockara imaju redom $l$ , $m$ i $n$ novčića. Oni igraju sledeću igru: istovremeno bace novčiće, i onaj čiji je novčić pao na drugačiju stranu u odnosu na preostala dva odnosi pobedu u tom bacanju i kupi sva tri novčića. Ako se dogodi da su svi novčići pali na istu stranu bacanje je nerešeno. Naći očekivani broj bacanja do ispadanja jednog od igrača (tj. do situacije kada jedan od njih ostane bez novčića).

Ja ne volim verovatnoću ali ovaj problem mi se baš svideo, pa želim da ga podelim sa vama. Da vas malo uplašim ;), zadatak je postavljen 1941. godine i bio je otvoren problem punih 25 godina dok se 1966. nije pokazalo da ima zapravo jako jednostavno rešenje.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Tri kockara sa novčićima 09.03.2006. u 03:37 · pre 251 mesec #2

Hm, možda mi je rezon pogrešan, ali očekivani dobitak/gubitak svakog igrača u svakom bacanju je nula (0,5 da će izgubiti jedan novčić; 0,25 da će dobiti dva novčića; 0,25 da će ostati na istom). Ne znači li to da je očekivani broj bacanja za bilo koji konačan gubitak beskonačan?

Re: [Zadatak]: Tri kockara sa novčićima 09.03.2006. u 13:03 · pre 251 mesec #3

Izgleda da nisi u pravu. Pretpostavimo da svi imaju samo po jedan novčić. Tada je očekivani broj bacanja do ispadanja jednog od njih zapravo očekivani broj bacanja do prvog odlučenog, a to svakako nije beskonačno.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Tri kockara sa novčićima 09.03.2006. u 21:31 · pre 251 mesec #4

Ja mislim da sam resio trivijalan slucaj kad je l=m=n=1.

Meni ocekivanje ispade 4/3.

Sledi obrazlozenje ....

Potpis

tisuću lijepih žena posve nagih

Re: [Zadatak]: Tri kockara sa novčićima 09.03.2006. u 23:10 · pre 251 mesec #5

Obelezimo osobe sa A,B i C i
G - grb,
P - pismo

U prvom bacanju su moguci sledeci ishodi:

A B C
-----
G G G
G G P
G P G
G P P
P G G
P G P
P P G
P P P

Ako je GGG ili PPP igra se nastavlja jer niko ne gubi nista i svi i dalje imaju po dinar a sve ostalo dovodi da cak dve osobe ostanu bez para i tu se igra prekida.

P("GGG ili PPP")=2/8=1/4
a
P("ostalih ishoda")=3/4

Neka je X slucajna promenljiva koja predstavlja broj bacanja do prekida igre.

Dakle
P(X=1) = P("da nije GGG ni PPP") = 3/4.

Dalje,
P(X=2) = P("u prvom bacanju je bilo GGG ili PPP a u drugom bacanju jedan od ishoda
koji dovode do prekida igre, tj nije bilo ni GGG ni PPP") = 1/4*3/4

Itd, itd.

P(X=n) =
$(1/4)^{n-1}*(3/4)$

Jasno je da postoji mogucnost da se igra nikad ne zavrsi (ako svaki put padne GGG ili PPP).
Slucajna promenljiva X ima takozvanu geomertijsku raspodelu.

$\left[\matrix{% 1&2&...&n...\cr 3/4&3/4*1/4&...&3/4*1/4^{n-1}...\cr}\right]$

Zaboravio sam kako ide matematocko ocekivanje za tu raspodelu, izvescemo je po definiciji za mat. ocekivanje.

$E(X)=\sum_{n=1}^{\infty}n*(1/4)^{n-1}*(3/4)$

Kad se malo sredi, dobije se

$E(X)=3*\sum_{n=1}^{\infty}n/4^n$

Ne znam bas kako se tacko sumira ovaj red ali MCAD mi izbacio 4/9.

Sve u svemu E(X)=3*4/9=4/3

Potpis

tisuću lijepih žena posve nagih

Re: [Zadatak]: Tri kockara sa novčićima 09.03.2006. u 23:42 · pre 251 mesec #6

Citat:

peddja_stankovic:
$E(X)=3*\sum_{n=1}^{\infty}n/4^n$

Ne znam bas kako se tacko sumira ovaj red ali MCAD mi izbacio 4/9.

$S=\frac 1 4+\frac 2{4^2}+\frac 3{4^3}+\cdots=\left(\frac 1 4+\frac 1{4^2}+\frac 1{4^3}+\cdots\right)+\left(\frac 1{4^2}+\frac 2{4^3}+\frac 3{4^4}+\cdots\right)=\frac 1 4\frac 1{1-\frac 1 4}+\frac 1 4S$ , odnosno $\frac 3 4S=\frac 1 3$ , pa sledi $S=\frac 4 9$ .

Inače, rezultat je tačan, ali može i dosta jednostavnije. Neka je $E$ traženo očekivanje. Posle nerešenog bacanja očekivanje ostaje isto, pa važi relacija $E=\frac 1 4(1+E)$ , iz čega odmah dobijamo $E=\frac 4 3$ . E sad samo treba to uopštiti :)

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Tri kockara sa novčićima 10.03.2006. u 08:02 · pre 251 mesec #7

Citat:

Bojan Basic: Inače, rezultat je tačan, ali može i dosta jednostavnije. Neka je $E$ traženo očekivanje. Posle nerešenog bacanja očekivanje ostaje isto, pa važi relacija $E=\frac 1 4(1+E)$

Mala ispravka:
$E=\frac 1 4(1+E) + \frac 3 4$

Re: [Zadatak]: Tri kockara sa novčićima 10.03.2006. u 12:59 · pre 251 mesec #8

U pravu si, greška u kucanju.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Tri kockara sa novčićima 12.03.2006. u 06:50 · pre 251 mesec #9

Ja dobih za l=m=n=2 da je E=8/3.
Da li to znaci da je za l=m=n=N, E=N*4/3?

Potpis

tisuću lijepih žena posve nagih

Re: [Zadatak]: Tri kockara sa novčićima 12.03.2006. u 12:51 · pre 251 mesec #10

Citat:

peddja_stankovic:
Ja dobih za l=m=n=2 da je E=8/3.

Dobro je.

Citat:

peddja_stankovic:
Da li to znaci da je za l=m=n=N, E=N*4/3?

Ne znači, samo se slučajno potrefilo da se za prve dve mogućnosti uklapa u tu formulu.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Tri kockara sa novčićima 15.03.2006. u 22:49 · pre 251 mesec #11

Evo novih informacija.
Napravio sam sitan programcic koji simulira bacanje novcica i dobio sam sledece eksperimentalne rezultate:

neka je l=m=n=N

Vec sam dobio za

N=1 E=4/3
N=2 E=8/3

Evo nekih drugih pribliznih vrednosti:

N=3 E=5.13
N=4 E=8.52
N=5 E=12.7
N=6 E=18.1
N=7 E=24.1
N=8 E=30.5
N=9 E=38.7
N=10 E=47.67
N=11 E=57.12
....
itd.

Sad ce mi biti lakse da dodjem do analiticke formule.
Mislim da ce mi trebati manje od 25 godina

Potpis

tisuću lijepih žena posve nagih

Re: [Zadatak]: Tri kockara sa novčićima 15.03.2006. u 23:12 · pre 251 mesec #12

Fino.

Težina ovog zadatka je upravo u tome kako „nabosti“ formulu tj. njen oblik. Nisam video takav pristup da se prvo krene od $l=m=n$ ali možda može i to da pomogne. U svakom slučaju ako bude zatrebao hint javite, meni se lično jako svideo pristup koji sam video iako na kraju sve izgleda kao slučajnost.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Tri kockara sa novčićima 17.03.2006. u 01:13 · pre 251 mesec #13

Trebalo bi možda najprije riješiti ovakav zadatak:
Dva kockara imaju po N novčića.U jednom bacanju
može se jedan novčić dobiti ili izgubiti.Naći broj bacanja
S za koji postoji veća vjerovatnost da jedan od njih
ode kući praznih džepova,nego da ne ode.
----------
Za S=N vjerovatnost je mala,pa onda sa porastom S
vjerovatnost takođe raste.

Potpis

________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]

Re: [Zadatak]: Tri kockara sa novčićima 19.03.2006. u 18:06 · pre 251 mesec #14

Posmatrajmo jednakostranicni trougao koji ima visinu $l+m+n$ . Oznacimo stranice sa $a$ , $b$ i $c$ . Neka nam je pocetna tacka $P$ udaljena od stranice $a$ za duzinu $l$ , od stranice $b$ za duzinu $m$ , od stranice $c$ za duzinu $n$ . Lako je dokazati da takva tacka postoji i da je jedinstvena. Pretpostavljam da vam je jasno da ce nam pri pomeranju tacke P zbir rastojanja uvek biti $l+m+n$ . Pro svakom potezu tacku P pomeramo za vrednost 2 u pravcu jedne visine u smeru suprotnom od stranice koja odgovara toj visini. Tada ce se rastojanja od tacke P od ostalih stranica smanjiti za po 1. Znaci ovaj random walk tacke P u potpunosti odgovara igri koju igraju 2 kockara. Sada verovatno postoji nekakva formula za resavanje tog random walk-a ali ja je ne znam, mogao bih kasnije da pokusam da smislim nesto ali mislim da je moguce naci resenje i bez toga. Posto tacka P radi random walk to znaci da je $c_1 \cdot {\hbox {min}(l,m,n)}^2\le E \le c_2 \cdot (l+m+n)^2$ . To nam govori da nasa formula za E sadrzi kvadrate $l$ , $m$ i $n$ .
//edit: ispostavilo se da to nije tacno ali posto navedena nejednakost i dalje vazi onda znamo da je formula priblizno jenaka $c \cdot (l+m+n)^2$ kada su l m i n veliki (i jednaki).

Imamo $E_{l,m,n}=\frac 1 4(1+E_{l,m,n}) + \frac 1 4(1+E_{l+2,m-1,n-1}+1+E_{l-1,m+2,n-1}+1+E_{l-1,m-1,n+2})$
$E_{l,m,n}=1+\frac 1 4(E_{l,m,n} + E_{l+2,m-1,n-1}+E_{l-1,m+2,n-1}+E_{l-1,m-1,n+2})$

Pretpostavimo da je:
$E_{l,m,n}=k_1(l^2+m^2+n^2)+k_2(lm+ln+mn)+k_3(l+m+n)+k_4$
Ubacivanjem u gornju formulu, moguce je naci koeficijente $k_1$ , $k_2$ , $k_3$ i $k_4$ . Ili ako ne moze tako onda jednostavno postavimo jednacine kada je l=m=n=1 gde smo izracunali verpvatnocu 4/3 i to uradimo za jos 3 razlicite vrednosti.

Re: [Zadatak]: Tri kockara sa novčićima 19.03.2006. u 23:00 · pre 251 mesec #15

Lepo

Koeficijenti se mogu naći na osnovu $E_{a,1,1}={4\over 3}$ za $a\ge 1$ .

$k_1=0$
$k_2={4\over 9}$
$k_3=-{8\over 9}$
$k_4={8\over 3}$

Možeš li da daš neko objašnjenje za onu procenu (nije mi očigledno zašto to mora da važi), a čak i kad bih znao zašto, ne bih nikad napravio toliko dobru pretpostavku o obliku f-je

Da li nam teorema o rekurzivnoj f-ji garantuje jedinstvenost rešenja?

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak]: Tri kockara sa novčićima 20.03.2006. u 01:10 · pre 251 mesec #16

Uranijum, tvoja kalkulacija je tacna ali nesto drugo nije u redu sa formulom.
Mora da se dobije za l=3, m=2, n=1

E=2

a ne 20/9 kako se dobija na osnovu srkijeve formule i uranijumovih koeficijenata ...

Potpis

tisuću lijepih žena posve nagih

Re: [Zadatak]: Tri kockara sa novčićima 20.03.2006. u 02:37 · pre 251 mesec #17

Potpuno si u pravu

Ako zahtevamo da važi ona rekurzija, onda mora biti:

$18k_1-9k_2+4=0$ . Koeficijente tražimo rešavajući sistem:

$E_{1,2,3}=2$
$E_{2,2,2}={8\over 3}$
$E_{3,1,1}={4\over 3}$

Međutim sistem nema rešenja.

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak]: Tri kockara sa novčićima 20.03.2006. u 04:18 · pre 251 mesec #18

Citat:

uranium:
$k_1=0$
$k_2={4\over 9}$
$k_3=-{8\over 9}$
$k_4={8\over 3}$

Posto k1 mora da bude razlicito od nule onda to znaci da nisam lepo ubo formulu. Ali ona nejednakost sto sam naveo mora da vazi. To znaci da kada su l, m i n veliki i priblizno isti (ili recimo da jesu isti) onda je E priblizno $k \cdot l^2$ . Sada treba ubosti tacnu formulu. Mozda negde treba podeliti sa (l+m+n) ili tako nesto ali u svakom slucaju kada je l=m=n i kada je l veliko dobicemo priblizno $k \cdot l^2$ .

Citat:

Možeš li da daš neko objašnjenje za onu procenu (nije mi očigledno zašto to mora da važi), a čak i kad bih znao zašto, ne bih nikad napravio toliko dobru pretpostavku o obliku f-je :-)

Pogledaj http://mathworld.wolfram.com/RandomWalk2-Dimensional.html
Takodje obrati paznju da je rastojanje od sredisnje tacke sigurno manje ili jednako od poluprecnika opisanog kruga oko trogugla a to 2(l+m+n). Minimalno rastojanje je min(l,m,n) a to znaci da je E vece od neke konstante pomnozene sa kvadratom tog rastojanja...
Ako ti to nije dovoljno intiutivno onda pogledaj http://mathworld.wolfram.com/RandomWalk1-Dimensional.html gde ces videti da je za jednodimenzionalni random walk devijacija proporcionalna korenu iz N. Posto nas interesuje devijacija (tj. rastojanje od tezista) a ta devijacija u nasem slucaju je izmedju l i 2l onda sam izvukao onaj zakljucak. Naravno ovo je sve bez ikakvog matematickog dokaza, koristim samo intuiciju ali me nije stid jer je i Bojan rekao da se tako doslo do resenja :-)

Citat:

Da li nam teorema o rekurzivnoj f-ji garantuje jedinstvenost rešenja?

Verovatno ne i zato kada nabodemo formulu treba uzeti i konkretne slucajeve (npr. $E_{1,1,1}$ , $E_{2,1,1}$ itd...

Mozda mozemo i bez ubadanja formule (Bojanov komentar me naveo da to pokusam) ali onda neko treba da smisli kako da resimo dvodimenzionalni random walk u trouglu.

Da li neko ima volje da pokusa da resi onu rekurziju za $\frac {k_1(l^3 + m^3 + n^3) +k_2 (l^2m + l m^2 +...) + ...\hbox{tako dalje za sve moguce kombinacije do treceg stepena} + ..+k_x (l+m+n) } {l+m+n}$

Bojane, da li mozes da nam kazes da li smo makar blizu resenja i da li je moja pretpostavka tacna da je za veliko l=m=n resenje priblizno $k \cdot l^2$ ?

Imam jednu ideju kako da nadjemo formulu za l=m=n, sada cu da pokusam. Mislim da na slican nacin moze da se nadje i kada je l razlicito od m i n i m razlicito od n. Javicu sta sam uradio.

Re: [Zadatak]: Tri kockara sa novčićima 20.03.2006. u 06:49 · pre 251 mesec #19

@srki:

Zahvaljujem na objašnjenju - nažalost efekat je takav da mi je za sad jasna samo procena donje granice. Pročitao sam samo 2D slučaj ali ako sam dobro razumeo formula govori o ukupnom pređenom putu - tako da ipak još uvek ne kapiram onu gornju procenu...

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak]: Tri kockara sa novčićima 20.03.2006. u 08:06 · pre 251 mesec #20

Citat:

uranium: ...ali ako sam dobro razumeo formula govori o ukupnom pređenom putu - tako da ipak još uvek ne kapiram onu gornju procenu...

Ne, formula govori o krajnjem polozaju tacke (srednjoj vrednosti krajnjeg rastojanja tacke od pocetnog polozaja (devijacija)). Formula nam kaze koji je ocekivani broj koraka da tacka dosegne to rastojanje. Ukupan predjeni put je priblizno 2N*3/4 jer je 3/4 sansa da se tacka pomeri :-)

E da, naravno da krajnji polozaj tacke ne znaci da tacka u toku puta nije otisla dalje ali opet i kada bismo racunali verovatnocu da nije otisla dalje mogli bismo videti da i ta verovatnoca ima slicnu raspodelu. O tome malo kasnije, idem sada kuci pa kada tamo stignem i veceram onda cu da probam da nastavim :-)

Forum kao aplikacija na telefonu

Srodne teme