Feladat: F.2939 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Cs. Kovács Ferenc ,  Csergőffy Tibor ,  Csorba Péter ,  Csörnyei Marianna ,  Dienes Péter ,  Dőtsch András ,  Futó Gábor ,  Horváth Gábor ,  Imreh Csanád ,  K. L. ,  Kóczy László ,  Kovács Gergely ,  Kucsera Henrik ,  Maróti Attila ,  Marx Gábor ,  Megyesi Zoltán ,  Pete Gábor ,  Rákóczi Bálint ,  Róka Dániel ,  Szabó László ,  Szeredi Tibor ,  Waldhauser Tamás 
Füzet: 1994/január, 16 - 17. oldal  PDF file
Témakör(ök): Maradékos osztás, Teljes indukció módszere, Maradékosztályok, Feladat
Hivatkozás(ok):Feladatok: 1993/január: F.2939

Legyen p prímszám, 1kp és a1,a2,...ak p-vel nem osztható egész számok. Képezzük az összes e1a1+e2a2+...+ekak összeget, ahol e1,e2,...ek egymástól függetlenül a 0 vagy +1 értéket veszik fel. Bizonyítsuk be, hogy ezek az összegek legalább k féle maradékot adnak p-vel osztva.

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 állítást k szerinti teljes indukcióval bizonyítjuk.
Ha k=1, akkor kétféle összeg van: 0 és a1, ezért az állítás igaz, sőt a kívánt 1 helyett kétféle maradékot adtunk p-vel osztva.
Tegyük fel, hogy at állítás igaz k=k0-ra, ahol 2k0<p. Jelölje az e1a1+...+ek0ak0-tagú összegeket s1,s2,...,sn. Az indukciós feltevés szerint ezek legalább k0-féle maradékot adnak p-vel osztva. Tekintsük most a (k0+1) tagú összegeket, és csoportosítsuk őket ek0+1 értéke szerint. Ha ek0=0, akkor éppen az s1,s2,...,sn összegeket kapjuk; amikor ek0+1=1, akkor pedig az s1+ak0+1,s2+ak0+1,...,sn+ak0+1 számokat.
Ha s1,s2,...,sn teljes maradékrendszer modulo p (azaz p-vel osztva minden maradékot kiadnak), akkor készen vagyunk, hiszen a különböző maradékok száma pk.
Feltehetjük tehát, hogy s1,s2,...,sn nem adnak ki minden maradékot p-vel osztva.
Azt állítjuk, hogy ekkor s1+ak0+1,s2+ak0+1,...,sn+ak0+1 valamelyike olyan maradékot ad p-vel osztva, amely s1,...,sn maradékai között nem szerepel. Ebből az állítás már következik, mivel így a (k0+1)-tagú összegek legalább 1-gyel több féle maradékot adnak p-vel osztva, mint a k0-tagúak.
Tekintsük a 0,ak0+1,2ak0+1,...,(p-1)ak0+1 számokat. Mivel ak0+1 nem osztható p-vel, azért ezek p-vel osztva mind különböző maradékot adnak (ha iak0+1 és jak0+1 ugyanazt a maradékot adja, akkor különbségük, (i-j)ak0+1 osztható p-vel, ami csak i=j esetén lehetséges); így ez egy teljes maradékrendszer modulo p.
Ezen számok között biztosan szerepel olyan, amelynek p-vel való osztási maradéka az si-k maradékai között nem szerepel, hiszen feltételezésünk szerint az si-k nem adnak ki minden lehetséges maradékot. Legyen az első ilyen szám az lak0+1. Mivel a 0 szerepel az si-k között, l nem lehet 0, azaz l1.
A feltevés szerint (l-1)ak0+1 maradéka előfordul az si-k maradékai között, mondjuk

sm(l-1)ak0+1(modp),
ahol 1mn. Ekkor viszont sm+ak0+1lak0+1(modp), tehát sm+ak0+1 maradéka nem szerepel az si-k maradékai között.
Ezzel az állítást igazoltuk.
 
Megjegyzések. 1. Ezzel a módszerrel valójában azt bizonyítottuk be, hogy kp-1 esetén a maradékok száma legalább k+1.
2. Ha a1=a2=...=ak és kp-1, akkor a különböző maradékok száma k+1.