Feladat: Gy.2055 Korcsoport: 14-15 Nehézségi fok: nehéz
Megoldó(k):  Bangha I. ,  Baráti Á. ,  Bujdosó 419 L. ,  Böröczky L. ,  Csillag P. ,  Edvi T. ,  Erdős 228 L. ,  Fodor Gy. ,  Hajdú S. Z. ,  Hraskó A. ,  Kerner Anna ,  Kovács 829 T. ,  Oravecz A. ,  Sárközy G. ,  Simon P. ,  Somogyi 196 A. ,  Szabó 741 Z. 
Füzet: 1983/február, 67 - 68. oldal  PDF file
Témakör(ök): Természetes számok, Abszolútértékes egyenletek, Szélsőérték-feladatok differenciálszámítás nélkül, Gyakorlat
Hivatkozás(ok):Feladatok: 1982/május: Gy.2055

Milyen határok között változik az alábbi kifejezés értéke, ha a1,a2,...,a10 helyére rendre beírjuk minden lehetséges sorrendben az első 10 pozitív egész számot ?
K=|a1-a2|+|a2-a3|+...+|a9-a10|+|a10-a1|

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.

Az |x-y| értéke (x-y) vagy (y-x) attól függően, hogy x és y közül melyik a nagyobb. Így ha a K kifejezésben felbontjuk az abszolút érték jeleket, akkor az 1,2,...10 számok mindegyike kétszer szerepel, mégpedig úgy, hogy a húsz szám közül tíznek pozitív, tíznek pedig negatív az előjele. Ez azt jelenti, hogy K értéke legfeljebb 2(10+9+9+8+7+6)-2(1+2+3+4+5)=50 lehet. Ez viszont lehetséges is, például úgy, ha a1=10,a2=1,a3=9,a4=2,a5=8,a6=3,a7=7,a8=4,a9=6,a10=5.
K legkisebb értékének megkereséséhez indítsunk el egy bogarat a számegyenesen a1-ből. Menjen először a2-be, onnan tovább a3-ba, majd a4-be, és így tovább, végül a10-ből vissza a1-be. K értéke nyilván a bogár körutazásának a hossza. Azt állítjuk, hogy útja közben a bogár az [1;10] intervallum minden pontján legalább kétszer halad át. Az egész számokra ez nyilván igaz, mert minden egész szám egy szakasz kezdő és egy másik szakasz végpontja. Ha x nem egész, akkor van olyan ai, amelyet x elválaszt a1-től. Ekkor a1-ből ai-be menet a bogár áthalad x-en, és mivel útja a1-ben végződik, ezért legalább még egyszer érintenie kell x-et.
A bogár tehát legalább kétszeresen járja be az [1;10] szakaszt, így K legalább kétszer akkora, mint a szakasz hossza, azaz legalább 18. Ez lehetséges is, például úgy, ha ai=i(i=1,2,...,10). Így 18K50.

 
Megjegyzés. Ha a feladatban 10 helyett n-et írunk (n2), akkor a fenti gondolatmenettel belátható, hogy 2n-2K[n2/2]. Megmutatható, hogy e határok között K minden páros értéket fölvesz.