Feladat: B.3888 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Balambér Dávid ,  Blázsik Zoltán ,  Csaba Ákos ,  Csató László ,  Cseh Ágnes ,  Cserép Máté ,  Dányi Zsolt ,  Dombi Soma ,  Farkas Ádám László ,  Grósz Dániel ,  Honner Balázs ,  Károlyi Gergely ,  Károlyi Márton ,  Kornis Kristóf ,  Kovács 129 Péter ,  Kunovszki Péter ,  Kurgyis Eszter ,  Kutas Péter ,  Lovász László Miklós ,  Mészáros Gábor ,  Milotai Zoltán ,  Peregi Tamás ,  Prőhle Zsófia ,  Sárkány Lőrinc ,  Sümegi Károly ,  Szabó Tamás ,  Szalkai Balázs ,  Szaller Dávid ,  Szalóki Dávid ,  Szilágyi Csaba ,  Szirmai Péter ,  Szőke Nóra ,  Szűcs Gergely ,  Tomon István ,  Tóthmérész Lilla ,  Udvari Balázs ,  Varga László ,  Véges Márton 
Füzet: 2006/november, 483. oldal  PDF file
Témakör(ök): Maradékos osztás, Számsorozatok, Feladat
Hivatkozás(ok):Feladatok: 2006/február: B.3888

Mely m>1 egészekre létezik az 1,2,...,m számoknak olyan a1,a2,...,am sorrendje, hogy az a1,a1+a2,...,a1+a2+...+am összegek mind különböző maradékot adnak m-mel 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.

Megoldás. Tegyük föl, hogy létezik a megfelelő a1,a2,...,am sorrend. Ha ak=m valamilyen k>1-re, akkor a1+...+ak-1 és a1+...+ak-1+ak különbsége osztható m-mel, ezért ugyanazt a maradékot adnák m-mel osztva. Így szükségképpen a1=m. Ezért a1+...+am-1+am=1+2+...+m=m+12m biztosan nemnulla maradékot ad (m>1 miatt), vagyis nem lehet m-mel osztható, azaz m páros.
Megmutatjuk, hogy a kapott szükséges feltétel, m párossága elégséges is: minden páros m-re megadható egy kívánt sorrend. Ilyen például a következő:

m,1,m-2,3,m-4,5,...,4,m-3,2,1,
azaz a páros maradékok csökkenő sorrendben az első, harmadik, ötödik helyen stb., a páratlanok pedig növekvő sorrendben a második, negyedik, hatodik helyen stb. Kiszámítjuk a1+...+ak-1+ak maradékát. Ha k=2t páros, akkor az összeg
m+1+(m-2)+3+...+(m-2t+2)+(2t-1)==(m+(m-2)+...+(m-2t+2))+(1+3+...+(2t-1))==t2((2m-2t+2)+2t)=(m+1)tt(modm),
míg páratlan k=2t+1 esetén az összeg maradéka
t+(m-2t)=m-t-t(modm).
Tehát a részletösszegek sorozatának m-mel való osztási maradékai rendre:
0,1,-1,2,-2,...,m-22,-m-22,m2;
az összes maradék, mindegyik pontosan egyszer.