Jóval a királylányos kaland előtt Arszlán a török szultán segítségére volt valamely gaztett elkövetésében, amelynek részleteit mára már homály fedi. Fizetségül és hálája jeléül a szultán egy hölgyet ajánlott Arszlánnak saját háreméből.
A hölgyek egymás után jöttek be a palotába, Arszlán pedig egyesével eldönthette, hogy megelégszik-e az adott hölggyel, vagy inkább megnézi a következőt. Mivel utólag vissza már nem hívhatott hölgyeket, mindössze annyit tehetett, hogy előbb felmérte a háremet az első néhány lány megtekintésével, és ezután kiválasztotta az első olyat, aki szebb volt az addigiaknál.
Természetesen, ha túl sok lányt nézett volna meg az elején, akkor a végén talán egy csinosabb sem lett volna náluk, így nagyon is fontos ennek az előzetes felmérési szakasznak a hossza.
Ha tudjuk, hogy a háremben 300 lány volt, és teljesen véletlenszerű sorrendben vonultak fel, hány lányból álljon a felmérés ahhoz, hogy a legnagyobb legyen az esély a legszebb kiválasztására?
Comments are closed.
ha jól sejtem nem azért vannak 300-an, mert Spártai özvegyek
s
Remélem nem számoltam el semmit, és hülyeséget sem írok. 🙂
n=300
k=? (felmérésben résztvevő lányok száma)
Az egyszerűség kedvéért feltettem, hogy nincsen két ugyanannyira szép lány.
Egy kis részfeladatként tegyük fel, hogy a legszebb lány az s-edik. Annak az esélye, hogy egy rögzített “s” esetén az s-edik lány legyen a legszebb:
P(s-edik a legszebb) = 1/n
Számoljuk ki egy ilyen esetre annak a valószínűségét, hogy az adott algoritmussal sikerül eljutnunk a legszebb lányig. Először vizsgáljuk meg, hányféleképpen jöhetnek a legszebb lány előtt a lányok. Ez n-1 elem (maradék lányok) “s-1”-ed osztályú ismétlés nélküli variációinak a számával egyenlő:
V_(n-1)^(s-1) = (n-1) * (n-2) * … * (n-s+1)
Ebből a kedvező esetek (amikor ki tudjuk választani a legszebb lányt) számát is ki tudjuk számolni. Ugyanis ezekből az esetekből számunkra azok a kedvezőek, amelyekben az első s-1 lány közül a legszebb lány (nevezzük parciálisan második legszebbnek) az első “k” között van. Ha ez teljesül, akkor biztosan eljutunk az s-edik lányig, aki a legszebb mind közül. Ha nem teljesül, akkor viszont biztosan nem jutunk el, hiszen az algoritmusunk szerint a parciálisan második legszebbnél fogunk megállni vagy valahol előtte.
Annak az esélye, hogy a parciálisan második legszebb az első “k” lány között legyen: k/(s-1), tehát a kedvező esetek száma:
V_(n-1)^(s-1) * k/(s-1)
Tehát annak a valószínűsége, hogy az algoritmusunkkal egy rögzített “s” esetén eljutunk a legszebb lányig, aki az s-edik lány:
P_k(siker | s-edik a legszebb) = (V_(n-1)^(s-1) * k/(s-1)) / V_(n-1)^(s-1) * k/(s-1) = k/(s-1)
Azt már tudjuk, hogy:
P(s-edik a legszebb) = 1/n
Tehát a feltételes valószínűség definíciója alapján:
P_k(s-edik a legszebb és siker) = P(s-edik a legszebb) * P_k(siker | s-edik a legszebb) = 1/n * k/(s-1)
A képletből is látszik, de jobban belegondolva is világos, hogy s-1 nem lehet kisebb, mint “k” (azaz szükséges, hogy s>k), hiszen ha kisebb lenne, akkor a valószínűség 1-nél nagyobb lenne, vagy másként fogalmazva, a legszebb lány az első “k” között lenne, így esélyünk sem lenne őt később kiválasztani. Ezért a siker valószínűsége:
P_k(siker) = sum[s=(k+1)..n](P_k(s-edik a legszebb és siker)) = sum[s=(k+1)..n](1/n * k/(s-1)) = k/n * sum[s=k..(n-1)](1/s) = k/n * (H_(n-1) – H_(k-1))
ahol H_n az n-edik harmonikus szám: H_n = sum[i=1..n](1/i)
A P_k(siker) sorozatból (k=1..(n-1)) kellene kiválasztani a maximális értéket, ami nem egyszerű, szóval inkább helyettesítsünk be:
P_k(siker) = k/300 * (H_(299) – H_(k-1))
Ezt már könnyedén kiszámolhatjuk pl. a WolframAlpha segítségével, aki ráadásul volt olyan kedves, és kérés nélkül kiszámolta a lokális maximumot, ami kb. 110.179-nél van:
http://www.wolframalpha.com/input/?i=k%2F300*%28HarmonicNumber%28299%29+-+HarmonicNumber%28k-1%29%29
Kiszámolva k=110-et és k=111-et kijön, hogy a k=110 nagyobb valószínűséget ad, tehát az egészek között az lesz a maximum:
P_110(siker) ≈ 36.8935 %
Tehát 110 lányt kell előzetesen megnézni ahhoz, hogy az algoritmusunkkal a lehető legnagyobb valószínűséggel ki tudjuk választani a legszebb lányt.
Gyönyörű feladat. Minden szempontból. 🙂
Jól tolod, drága barátaim! Neked érdemes feladatot feladni.
A “P_k(siker | s-edik a legszebb)” formulát persze sikerült elírnom (éljen a copy-paste). Helyesen így van:
P_k(siker | s-edik a legszebb) = (V_(n-1)^(s-1) * k/(s-1)) / V_(n-1)^(s-1) = k/(s-1)
természetesen.
na, most van az, hogy logout
🙂
magyarázom a bizonyítványom – régebbről emlékeztem, de csak arra, hogy vmi szép 🙂 szám, és nagyságrendileg stimmelt is az egyharmad – de most látom , hogy 1/e