Problem B. 4575. (November 2013)

B. 4575. According to the tradition of the ancient tribe of Head Counters, every year is designated either as lucky or as sinister. For example, 2013 is a lucky year since the first 2013 positive integers can be partitioned into at least two classes such that each class contains the same number of elements and the sum of the elements is also equal in each class. If such a partition does not exist, the year is said to be sinister. Which years are sinister?

Suggested by T. Káspári, Paks

(6 pont)

Deadline expired on December 10, 2013.

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

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.

Statistics:

103 students sent a solution.
6 points:	53 students.
5 points:	2 students.
4 points:	5 students.
3 points:	8 students.
2 points:	17 students.
1 point:	11 students.
0 point:	7 students.

Problems in Mathematics of KöMaL, November 2013