Feladat: 2000. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csikvári Péter ,  Kovács Erika Renáta ,  Nagy Zoltán ,  Zábrádi Gergely 
Füzet: 2001/február, 73 - 77. oldal  PDF file
Témakör(ök): Oszthatósági feladatok, Maradékosztályok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 2001/február: 2000. évi Kürschák matematikaverseny 3. feladata

Legyen k nemnegatív egész szám, és tegyük fel, hogy az a1, a2, ..., an egész számok legalább 2k különböző maradékot adnak (n+k)-val osztva. Bizonyítandó, hogy a számok között van néhány, amelyek összege osztható (n+k)-val.

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.

 
I. megoldás. Az általánosság megszorítása nélkül feltehető, hogy az a1, a2, ..., a2k számok páronként különböző maradékot adnak (n+k)-val osztva. Tekintsük a következő n+k különböző számot:
b1=a1,b2=a1,b3=a1+a2b3i+1=a1+a2+...+a2i+a2i+1(0<i<k)b3i+2=a1+a2+...+a2i+a2i+2(0<i<k)b3i+3=a1+a2+...+a2i+a2i+1+a2i+2(0<i<k)bj=a1+a2+...+aj-k(3k<jn+k)
Ha ezek között van olyan, amelyik osztható (n+k)-val, akkor mar készen is vagyunk. Ellenkező esetben pedig van a számok között kettő, mondjuk bs és bt (s<t) amelyik ugyanolyan maradékot ad (n+k)-val osztva. Ekkor bt-bs nyilván osztható (n+k)-val. Azt kell már csak észrevennünk, hogy ez a különbség felírható az a1, a2, ..., an számok közül néhánynak az összegeként. Ha ugyanis ez nem így lenne, akkor valamilyen k-nál kisebb i-re s=3i+1 és t=3i+2, vagyis bt-bs=a2i+2-a2i+1 volna. Ez azonban feltételezésünk értelmében nem osztható (n+k)-val.
 
II. megoldás. Ugyanehhez a végeredményhez egy kissé eltérő kiindulással is eljuthatunk.
Állítás. Tetszőleges b1, b2, ..., bN egész számok esetén léteznek olyan 1ijN indexek, hogy a bi+bi+1+...+bj összeg osztható N-nel.
Ez egyébként éppen a feladat állítása a k=0 esetben. A bizonyításhoz tekintsük t=0, 1, ..., N esetén az st=b1+...+bt összegeket, ahol s0=0 az üres összeg. Az így felírt N+1 egész szám között biztosan van kettő, amelyik ugyanolyan maradékot ad N-nel osztva. Ha sk és s (0k<N) két ilyen összeg, akkor s-sk=bk+1+bk+2+...+b osztható N-nel.
A feladatot ezután a következő módon vezethetjük vissza erre a speciális esetre. Az első megoldáshoz hasonlóan, most is feltehetjük, hogy az a1, a2, ..., a2k számok páronként különböző maradékot adnak (n+k)-val osztva. Tekintsük a
b1=a1,b2=a2-a1,b3=a1,b4=a3,b5=a4-a3,b6=a3,...,b3k=a2k-1,b3k+1=a2k+1,b3k+2=a2k+2,...,bn+k=an
számokat. Így éppen N=n+k egész számot írtunk fel.
A fenti állítás értelmében léteznek olyan 1ijN indexek, hogy S=bi+bi+1+...+bj osztható N-nel. Elegendő azt megmutatni, hogy S felírható az a1, a2, ..., an számok közül néhánynak az összegeként. Ez egészen nyilvánvaló akkor, ha i3k+1, ebben az esetben ugyanis
S=ai-k+ai-k+1+...+aj-k.

Ha i3k<j, akkor legyen i=3s+q, ahol 0s<k és 1q3. Ekkor nyilván
S=A+a2s+3+a2s+4+...+aj-k,
ahol A=a2s+1+a2s+2, a2s+2, vagy a2s+1 annak megfelelően, hogy q értéke 1, 2, vagy pedig 3.
Végül j3k esetén legyen i=3s+q, j=3t+r, ahol 0st<k és 1q,r3. Ekkor könnyen ellenőrizhető, hogy
S=A+a2s+3+a2s+4+...+a2t+B,
ahol A-t ugyanúgy definiáljuk, mint az előző esetben, B értéke pedig a2t+1, a2t+2, vagy pedig e kettő összege aszerint, hogy r=1, 2, vagy 3, feltéve, hogy st. Ha s=t, akkor is könnyen látható, hogy S értéke a2s+1+a2s+2, a2s+2, vagy a2s+1. Kivételt képezne az az egyetlen esetet, amikor s=t és q=r=2. Ez azonban nem fordulhat elő, hiszen ekkor S=a2s+2-a2s+1 lenne, az a1, a2, ..., a2k számok közül viszont semelyik kettő különbsége nem osztható N-nel.
 
