Kezdőlap


Feladat:	F.2587	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Beke T. , Benczúr A. , Biró J. , Blahota I. , Bóna M. , Cynolter G. , Domokos M. , Dringó L. , Habony Zs. , Hajdú G. , Illés L. , Kintli L. , Máté Nóra , Mátrai Katalin , Olasz-Szabó M. , Pál G. , Pálmai L. , Ribényi Á. , Rimányi R. , Szalay Gy. , Szederkényi Judit , Takács Á. , Vindics Péter , Zaránd G.
Füzet:	1986/november, 378 - 379. oldal		PDF \| MathML
Témakör(ök):	Szorzat, hatványozás azonosságai, Egyenlőtlenségek, Egész számok összege, Négyzetszámok összege, Permutációk, Polinomok szorzattá alakítása, Feladat
Hivatkozás(ok):	Feladatok: 1986/május: F.2587

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.

Bebizonyítjuk, hogy nem adhatók meg ilyen permutációk. Tekintsük az $S = \sum_{i = 1}^{50} x_{i} y_{i}$ összegeket, ahol $x_{1}$ , $x_{2}$ , $...$ , $x_{50}$ ; $y_{1}$ , $y_{2}$ , $...$ , $y_{50}$ az első 50 pozitív egész szám permutációi. Mivel $S$ csak véges számú értéket vehet fel, ezek között van legnagyobb és legkisebb. Először is azt fogjuk belátni, hogy
1) a legnagyobb értéket akkor kapjuk, ha $y_{i} = x_{i}$ , vagyis ha "nagyobb $x_{i}$ -hez mindig nagyobb $y_{i}$ tartozik'';
2) a legkisebb értéket akkor kapjuk, ha $y_{i} = 51 - x_{i}$ , vagyis ha "nagyobb $x_{i}$ -hez mindig kisebb $y_{i}$ tartozik''.

Legyen ugyanis

S'

az az összeg, amely

S

-től csak abban tér el, hogy

y_{r}

és

y_{s}

"helyet cserélt'' (

1 \leq r \leq s \leq 50

). E két összeg különbsége:

\begin{matrix} S' - S = x_{r} y_{s} + x_{s} y_{r} - x_{r} y_{r} - x_{s} y_{s} = (x_{s} - x_{r}) (y_{r} - y_{s}) . \end{matrix}

x_{s} > x_{r}

és

y_{r} > y_{s}

, vagy

x_{s} < x_{r}

és

y_{r} < y_{s}

, vagyis a csere során a nagyobbik

x

mellé nagyobb

y

került, akkor az összeg növekedett, ellenkező esetben pedig csökkent. Ilyen cserével az 1) pontban leírt összeg kivételével minden más összeg növelhető, a 2) pontban leírt összeg kivételével minden más összeg csökkenthető. Ebből következik, hogy az 1) pontban megadottól különböző összeg nem lehet maximális, és mivel maximális összeg létezik, ez éppen az 1)-beli. Hasonlóan adódik az állítás második része is.
Számítsuk ki ezek után

S

legnagyobb és legkisebb értékét. Az ismert

\begin{matrix} \sum_{i = 1}^{n} i = \frac{n (n + 1)}{2} és \sum_{i = 1}^{n} i^{2} = \frac{n (n + 1) (2 n + 1)}{6} \end{matrix}

összefüggések alapján

\begin{matrix} S_{max} = \sum_{i = 1}^{50} i^{2} = \frac{50 \cdot 51 \cdot 101}{6} = 42 925, \\ S_{min} = \sum_{i = 0}^{50} i (51 - i) = 51 \sum_{i = 1}^{50} i - \sum_{i = 1}^{50} i^{2} = \frac{51 \cdot 50 \cdot 51}{2} - 42 925 = 22 100. \end{matrix}

Mivel

S_{max} < 2 S_{min}

, a feladat kérdésére valóban nemleges a válasz, hiszen a kívánt egyenlőség bal oldalának legnagyobb értéke is kisebb a jobb oldal legkisebb értékénél.

Megjegyzés. Az

S

összegek minimumának és maximumának megállapításakor nagyon lényeges volt az a tény, hogy a szélsőértékek léteznek. Csupán abból, hogy egy adott

T

számhalmaz

t

elemeihez egyetlen egy

t_{0}

elem kivételével megadható olyan

t'

elem, amelyre

t' > t

, még nem következik, hogy

t_{0}

T

legnagyobb eleme.
Legyen például

T

a pozitív egész számok halmaza. Ekkor az 1 kivételével minden

t

számra

t' = t^{2} > t

, az "eljárás'' tehát az 1-től különböző számokat növeli.

T

legnagyobb eleme ‐ ha van ‐ tehát csak az 1 lehet; legnagyobb elem természetesen nem létezik, állításunk igaz, de semmitmondó.