Kezdőlap


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

p_{j}

annak a valószínűsége, hogy az irat a

j

-ik fiókban van

(j = 1,2, ..., n, \sum_{j = 0}^{n} p j = 1)

, és azt is tudjuk, hogy a

j

-ik fiók átnézése

T_{j}

ideig tart. Mielőtt a keresésbe fognánk, tervet készítünk, azaz megadjuk az első

n

természetes szám egy

i_{1}, i_{2}, ... i_{n}

, 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:

\begin{matrix} K (i_{1}, i_{2}, ..., i_{n}) = \sum_{j = 1}^{n} p_{i_{j}} (T_{i_{1}} + T_{i_{2}} + ... + T_{i_{j}}) . \end{matrix}

(1)

Határozzuk meg a

p_{1}, ..., p_{n}

T_{1}, ..., T_{n}

számokhoz azt az

i_{1}, i_{2}, ..., i_{n}

permutációt, melyre

K (i_{1}, i_{2}, ..., i_{n})

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 ( $i_{1}$ , $i_{2}$ , $...$ , $i_{n}$ ) permutációt. A $K (π)$ kifejezés $p_{k} T_{m}$ alakú szorzatok összegével egyenlő. A $k = m$ indexpárokhoz tartozó szorzatok mindegyike szerepel $K (π)$ -ben, a $k \neq m$ 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 $k \neq m$ indexpárhoz, hogy a $p_{k} T_{m}$ és $p_{m} T_{k}$ 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

\begin{matrix} p_{k} T_{m} < p_{m} T_{k}, \end{matrix}

(2)

azaz ha

\begin{matrix} \frac{p_{k}}{T_{k}} < \frac{p_{m}}{T_{m}} \end{matrix}

(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

k \neq m

indexpárra (3) akkor és csak akkor teljesül, ha

π

-ben

m

megelőzi

k

-t, azaz ha

\begin{matrix} \frac{p_{i_{1}}}{T_{i_{1}}} \geq \frac{p_{i_{2}}}{T_{i_{2}}} \geq ... \geq \frac{p_{i_{n}}}{T_{i_{n}}}, \end{matrix}

(4)

ezzel ugyanis egy csapásra biztosítjuk, hogy a

p_{k} T_{m}

p_{m} T_{k}

szorzatpárok közül mindig a kisebbik szerepeljen

K (π)

-ben. (Természetesen, ha a

\frac{p}{T}

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)