A B. 4575. feladat (2013. november)

B. 4575. Ősi hagyományai szerint a Fejszámolók törzse az éveknek a szerencsés, illetve a baljós besorolást adja. Például 2013 szerencsés év, mert az első 2013 pozitív egészet be lehet sorolni legalább két csoportba úgy, hogy bármely két csoportban lévő számok összege és darabszáma is egyenlő. Ha ez nem lehetséges, akkor az év a baljós jelzőt kapja. Melyek a baljós évek?

Javasolta: Káspári Tamás (Paks)

(6 pont)

A beküldési határidő 2013. december 10-én LEJÁRT.

Megoldás. Azt fogjuk belátni, hogy pontosan az 1 és a prímszámok a baljósak, az összetett számok pedig a szerencsések. Az 1 nyilvánvalóan baljós. Ha pedig \(\displaystyle n\) prímszám, és az első \(\displaystyle n\) számot \(\displaystyle d\geq 2\) egyenlő elemszámú részre osztjuk, akkor \(\displaystyle d|n\) miatt csak \(\displaystyle d=n\) lehetséges, vagyis minden szám egy külön csoportba kerül, ekkor viszont a csoportokon belüli összegek nem egyeznek.

Most tegyük fel, hogy \(\displaystyle n\) összetett szám. Ha \(\displaystyle 2<n\) páros, akkor \(\displaystyle n\) darab kételemű csoportot hozhatunk létre, amelyek mindegyikében \(\displaystyle n+1\) az összeg: \(\displaystyle (1,n);(2,n-1);\dots;(\frac{n}{2},\frac{n}{2}+1)\). Tehát a 2-nél nagyobb páros számok szerencsések.

Végül, tegyük fel, hogy az \(\displaystyle n\) összetett szám páratlan. Legyen a legkisebb prímosztója \(\displaystyle p\). Mivel \(\displaystyle n\) összetett, ezért \(\displaystyle n/p\) egy 1-nél nagyobb egész szám, így \(\displaystyle p\) definíciója miatt \(\displaystyle p\leq n/p\). Mivel \(\displaystyle n\) páratlan, ezért \(\displaystyle n/p\) is az, vagyis \(\displaystyle n=p(p+2k)\), ahol \(\displaystyle k\) nemnegatív egész szám. Megmutatjuk, hogy az első \(\displaystyle n\) pozitív egész számot szét lehet osztani \(\displaystyle p\) egyforma méretű csoportba úgy, hogy mindegyik csoporton belül ugyanannyi az elemek összege. Először osszuk be az \(\displaystyle 1,2,\dots,p^2\) számokat. Ehhez írjuk őket egy \(\displaystyle p\times p\)-es táblázat mezőibe úgy, hogy az \(\displaystyle i.\) sor \(\displaystyle j.\) eleme \(\displaystyle (i-1)p+j\) legyen. Azt állítjuk, hogy ha a beosztásnál minden csoportba minden sorból és minden oszlopból pontosan egy elem kerül, akkor olyan \(\displaystyle p\) elemű csoportokat hozunk létre, amelyekben az elemek összege \(\displaystyle (0+1+\dots+(p-1))p+(1+2+\dots+p)\). Legyen ugyanis \(\displaystyle S\) egy tetszőlegesen kiválaszott csoport. Ekkor

\(\displaystyle \sum\limits_{(i-1)p+j\in S} (i-1)p+j=\sum\limits_{(i-1)p+j\in S} (i-1)p+\sum\limits_{(i-1)p+j\in S} j=(0+1+\dots+(p-1))p+(1+2+\dots+p),\)

ahol az első összeg kiszámításánál azt használtuk, hogy \(\displaystyle S\) minden sorból, a másodiknál pedig azt, hogy \(\displaystyle S\) minden oszlopból pontosan egy elemet tartalmaz. Továbbá a kívánt beosztás megvalósítható, például úgy, ha az egyik csoportot a főátlón lévő számok (\(\displaystyle 1,p+2,2p+3,\dots,(p-1)p+p\)) alkotják, a többit pedig ennek ,,eltoltjai''. Be kell még osztanunk a \(\displaystyle p^2+1,p^2+2,\dots,p^2+2kp\) számokat. Ehhez először képezzünk belőlük \(\displaystyle kp\) darab párt: \(\displaystyle x\) párja legyen \(\displaystyle 2p^2+2kp+1-x\), vagyis a párok: \(\displaystyle (p^2+1,p^2+2kp);(p^2+2,p^2+2kp-1);\dots;(p^2+kp,p^2+kp+1)\). Az első \(\displaystyle p^2\) pozitív egész előbbi csoportokba osztását egészítsük ki úgy, hogy mindegyikhez hozzáveszünk \(\displaystyle k\) darab párt. Így egyrészt minden csoportban ugyanannyi lesz az elemek összege, másrészt a csoportok elemszáma is egyezni fog: \(\displaystyle p+2k\) lesz. Ezzel beláttuk, hogy a páratlan összetett számok is szerencsések.

A baljós évek tehát az első és a prímszám sorszámú évek.

Molnár-Sáska Zoltán (Budapesti Fazekas M. Főv. Gyak. Gimn.), 8. évf.

Statisztika:

103 dolgozat érkezett.
6 pontot kapott:	53 versenyző.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	5 versenyző.
3 pontot kapott:	8 versenyző.
2 pontot kapott:	17 versenyző.
1 pontot kapott:	11 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2013. novemberi matematika feladatai