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 file
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

Megadhatók-e az első 50 pozitív egész számnak olyan a1,a2,...,a50;b1,b2,...,b50;c1,c2,...,c50;d1,d2,...,d50 permutációi, amelyekre
i=150aibi=2i=150cidi.

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=i=150xiyi összegeket, ahol x1, x2, ..., x50; y1, y2, ..., y50 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 yi=xi, vagyis ha "nagyobb xi-hez mindig nagyobb yi tartozik'';
2) a legkisebb értéket akkor kapjuk, ha yi=51-xi, vagyis ha "nagyobb xi-hez mindig kisebb yi tartozik''.

 

Legyen ugyanis S' az az összeg, amely S-től csak abban tér el, hogy yr és ys "helyet cserélt'' (1rs50). E két összeg különbsége:
S'-S=xrys+xsyr-xryr-xsys=(xs-xr)(yr-ys).
Ha xs>xr és yr>ys, vagy xs<xr és yr<ys, 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
i=1ni=n(n+1)2ési=1ni2=n(n+1)(2n+1)6
összefüggések alapján
Smax=i=150i2=50511016=42925,Smin=i=050i(51-i)=51i=150i-i=150i2=5150512-42925=22100.



Mivel Smax<2Smin, 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 t0 elem kivételével megadható olyan t' elem, amelyre t'>t, még nem következik, hogy t0 a 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'=t2>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ó.