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 \| MathML
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

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)