Feladat: Gy.2977 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Burcsi Péter ,  Elek Péter ,  Gröller Ákos ,  Hangya Balázs ,  Lippner Gábor ,  Mátrai Tamás ,  Nyul Gábor ,  Pintér Dömötör ,  Ruzsa Gábor ,  Sánta Zsuzsa ,  Tóth Gábor Zsolt ,  Ugron Balázs ,  Varga Péter ,  Véber Miklós ,  Zsíros András 
Füzet: 1996/január, 17. oldal  PDF file
Témakör(ök): Számelrendezések, Gyakorlat
Hivatkozás(ok):Feladatok: 1995/március: Gy.2977

Egy körvonal véges sok pontjához egy-egy valós számot írtunk. Ha valamely négy egymás utáni számra (sorrendben: a, b, c, d) (a-d)(b-c)<0  igaz, akkor b-t és c-t felcserélhetjük. Bizonyítsuk be, hogy csak véges sok ilyen cserét végezhetünk.

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ölje a körre írt számokat (sorrendben) a1, a2, ..., an, és képezzük az

S=a1a2+a2a3+...+ana1
összeget. Vizsgáljuk meg, hogyan változik S értéke egy csere során. Legyen a négy egymás utáni szám a, b, c, d. A cserével b és c pozíciója változik, így az S-et alkotó összegben a következő változások jelentkeznek:
S'=S-ab-cd+ac+bd,
hiszen kezdetben (ab), (bc), (cd) voltak szomszédosak, a csere után pedig (ac), (cb), (bd), más változás nem történt. Tehát
S'-S=ac+bd-ab-cd=-(a-d)(b-c),
és ez a feltételek miatt pozitív, következésképpen S értéke egy lépés alatt szigorúan nő. Azonban csak véges sok értéket vehet föl: a számok ciklikus sorrendje már egyértelműen meghatározza S-et, azaz legfeljebb (n-1)!-féle lehet. Mindez viszont azt jelenti, hogy legfeljebb ennyi lépés után S már nem nőhet tovább, vagyis nem végezhető további csere.
 Varga Péter (Békéscsaba, Kemény G. Szki., I. o.t.) dolgozata alapján