Fórum: Szindbád problémája

Úgy látom, hogy a probléma nem mozgatta meg senki fantáziáját, viszont nem szeretném, ha így félben maradna, ezért elmondok két megoldást, amelyek ugyan mindketten a teljes valószínűség tételén alapulnak, de mégis különbözőek.

1. megoldás:

Legyen $\displaystyle A_m$ az az esemény, hogy az első $\displaystyle k$ háremhölgy között a legszebb szépségindexe $\displaystyle m$. Határozzuk meg ennek valószínűségét a klasszikus $\displaystyle (\frac{kedvező~esetek~száma}{összes~esetek~száma})$ képlettel! $\displaystyle m$ értékei nyilván $\displaystyle k,k+1,...,n$ lehetnek.

Az összes esetek száma nyilván $\displaystyle n!$

A kedvező esetek számához a következőképpen jutunk:

1. az első $\displaystyle k$ háremhölgy kiválasztását úgy kezdjük, hogy kiválasztjuk az $\displaystyle m$ szépségindexűt, és választunk hozzá még $\displaystyle k-1$-et a kevésbé szépek közül. Ezek száma nyilván $\displaystyle m-1$ tehát ezt a kiválasztást $\displaystyle \binom{m-1}{k-1}$ féleképpen tehetjük meg.

2. az első $\displaystyle k$ háremhölgyet $\displaystyle k!$ féle sorrendben helyezhetjük el, míg a maradék $\displaystyle n-k$ háremhölgyet $\displaystyle (n-k)!$ féle sorrendben.

3. így a kedvező esetek száma: $\displaystyle \binom{m-1}{k-1}k!(n-k)!$

Ezek alapján $\displaystyle A_m$ valószínűsége: $\displaystyle P(A_m)=\frac{\binom{m-1}{k-1}k!(n-k)!}{n!}=\frac{\binom{m-1}{k-1}}{\binom{n}{k}}$.

Legyen $\displaystyle B$ az az esemény, hogy Szindbádnak sikerül kiválasztania a legszebb háremhölgyet.

Ha az első $\displaystyle k$ háremhölgy között a legszebb szépségindexe $\displaystyle m$, akkor Szindbád abban az esetben tudja kiválasztani a legszebbet, ha az $\displaystyle m$ szépségindexű háremhölgynél szebbek közül a legszebb jön először. Az $\displaystyle m$ szépségindexű háremhölgynél szebbek száma $\displaystyle n-m$ és mindegyikük egyenlő valószínűséggel jön elsőnek, így annak valószínűsége, hogy a legszebb jön először $\displaystyle \frac{1}{n-m}$.

Így $\displaystyle P(B|A_m)=\frac{1}{n-m}$, illetve $\displaystyle 0$, ha $\displaystyle m=n$ (hiszen Szindbád hoppon marad). A teljes valószínűség tétele alapján

$\displaystyle P(B)=\sum_{m=k}^{n-1} \frac{1}{n-m}\frac{\binom{m-1}{k-1}}{\binom{n}{k}}=\frac{1}{\binom{n}{k}} \sum_{m=k}^{n-1} \frac{\binom{m-1}{k-1}}{n-m}$

2. megoldás:

Legyen $\displaystyle C_i$ az az esemény, hogy a legszebb hölgy $\displaystyle i$-ediknek érkezik. Nyilván ennek valószínűsége $\displaystyle \frac{1}{n}$, hiszen minden helyen egyforma valószínűséggel érkezhet. Legyen $\displaystyle B$ az az esemény, hogy Szindbádnak sikerül kiválasztania a legszebb háremhölgyet. Nézzük meg, mennyi a valószínűsége annak, hogy Szindbád a legszebbet választja, ha az $\displaystyle i$-ediknek érkezik, azaz keressük $\displaystyle P(B|C_i)$ értékét!

1. Ha $\displaystyle i\leq k$, akkor nyilván Szindbád nem tudja kiválasztani a legszebbet, hiszen az elment az orra előtt az első $\displaystyle k$ között (hoppon marad), így $\displaystyle P(B|C_i)=0$

