|
Feladat: |
Pontversenyen kívüli P.114 |
Korcsoport: 18- |
Nehézségi fok: nehéz |
Megoldó(k): |
Balogh Zoltán , Breuer P. , Füredi Zoltán , Hermann Péter , Nemeskéri I. , Pap Gyula , Stachó Balázs , Totik V. , Turán Gy. |
Füzet: |
1972/április,
171 - 172. oldal |
PDF file |
Témakör(ök): |
Permutációk, Várható érték, Pontversenyen kívüli probléma |
Hivatkozás(ok): | Feladatok: 1971/október: Pontversenyen kívüli P.114 |
|
Egy fontos iratot keresünk az íróasztalunkban. Tudjuk, hogy annak a valószínűsége, hogy az irat a -ik fiókban van , és azt is tudjuk, hogy a -ik fiók átnézése ideig tart. Mielőtt a keresésbe fognánk, tervet készítünk, azaz megadjuk az első természetes szám egy , permutációját és ebben a sorrendben fogjuk végignézni a fiókokat mindaddig, amíg az iratot meg nem találjuk. E mellett a terv mellett a keresési idő várható értéke: | | (1) | Határozzuk meg a , számokhoz azt az permutációt, melyre minimális.
|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Jelöljük -vel az (, , , ) permutációt. A kifejezés alakú szorzatok összegével egyenlő. A indexpárokhoz tartozó szorzatok mindegyike szerepel -ben, a indexpárhoz tartozó szorzat pedig akkor és csak akkor szerepel benne, ha -ben megelőzi -t, vagyis az -edik fiókot előbb akarjuk megnézni, mint a -adikat. Ha szabadon választhatnánk meg minden indexpárhoz, hogy a és szorzatok közül melyik szerepeljen -ben, nyilván a kisebbiket választanánk. Eszerint előbb kellene megnézni az -edik fiókot, mint a -adikat, ha azaz ha teljesül, ha pedig e két hányados egyenlő, akkor a két fiók megnézésének a sorrendje (ebből a szempontból) közömbös. Minimális lesz tehát értéke, ha tetszőleges indexpárra (3) akkor és csak akkor teljesül, ha -ben megelőzi -t, azaz ha | | (4) | ezzel ugyanis egy csapásra biztosítjuk, hogy a , szorzatpárok közül mindig a kisebbik szerepeljen -ben. (Természetesen, ha a hányadosok között egyenlőek is vannak, akkor minden olyan permutációra minimális értéke, amelyikre (4) teljesül.)
Pap Gyula (Debrecen, Fazekas M. Gimn., IV. o. t) |
|
|