Feladat: Pontversenyen kívüli P.114 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1971/október, 78. oldal  PDF  |  MathML 
Témakör(ök): Permutációk, Várható érték, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok megoldásai: 1972/április: Pontversenyen kívüli P.114

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.

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.