2. Ha $\displaystyle i>k$, akkor Szindbád akkor választja a legszebbet, ha az előtte érkező $\displaystyle i-1$ hölgy közül a legszebb benne van az első $\displaystyle k$-ban, tehát a lehetséges $\displaystyle i-1$ azonos valószínűségű lehetőség közül $\displaystyle k$ kedvező van. Így $\displaystyle P(B|C_i)=\frac{k}{i-1}$.

Így a teljes valószínűség tétele alapján

$\displaystyle P(B)=\sum_{i=k+1}^{n} \frac{k}{i-1}\frac{1}{n}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$

Következmények:

1. Ha mindkét megoldás hibátlan, akkor

$\displaystyle \frac{1}{\binom{n}{k}} \sum_{m=k}^{n-1} \frac{\binom{m-1}{k-1}}{n-m}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$

ami a 2023-09-29-én közreadott Egy érdekes egyenlőség.

2. $\displaystyle \int_k^n \frac{1}{x} dx < \sum_{i=k+1}^{n}\frac{1}{i-1}< \int_{k-1}^{n-1} \frac{1}{x} dx$, azaz $\displaystyle \ln(\frac{n}{k}) < \sum_{i=k+1}^{n}\frac{1}{i-1}<\ln(\frac{n-1}{k-1})$, így $\displaystyle \frac{k}{n}\ln(\frac{n}{k}) < \frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}<\frac{k}{n}\ln(\frac{n-1}{k-1})$, ezért, ha $\displaystyle f(x)=\frac{1}{x}\ln(x)$ , akkor $\displaystyle P(B)\approx f(\frac{n}{k})$. Mivel $\displaystyle f(x)$ maximuma $\displaystyle x=e$-nél van, ezért Szindbád akkor választja ki legnagyobb eséllyel a legszebb hölgyet, ha $\displaystyle \frac{n}{k}\approx e$. Mivel $\displaystyle f(e)=\frac{1}{e}$, ezért $\displaystyle P(B) < \frac{1}{e}$.

Az utolsó kérdésre a válasz megtalálása nem igényel újabb gondolatot, ezért csak leírom:

$\displaystyle P(\xi = m)=\sum_{i=k+1}^{m} \frac{\binom{m-1}{i-1}}{\binom{n}{i}}\frac{1}{i}\frac{k}{i-1},$

ha $\displaystyle m=k+1, k+2, ..., n$ és

$\displaystyle P(\xi = 0)=\frac{k}{n}$

A probléma talán ismerős lesz sokaknak, de az érdekelne, hogy milyen különböző megoldásokat ismertek.

A probléma:

Szindbád megmentette a szultán életét, ezért a szultán hálából felajánlotta, hogy Szindbád válasszon magának egyet a szultán $\displaystyle n$ háremhölgye közül. A háremhölgyek valamilyen véletlenszerű sorrendben egyesével sétálnak el Szindbád előtt, és akire Szindbád rámutat, azt fogja megkapni. A háremhölgyek azonban csak egyszer jelennek meg, így aki elhaladt, azt már visszahívni nem lehet. Szindbád természetesen a legszebbet szeretné kiválasztani és ezért elhatározza, hogy a $\displaystyle k$-stratégiát fogja követni, azaz $\displaystyle k$ háremhölgyet elenged anélkül, hogy közülük választana, majd kiválasztja az első olyat, aki az összes korábbinál szebb. Feltételezzük, hogy a szépség objektíven megállapítható és a háremhölgyeket el lehet látni egy sorszámmal $\displaystyle 1$ és $\displaystyle n$ között (szépségindex) úgy, hogy minél szebb valaki, annál nagyobb a szépségindexe. A megválaszolandó kérdések ezek után:

1. Mekkora a valószínűsége annak, hogy Szindbád így a legszebb háremhölgyet fogja kiválasztani?

2. Hogyan állapítsa meg Szindbád a $\displaystyle k$ értékét ahhoz, hogy ez a valószínűség a legnagyobb legyen?

3. Legyen a $\displaystyle \xi$ valószínűségi változó értéke 0, ha Szindbád hoppon marad (azaz a legszebb háremhölgy az első $\displaystyle k$ között volt és ezért nem tudott választani), egyébként pedig a kiválasztott hölgy szépségindexe. Adjuk meg a valószínűségi változó eloszlását!