Egy állásra ismert n számú jelölt jelentkezik, akik véletlen sorrendben jelennek meg a felvételi interjúra, és minden lehetséges sorrend egyforma valószínû. Legyen a legjobb jelölt rangja 1, a második legjobb jelölt rangja 2, és a k-ik legjobb jelölt rangja k, k=1,2,... A felvételi interjú során az éppen jelentkezõ felvételizõ jóságát össze tudjuk hasonlítani az addig megjelentekkel, azaz meg tudjuk mondani az addig megjelentek közötti relativ rangját. Ezután eldöntjük, hogy a jelöltet elfogadjuk-e vagy elbocsájtjuk, és ezt a döntést késõbb nem változtathatjuk meg. Célunk az, hogy minimalizáljuk a kiválasztott jelölt rangjának a várható értékét. Kérdés, hogy ez a rang optimális választás esetén véges számhoz tart-e, ha a jelöltek n száma tart a végtelenhez. Be lehet látni, hogy optimális választás esetén létezik véges határérték, és annak értéke is ismert.

A Secretary problem-nak csak részleges megoldását írom le. Megadom minden rögzített n számra az optimális stratégiát, illetve azt a rekurziót, melynek segítségével kiszámítható az optimális stratégia esetén a kiválasztott jelölt rangjának a várható értéke. Ennek segítségével megmutatom, hogy ennek a várható értéknek az értéke minden n számra kisebb mint 8. Annak bizonyítása, hogy létezik a fent megadott határérték a rekurzió alaposabb vizsgálatát igényli. Ez meglehetõsen fárasztó, a valószínûségszámításhoz közvetlenül nem kapcsolódó probléma. Ezért ennek részleteit nem tárgyalom, csak egy heurisztikus indoklást adok, amelyik felhasználja az optimális megoldás megadásához szükséges számsorozat néhány természetes, de bizonyításra szoruló tulajdonságát. Az érdeklõdõk a részleteket kidolgozó, teljes bizonyítást megtalálhatják Y. S. Chow, S. Moriguti, H. Robbins és M. Samuels Optimal Selection Based On Relative Ranks (the Secretary Problem) címû az Israel Journal of Mathematics (1964) 81--90 újságan megjelent cikkében.

• A megoldás ismertetésének TeX file-ja
• A megoldás ismertetésének dvi file-ja
• A megoldás ismertetésének pdf file-ja