Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 524. feladat (2011. január)

A. 524. Felbontható-e az {1,2,...,2010} halmaz páronként diszjunkt, ötelemű halmazokra úgy, hogy az elemek összege mindegyik ötelemű halmazban osztható legyen 2011-gyel?

(5 pont)

A beküldési határidő 2011. február 10-én LEJÁRT.


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.


Statisztika:

12 dolgozat érkezett.
5 pontot kapott:Á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.

A KöMaL 2011. januári matematika feladatai