Tri prijatelja večeraju u restoranu

PostPoslato: Subota, 02. Decembar 2017, 15:21
od desideri
Evo jednog interesantnog i rekao bih laganog zadatka:

Tri prijatelja večeraju u restoranu. Konobar je pobrkao njihove tri porudžbine, pa im je nasumično servirao. Kolika je verovatnoća da nijedan od njih trojice neće dobiti svoju poružbinu (sve poružbine su različite).

Očigledno je da je ukupan broj mogućnosti [inlmath]3![/inlmath]. Naravno, [inlmath]3[/inlmath] jela na tri pozicije, broj permutacija. Ja sam onda tražio broj povoljnih permutacija.
Posmatrao sam to preko brojeva [inlmath]1[/inlmath], [inlmath]2[/inlmath] i [inlmath]3[/inlmath].
Broj [inlmath]1[/inlmath] ne sme biti na prvoj poziciji, broj [inlmath]2[/inlmath] ne sme biti na drugoj poziciji i broj [inlmath]3[/inlmath] ne sme biti na trećoj poziciji.
Evidentno je da su povoljne samo dve permutacije:
[inlmath]231[/inlmath] i [inlmath]312[/inlmath]
Ovo znači da je tražena verovatnoća [inlmath]\frac{1}{3}[/inlmath]

Razmisljao sam o uopštenju zadatka. Ovo moje brojanje "na prste" mi se ne sviđa. Šta bi bilo da je broj osoba [inlmath]n[/inlmath] kao i broj jela (različitih)?
Pokušao sam, no mi se čini jako zahtevnim.
p.s. Od zadatka može da se ogladni. :D

Re: Tri prijatelja večeraju u restoranu

PostPoslato: Nedelja, 03. Decembar 2017, 02:16
od Daniel
Interesantan zadatak. :thumbup: Može se raditi preko formule uključivanja i isključivanja. Ako mi padne na pamet još koji način, dopisaću – al' zasad ovako.

Hajde prvo da vidimo broj nepovoljnih slučajeva. Znači, broj slučajeva kod kojih je bar jedna porudžbina stigla svom poručiocu. Obeležimo sa [inlmath]A_i[/inlmath] događaj da je [inlmath]i[/inlmath]-ta porudžbina stigla svom poručiocu. Npr. [inlmath]A_5[/inlmath] znači da je [inlmath]5.[/inlmath] porudžbina stigla [inlmath]5.[/inlmath] poručiocu, dok za ostale ne znamo jesu li stigle svojim poručiocima ili ne. Ili, [inlmath]A_4\cap A_7[/inlmath] znači da su [inlmath]4.[/inlmath] i [inlmath]8.[/inlmath] porudžbina stigle [inlmath]4.[/inlmath] i [inlmath]8.[/inlmath] poručiocu respektivno, dok za ostale ne znamo jesu li stigle svojim poručiocima ili ne.