III. megoldás. (Kovács Erika Renáta megoldása.) Ismét tegyük fel, hogy az a1, ..., a2k számok páronként különböző maradékot adnak (n+k)-val osztva. Vezessük be az A={a1,a2,...,a2k} jelölést, és legyen b1=a1. Ha valamilyen 1<jk+1 esetén a b1, b2, ..., bj-1 számokat már definiáltuk, akkor legyen bj az A halmaznak egy olyan eleme, amelyik a b1, b2, ..., bj-1, b1+b2, b1+b2+b3, ..., b1+b2+...+bj-1 számok egyikével sem ad azonos maradékot (n+k)-val osztva. Ilyen szám valóban létezik, hiszen ezekkel a feltételekkel az A halmaznak legfeljebb (j-1)+(j-2)<2k elemét zártuk ki.
Jelölje bk+2, bk+3, ..., b2k az A halmaz fennmaradó elemeit valamilyen sorrendben, és tekintsük a következő n+k számot:
si=b1+b2+...+bi(1i2k),sj=a1+a2+...+aj(2k<in),sn+1=b2,sn+2=b3,...,sn+k=bk+1.
Ha ezek közül valamelyik osztható (n+k)-val, akkor készen is vagyunk, ellenkező esetben viszont közülük kettő azonos maradékot ad (n+k)-val osztva, ezek különbsége tehát ismét csak osztható (n+k)-val. Az nyilván nem lehetséges hogy mindkét szám az utolsó k darab közül kerüljön ki, hiszen ezek páronként különböző maradékkal rendelkeznek. Ha mindkét szám az első n szám között van, akkor különbségük éppen az ai számok közül néhánynak az összege, ebben az esetben tehát megint csak célhoz értünk. Végül, ha a két szám közül az egyik si, ahol 1in, a másik pedig sn+j, 1jk, akkor a bi számok megválasztása miatt i>j kell, hogy teljesüljön. Ekkor azonban sn+j=bj+1 éppen az si egyik összeadandója, következésképpen az (n+k)-val osztható si-sn+j szám most is felírható az ai számok közül néhánynak az összegeként.
 
