Feladat: Gy.2656 Korcsoport: 16-17 Nehézségi fok: könnyű
Megoldó(k):  Csermely Zoltán ,  Csörnyei Marianna ,  Farkas Zénó ,  Futó Gábor ,  Győry Máté ,  György András ,  Kálmán Tamás ,  Marx Gábor ,  Molnár-Sáska Gábor ,  Németh Ákos ,  Róka Dániel ,  Szeidl Ádám ,  Szendrei Tamás 
Füzet: 1991/szeptember, 261. oldal  PDF file
Témakör(ök): Indirekt bizonyítási mód, Természetes számok, Gyakorlat
Hivatkozás(ok):Feladatok: 1990/november: Gy.2656

Adott 19 különböző, 91-nél kisebb pozitív egész szám. Igaz-e, hogy a különbségeik között van legalább három egyforma szám?

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.

Rendezzük a számokat nagyság szerint növekvő sorrendbe: legyen a1<a2<...<a19. Megmutatjuk, hogy már akkor is igaz a feladat állítása, ha a fenti sorban csak a szomszédos számok különbségeit vesszük figyelembe. Jelölje ezeket a különbségeket di=ai+1-ai, ahol 1i18. Ekkor di>0, másrészt ezeknek a különbségeknek az összege éppen a legnagyobb és a legkisebb szám különbsége, azaz d1+d2+...+d18=a19-a1.
Tegyük fel, hogy a di-vel jelölt különbségek között nincsen három egyenlő szám, azaz minden érték legfeljebb kétszer fordul elő közöttük. Ekkor e tizennyolc szám összege legalább akkora, mint a kilenc legkisebb pozitív egész összegének a kétszerese: d1+d2+...+d182(1+2+...+9)=90. Másrészt a11 és a1990, ezért d1+d2+...+d18=a19-a190-1=89.
A talált ellentmondás azt jelenti, hogy már a d1, d2, ..., d18 különbségek között is kell lennie legalább 3 egyforma számnak, a feladat állítása tehát valóban igaz.