Tada će broj nepovoljnih slučajeva biti
[dispmath]\sum_{i=1}^n|A_i|-\sum_{1\le i<j\le n}|A_i\cap A_j|+\sum_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap A_2\cap\cdots\cap A_n|[/dispmath] Pri tome:
[inlmath]\sum\limits_{i=1}^n|A_i|=n(n-1)![/inlmath] (jer prvo od [inlmath]n[/inlmath] elemenata biramo [inlmath]1[/inlmath] element koji će biti na svom mestu, a zatim preostalih [inlmath]n-1[/inlmath] možemo slobodno raspoređivati;
[inlmath]\sum\limits_{1\le i<j\le n}|A_i\cap A_j|={n\choose2}(n-2)![/inlmath] (jer prvo od [inlmath]n[/inlmath] elemenata biramo [inlmath]2[/inlmath] elementa koja će biti na svojim mestima, a zatim preostalih [inlmath]n-2[/inlmath] možemo slobodno raspoređivati;
[inlmath]\sum\limits_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|={n\choose3}(n-3)![/inlmath] (jer prvo od [inlmath]n[/inlmath] elemenata biramo [inlmath]3[/inlmath] elementa koja će biti na svojim mestima, a zatim preostalih [inlmath]n-3[/inlmath] možemo slobodno raspoređivati;
[inlmath]\vdots[/inlmath]

Prema tome, broj nepovoljnih slučajeva iznosi:
[dispmath]n(n-1)!-{n\choose2}(n-2)!+{n\choose3}(n-3)!-\cdots+(-1)^{n+1}(n-n)![/dispmath] dok ćemo broj povoljnih slučajeva dobiti kada od ukupnog broja slučajeva ([inlmath]n![/inlmath]) oduzmemo broj nepovoljnih:
[dispmath]\cancel{n!}-\cancel{n(n-1)!}+{n\choose2}(n-2)!-{n\choose3}(n-3)!+\cdots+(-1)^n(n-n)![/dispmath] što možemo zapisati u obliku sume,
[dispmath]\enclose{box}{\sum_{k=2}^n(-1)^k{n\choose k}(n-k)!}[/dispmath] Tražena verovatnoća se, naravno, dobije kada se prethodni izraz podeli sa [inlmath]n![/inlmath]...

Re: Tri prijatelja večeraju u restoranu

PostPoslato: Nedelja, 03. Decembar 2017, 16:38
od Daniel
Aj' da doćeram ovo do kraja, budući da naknadno uočih da se to može još srediti...

Naravno, [inlmath]{n\choose k}(n-k)![/inlmath] se može napisati i kao [inlmath]\frac{n!}{k!}[/inlmath], tako da se broj povoljnih slučajeva svodi na
[dispmath]n!\sum_{k=2}^n\frac{(-1)^k}{k!}[/dispmath] dok je tražena verovatnoća (kada se ovaj izraz podeli brojem ukupnih slučajeva [inlmath]n![/inlmath]),
[dispmath]\enclose{box}{P(n)=\sum_{k=2}^n\frac{(-1)^k}{k!}}[/dispmath] Ovde možemo uočiti sličnost s razvojem funkcije [inlmath]\frac{1}{e^x}[/inlmath] u Maklorenov red,
[dispmath]\frac{1}{e^x}=1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\frac{x^4}{4!}-\cdots[/dispmath] što nakon uvrštavanja [inlmath]x=1[/inlmath] daje
[dispmath]\frac{1}{e}=\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\cdots=\sum_{k=2}^\infty\frac{(-1)^k}{k!}[/dispmath] odakle sledi da [inlmath]P(n)[/inlmath] konvergira ka [inlmath]\frac{1}{e}[/inlmath]:
[dispmath]\lim_{n\to\infty}P(n)=\lim_{n\to\infty}\sum_{k=2}^n\frac{(-1)^k}{k!}=\frac{1}{e}[/dispmath] To, zapravo, znači da u nekom teorijskom slučaju kad imamo beskonačno mnogo gostiju restorana, pri čemu konobar pobrka njihove porudžbine (koje su sve različite) i svima ih podeli po random redosledu, verovatnoća da baš niko od tih beskonačno mnogo gostiju neće dobiti svoju porudžbinu iznosi – tačno [inlmath]\frac{1}{e}[/inlmath]. Meni lično je ovaj rezultat fascinantan, jer je to još jedan primer kako se broj [inlmath]e[/inlmath] pojavljuje u prirodi čak i tamo gde ga najmanje očekujemo. :)

Može se videti da red preko koga je predstavljena verovatnoća [inlmath]P(n)[/inlmath] vrlo brzo konvergira ka [inlmath]\frac{1}{e}[/inlmath],
[dispmath]\begin{array}{|c|c|c|c|c|c|c} \hline
n & 2 & 3 & 4 & 5 & 6 & \cdots\\ \hline
P(n) & \displaystyle\frac{1}{2} & \displaystyle\frac{1}{3} & \displaystyle\frac{3}{8} & \displaystyle\frac{11}{30} & \displaystyle\frac{53}{144} & \cdots\\ \hline
\displaystyle\left|\frac{1}{e}-P(n)\right| & 0,1321 & 0,0345 & 0,0071 & 0,0012 & 0,0002 & \cdots\\ \hline
\end{array}[/dispmath] tako da se već negde za [inlmath]n\ge4[/inlmath] ili [inlmath]n\ge5[/inlmath] verovatnoća [inlmath]P(n)[/inlmath] može s priličnom tačnošću aproksimirati sa [inlmath]\frac{1}{e}[/inlmath]...

Re: Tri prijatelja večeraju u restoranu

PostPoslato: Subota, 01. Maj 2021, 07:09
od miki069
Bravo za vrhunsko objasnjenje. Interesantno je jos da kada [inlmath]n[/inlmath] tezi beskonacno, verovatnoca tezi ka [inlmath]\frac{1}{e}[/inlmath], a to je oko [inlmath]37\%[/inlmath]. Intuitivno sam ocekivao mnogo manje.