IV. megoldás. (Zábrádi Gergely ötlete.) Most egy indukciós bizonyítást mutatunk. Pontosabban az alábbi erősebb állítást fogjuk teljes indukcióval igazolni.
Állítás. Legyenek m, n pozitív egész számok. Ha az a1, a2, ..., an egész számok legalább 2i különböző maradékot adnak m-mel osztva, akkor vagy van közöttük néhány, amelyek összege osztható m-mel, vagy képezhető belőlük legalább n+i olyan összeg, amelyek páronként különböző maradékot adnak m-mel osztva.
Ebből az állításból m=n+k, i=k választással az eredeti feladat megoldása azonnal leolvasható.
Ha i=0, akkor egyszerűen tekintjük az a1, a1+a2, ..., a1+a2+...+an összegeket; ha ezek között van két olyan, amelyik azonos maradékot ad m-mel osztva, akkor különbségük, ami szintén néhány ai összege, osztható m-mel.
Tegyük fel most egy pillanatra, hogy i=1 esetén is igazoltuk már az állítást. Az indukciós lépéshez legyen j1 és tegyük fel azt is, hogy az állítás igazolást nyert már i=j esetén is. Ebből i=(j+1)-re a következőképpen kaphatjuk meg az állítást. Legyenek a1, a2, ..., an olyan egész számok, amelyek legalább 2j+2 különböző maradékot adnak m-mel osztva. Válasszunk ki közülük két különböző maradékot adót, és tekintsük az összes olyan ai-t, amelyik ezek valamelyikével kongruens modulo m. Az általánosság megszorítása nélkül feltehetjük, hogy ezek éppen az at+1, at+2, ..., an számok. Az a1, a2, ..., at számokról tudjuk azt, hogy legalább 2j különböző maradékot adnak m-mel osztva.
Tegyük fel, hogy az ai számokból nem képezhető m-mel osztható összeg. Ekkor az indukciós feltevés és az i=1 esetre vonatkozó feltevés értelmében az a1, a2, ..., at számokból képezhető t+j különböző maradékot adó összeg, az at+1, at+2, ..., an számokból pedig képezhető n-t+1 különböző maradékot adó összeg. Jelölje ezeket rendre s1, s2, ..., st+j, illetve r1, r2, ..., rn-t+1. Minden további nélkül feltehető az is, hogy s1=a1+a2+...+at. Tekintsük most a következő n+j+1 számot: s1, s2, ..., st+j, s1+r1, s1+r2, ..., s1+rn-t+1, ezek bármelyike felírható az ai számok közül néhánynak az összegeként. Tudjuk, hogy az első t+j szám páronként inkongruens modulo m, és hasonlóképpen az utolsó n-t+1 is az. Az sem lehet, hogy valamelyik sb ugyanolyan maradékot ad m-mel osztva, mint s1+rc, hiszen különbségük, (s1-sb)+rc jól láthatóan néhány ai összege. A felsorolt n+j+1 szám tehát páronként inkongruens modulo m, és éppen ezt akartuk megmutatni.
Annyi van már csak hátra, hogy a fent kimondott állítást i=1 esetén is igazoljuk. Tegyük fel tehát, hogy az a1, a2, ..., an számok közül a1 és a2 különböző maradékot adnak m-mel osztva. Ha az a1,a2,a1+a2,a1+a2+a3,...,a1+a2+...+an számok között van kettő, ami ugyanazt a maradékot adja, akkor különbségük, ami nem más, mint néhány ai összege, osztható lesz m-mel. Ellenkező esetben pedig máris találtunk n+1 olyan összeget, ami mind különböző maradékot ad m-mel osztva.
 
Megjegyzések. 1. Ahogy azt Gyenes Zoltán és Kiss Gergely is megjegyzik, az első megoldásból (és az azzal lényegében megegyező másodikból is) világosan látszik, hogy nem kell megkövetelnünk 2k különböző maradék létezését: elegendő, ha az ai számokból kiválasztható k olyan pár, hogy az azonos párban lévő számok különböző maradékot adnak (n+k)-val osztva.
Ez megtehető már akkor is (hogyan?), ha csak k+1 különböző maradék létezését követeljük meg (feltéve persze, hogy 2kn).
2. A KöMaL 2000. decemberi számának A. 252. feladata szerint a 2kn feltételre valójában nincs is szükség: a feladatban megfogalmazott állítás igazolásához elég annyit feltenni, ahogy az a1, a2, ..., an számok legalább k+1 különböző maradékot adnak (n+k)-val osztva. Az alábbiakban erre mutatunk két különböző bizonyítást.
3. Megjegyezzük még, hogy Szemerédi Endre egy nehéz eredményére támaszkodva ez a feltétel is lényegesen gyengíthető: ha k értéke n-hez képest ,,elég nagy'', akkor elegendő annyit feltenni, hogy az ai számok több, mint ck különböző maradékot adnak (n+k)-val osztva.

 
V. megoldás. (Csikvári Péter megoldásából.) Ha k=0, akkor a feltétel semmitmondó, és a bizonyítandó állítás következik a II. megoldás elején kimondott egyszerű állításból. A továbbiakban legyen tehát k>0.
Tegyük fel, hogy az a1, a2, ..., ak+1 számok különböző maradékot adnak (n+k)-val osztva. Legyen s=a1+a2+...+ak+1, és tekintsük 1ik+1 esetén az ai és bi=s-ai számokat, valamint 1jn-k esetén a cj=a1+a2+...+ak+j számokat, ez összesen n+k+2 egész szám. Vizsgáljuk meg, hogyan adhat ezek közül kettő ugyanolyan maradékot (n+k)-val osztva. Az ai számok páronként különböző maradékot adnak, csakúgy mint a bi számok. Ha a cj számok közül kettő ugyanazt a maradékot adja, akkor már készen is vagyunk. Hasonlóképpen készen vagyunk akkor is, ha valamelyik cj szám ugyanolyan maradékot ad, mint valamelyik ai vagy bi, hiszen mind maga az ai szám, mind pedig a bi minden egyes összeadandója szerepel bármelyik cj összeadandói között. Mivel ai a bj-nek is összeadandója ji esetén, feltehetjük azt is, hogy ilyen esetekben ai és bj különböző maradékot adnak.
Összefoglalva, feltehetjük tehát, hogy ha a fent felsorolt n+k+2 szám között kettő azonos maradékot ad (n+k)-val osztva, akkor ez a két szám ai és bi egy alkalmas 1ik+1 indexre. Minden egyéb esetben ugyanis a bizonyítandó állítás az elmondottak miatt rögtön következik. Vegyük észre azt is, hogy azonnal befejezettnek tekinthetjük a bizonyítást akkor is, ha a felsorolt n+k+2 szám valamelyike osztható (n+k)-val. Egyetlen olyan eset képzelhető már csak el, amelyben még nem végeztük el a bizonyítást, nevezetesen ha 3 különböző i index is létezik úgy, hogy ai és bi ugyanazt a maradékot adják, vagyis különbségük, s-2ai osztható (n+k)-val. Legyenek ezek i1, i2 és i3, ekkor a 2ai1, 2ai2 és 2ai3 számok ugyanolyan maradékot adnak (n+k)-val osztva. Nem nehéz megmutatni, hogy ez csak úgy lehetséges, ha az ai1, ai2, ai3 számok közül kettőnek a maradéka megegyezik, ellentétben a megoldás legelején tett feltevésünkkel. Ez mutatja, hogy a bizonyítást már minden esetben elvégeztük.
 
