Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem A. 524. (January 2011)

A. 524. Is it possible to split the set {1,2,...,2010} into pairwise disjoint, 5-element subsets in such a way that the sum of elements in each subset is divisible by 2011?

(5 pont)

Deadline expired on February 10, 2011.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Mivel \(\displaystyle 2011\) prímszám, létezik modulo \(\displaystyle 2011\) primitív gyök, azaz olyan \(\displaystyle g\) pozitív egész szám, amire az \(\displaystyle 1,g,g^2,\dots,g^{2009}\) számok minden nemnulla maradékot kiadnak \(\displaystyle 2011\)-gyel osztva. (Modulo 2011 primitív gyök például a \(\displaystyle 3\).)

Továbbiakban modulo 2011 maradékosztályokkal dolgozunk, nem teszünk különbséget egy egész szám és a 2011-es maradéka között.

 

Tekintsük a következő számötösöket:

\(\displaystyle \matrix{ ( & 1 & g^{402} & g^{2\cdot402} & g^{3\cdot402} & g^{4\cdot402} & ) \cr ( & g & g^{402+1} & g^{2\cdot402+1} & g^{3\cdot402+1} & g^{4\cdot402+1} & ) \cr ( & g^2 & g^{402+2} & g^{2\cdot402+2} & g^{3\cdot402+2} & g^{4\cdot402+2} & ) \cr & & & \vdots & & \cr ( & g^{401} & g^{402+401} & g^{2\cdot402+401} & g^{3\cdot402+401} & g^{4\cdot402+401} & ) \cr }\)

Azt állítjuk, hogy ezek az 1,2,...,2010 maradékosztályok egy, a feladat feltételeinek megfelelő felbontását adják, azaz az előforduló \(\displaystyle g^k\) maradékosztályok között az 1,2,...,2010 mindegyike pontosan egyszer fordul elő, és mindengyik ötösben az összeg \(\displaystyle 0\).

A fenti ötösök között \(\displaystyle 1,g,g^2,\dots,g^{2009}\) mindegyike pontosan egyszer fordul elő, az első állítás triviális ezért az állítás első fele azzal ekvivalens, hogy \(\displaystyle g\) primitív gyök.

A második rész bizonyítása: Mivel \(\displaystyle g\) primitív gyök, \(\displaystyle g^{402}-1\) nem osztható \(\displaystyle 2011\)-gyel, ugyanakkor

\(\displaystyle (g^{402}-1)(1+g^{402}+g^{2\cdot402}+g^{3\cdot402}+g^{4\cdot402} = g^{5\cdot402}-1 = g^{2010}-1 \)

osztható 2011-gyel. Tehát

\(\displaystyle 1+g^{402}+g^{2\cdot402}+g^{3\cdot402}+g^{4\cdot402} \)

és tetszőleges \(\displaystyle k\) egészre ennek \(\displaystyle g^k\)-szorosa,

\(\displaystyle g^k+g^{402+k}+g^{2\cdot402+k}+g^{3\cdot402+k}+g^{4\cdot402+k} \)

is osztható \(\displaystyle 2011\)-gyel.


Statistics:

12 students sent a solution.
5 points:Ágoston Tamás, Backhausz Tibor, Damásdi Gábor, Frankl Nóra, Gyarmati Máté, Janzer Olivér, Maga Balázs, Mester Márton, Nagy 235 János, Nagy 648 Donát, Strenner Péter, Viharos Andor.

Problems in Mathematics of KöMaL, January 2011