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 pj annak a valószínűsége, hogy az irat a j-ik fiókban van (j=1,2,...,n,j=0npj=1), és azt is tudjuk, hogy a j-ik fiók átnézése Tj ideig tart. Mielőtt a keresésbe fognánk, tervet készítünk, azaz megadjuk az első n természetes szám egy i1,i2,...in, 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:
K(i1,i2,...,in)=j=1npij(Ti1+Ti2+...+Tij).(1)
Határozzuk meg a p1,...,pn, T1,...,Tn számokhoz azt az i1,i2,...,in permutációt, melyre K(i1,i2,...,in) 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 (i1, i2, ..., in) permutációt. A K(π) kifejezés pkTm alakú szorzatok összegével egyenlő. A k=m indexpárokhoz tartozó szorzatok mindegyike szerepel K(π)-ben, a km indexpárhoz tartozó szorzat pedig akkor és csak akkor szerepel benne, ha π-ben m megelőzi k-t, vagyis az m-edik fiókot előbb akarjuk megnézni, mint a k-adikat. Ha szabadon választhatnánk meg minden km indexpárhoz, hogy a pkTm és pmTk szorzatok közül melyik szerepeljen K(π)-ben, nyilván a kisebbiket választanánk. Eszerint előbb kellene megnézni az m-edik fiókot, mint a k-adikat, ha

pkTm<pmTk,(2)
azaz ha
pkTk<pmTm(3)
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 K(π) értéke, ha tetszőleges km indexpárra (3) akkor és csak akkor teljesül, ha π-ben m megelőzi k-t, azaz ha
pi1Ti1pi2Ti2...pinTin,(4)
ezzel ugyanis egy csapásra biztosítjuk, hogy a pkTm, pmTk szorzatpárok közül mindig a kisebbik szerepeljen K(π)-ben. (Természetesen, ha a pT hányadosok között egyenlőek is vannak, akkor minden olyan π permutációra minimális K(π) értéke, amelyikre (4) teljesül.)
 

Pap Gyula (Debrecen, Fazekas M. Gimn., IV. o. t)