VI. megoldás. (Nagy Zoltán megoldásából.) Ha a számok közül valamelyik osztható (n+k)-val, akkor már készen is vagyunk, találtunk egy egytagú megfelelő összeget. Tegyük fel tehát, hogy az ai számok p különböző maradékot (pk+1) adnak (n+k)-val osztva, és ezek 0<m1<m2<...<mp<n+k. Ha egy összeg minden egyes tagját egy azzal azonos maradékot adó számmal helyettesítünk, a kapott összeg nyilván pontosan akkor lesz osztható (n+k)-val, ha az eredeti összeg is ilyen volt. Ezért feltehetjük azt is, hogy mindegyik ai valamelyik mj-vel egyenlő.
Állítsuk nagyság szerinti sorrendbe az ai számokat, vagyis legyen a1=a2=...=ak1=m1, ak1+1=ak1+2=...=ak2=m2, ..., akp-1+1=...=an=mp, ahol 1k1<k2<...<kp-1<n. Tekintsük most minden 1in esetén az si=a1+a2+...+ai összeget, és minden 1jp-1 esetén a tj=a1+a2+...+akj-1+akj+1 összeget is. Ez összesen n+p-1n+k szám. Ha ezek között van (n+k)-val osztható, akkor készen vagyunk. Ellenkező esetben kell, hogy legyen kettő, amelyik ugyanolyan maradékot ad (n+k)-val osztva.
Ha az si számok között van két ilyen, akkor a szokásos indoklás működik.
Ha si-tj osztható (n+k)-val valamilyen i, j esetén, akkor ismét csak készen vagyunk. Ha ugyanis i<kj, akkor az si összeg valódi része a tj összegnek, és ezért tj-si néhány ai összege. Ha i>kj, akkor pedig a tj összeg képezi valódi részét az si összegnek. Az pedig nem lehet, hogy i=kj, mert ekkor si-tj=akj-akj+1=mj-mj+1 lenne, ami nem osztható (n+k)-val.
Végül tegyük fel, hogy t-tj osztható (n+k)-val valamilyen 1j<p-1 esetén. Ha még j+1< is teljesül, akkor könnyen látható, hogy t-tj az ai számok közül néhánynak az összege. Ugyanez a helyzet akkor is, ha =j+1 és kj+1kj+2. Az pedig nem lehetséges, hogy =j+1 és kj+1=kj+1, ekkor ugyanis t-tj=akj+1+1+akj-akj+1=mj+2+mj-mj+1. Viszont az mi számokra tett feltevés miatt nyilván 0<mj<mj+2+mj-mj+1<mj+2<n+k, vagyis az egyetlen megmaradt esetben t-tj nem osztható (n+k)-val.