Feladat: Gy.3233 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Bákor Krisztina ,  Bárány Zsófi ,  Csiszár Gábor ,  Dénes Attila ,  Dőrr Zsuzsanna ,  Harangi Viktor ,  Hudomiet Péter ,  Keszegh Balázs ,  Kiss Gergely ,  Kunszenti-Kovács Dávid ,  Lábó Eszter ,  Lábó Melinda ,  Leipold Diána ,  Varga Balázs ,  Venter György ,  Vizer Máté 
Füzet: 1999/szeptember, 350 - 351. oldal  PDF file
Témakör(ök): Oszthatóság, Természetes számok, Gyakorlat
Hivatkozás(ok):Feladatok: 1998/november: Gy.3233

Bizonyítsuk be, hogy akárhogyan adunk meg 100 különböző pozitív egész számot, mindig kiválasztható közülük 98, amelyeknek az összege nem osztható a megmaradó kettő összegével. (H)

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.

Legyenek a1<a2<...<a100 tetszőleges különböző pozitív egész számok, összegük j=1100aj=A, és tegyük fel, a feladat állításával ellentétben, hogy sehogyan sem választható ki közülük kettő, amelyek összege ne lenne osztója a többi 98 összegének, tehát e kettőt is hozzáadva, A-nak. Ez azt jelentené, hogy minden 1k<l100 egészre ak+alA. Nyilván A<100a100, azaz a100>A100.
Ekkor az a1+a100; a2+a100; ...; a99+a100 számok mindegyike nagyobb, mint A100, különbözőek, és feltevésünk szerint mind osztói A-nak. De A-nak nem lehet 99 különböző A-nál kisebb és A100-nál nagyobb osztója, legfeljebb csak 98:

A99,A98,A97,...,A2,
hiszen aj+a100=A már nem lehetséges, mert akkor a többi 98 szám mind 0 volna.
Így az aj+a100 számok nem lehetnek mindannyian különbözők, ez pedig ellentmond a kiindulásunknak, hogy maguk az aj-k különbözőek.
Indirekt feltevésünkkel ellentmondásra jutottunk, így a feladat állítását bebizonyítottuk.
 Venter György (Fazekas M. Főv. Gyak. Gimn., 11. o.t.)

 
Megjegyzés. Teljesen hasonló módon bizonyítható a feladat 100 és 98 helyett n-re és (n-2)-re (n3) kimondva.