Kezdőlap


Feladat:	B.4172	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2010/január, 27 - 28. oldal		PDF \| MathML
Témakör(ök):	Feladat, Teljes indukció módszere, Permutációk
Hivatkozás(ok):	Feladatok: 2009/április: B.4172

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.

Megoldás. A zárójeleket felbontva és rendezve:

\begin{matrix} \sum_{i = 1}^{n} {(i - k_{i})}^{2} = \sum_{i = 1}^{n} i^{2} + k_{i}^{2} - 2 i k_{i} = 2 \cdot \sum_{i = 1}^{n} i^{2} - 2 \sum_{i = 1}^{n} i \cdot k_{i} . \end{matrix}

A kifejezés értéke akkor a legnagyobb, amikor a

\begin{matrix} K = \sum_{i = 1}^{n} i \cdot k_{i} \end{matrix}

összeg a legkisebb. Először megmutatjuk, hogy ez

k_{i} = n + 1 - i

esetén következik be. Tekintsünk ehhez egy tetszőleges

k_{1}, k_{2}, k_{3}, ..., k_{n}

sorrendet, és tegyük fel, hogy valamilyen

i < j

-re

k_{i} < k_{j}

. Cseréljük fel

k_{i}

-t és

k_{j}

-t, azaz legyen

k_{i}' = k_{j}

és

k_{j}' = k_{i}

; a többi elem sorrendjén nem változtatunk. A cserével kapott összeget jelölje

K'

; ekkor

\begin{matrix} K' - K & = (i \cdot k_{i}' + j \cdot k_{j}') - (i \cdot k_{i} + j \cdot k_{j}) = (i \cdot k_{j} + j \cdot k_{i}) - (i \cdot k_{i} + j \cdot k_{j}) = \\ = (i - j) (k_{j} - k_{i}) < 0, \end{matrix}

azaz

K' < K

. Ilyen cserék sorozatával bármilyen sorrendből eljuthatunk ahhoz, ahol a számok csökkenő rendben követik egymást, és az ehhez tartozó összeg értéke a kiindulásinál kisebb.
Hátra van még ennek a minimális értékű összegnek, illetve az eredeti kifejezés maximális értékének a kiszámítása:

\begin{matrix} 2 \cdot \sum_{i = 1}^{n} i^{2} - 2 \sum_{i = 1}^{n} i \cdot (n + 1 - i) = 4 \cdot \sum_{i = 1}^{n} i^{2} - (2 n + 2) \sum_{i = 1}^{n} i = \\ = & 4 \cdot \frac{n (n + 1) (2 n + 1)}{6} - (2 n + 2) \cdot \frac{n (n + 1)}{2} = \frac{n (n + 1) (n - 1)}{3} . \end{matrix}