Problem B. 5092. (March 2020)

B. 5092. The sum of the elements is calculated for each subset of the set \(\displaystyle \{0,1,\dots,n-1\}\). What may the value of \(\displaystyle n\) be if exactly one \(\displaystyle n\)th of the resulting \(\displaystyle 2^n\) sums is divisible by \(\displaystyle n\)?

(6 pont)

Deadline expired on April 14, 2020.

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

Megoldás. A feltétel csak akkor teljesülhet, ha \(\displaystyle 2^n\) osztható \(\displaystyle n\)-nel, vagyis \(\displaystyle n\) csak 2-hatvány lehet. Megmutatjuk, hogy az összes 2-hatványra teljesül a feltétel. Valójában erősebb állítást igazolunk: belátjuk, hogy ha \(\displaystyle n\) 2-hatvány, akkor mind az \(\displaystyle n\)-féle maradék ugyanannyiszor fordul elő.

Legyen tehát \(\displaystyle n=2^k\), ahol \(\displaystyle k\) nemnegatív egész szám. Legyen \(\displaystyle K=\{1,2,\dots,2^{k-1}\}\). A \(\displaystyle K\) elemeiből képezhető részhalmazösszegek éppen az egész számok \(\displaystyle 0\) és \(\displaystyle 2^k-1\) között (ez a számok 2-es számrendszerbeli alakja alapján egyből látható), vagyis a \(\displaystyle K\) elemeiből képezhető összegek között mind az \(\displaystyle n\)-féle modulo \(\displaystyle n=2^k\) maradék pontosan egyszer szerepel. Ebből következik, hogy akárhogyan is választunk ki \(\displaystyle \{1,2,\dots,n\}\setminus K\) elemei közül néhányat, ezekhez \(\displaystyle K\) elemei közül pontosan egyféleképpen lehet néhányat hozzávenni, hogy az összeg \(\displaystyle n\)-es maradéka egy kiválasztott érték (például 0) legyen. Azaz mind az \(\displaystyle n\)-féle \(\displaystyle n\)-es maradék ugyanannyiféleképpen áll elő, speciálisan éppen az összegek \(\displaystyle n\)-edrésze lesz osztható \(\displaystyle n\)-nel.

(Megjegyezzük, hogy ez a gondolatmenet már \(\displaystyle k=0\)-ra is működik, ilyenkor \(\displaystyle K=\emptyset\), és egyetlen részhalmazösszeg van, a 0. Ehelyett külön is ellenőrizhető, hogy a \(\displaystyle \{0\}\) halmaz részhalmazösszegei, ami 0 és 0, mind oszthatók 1-gyel, vagyis a 2 darab összegnek pontosan az ,,1-edrésze'' osztható 1-gyel.)

Statistics:

35 students sent a solution.
6 points:	Asztalos Ádám, Baski Bence, Beke Csongor, Bognár 171 András Károly, Csizmadia Miklós, Fekete Richárd, Fleiner Zsigmond, Füredi Erik Benjámin, Geretovszky Anna, Hámori Janka, Jánosik Máté, Kercsó-Molnár Anita, Király Csaba Regő, Kovács 129 Tamás, Lengyel Ádám, Lovas Márton, Mátravölgyi Bence, Móra Márton Barnabás, Nádor Benedek, Nagy 429 Leila, Nagy 551 Levente, Németh Márton, Nguyen Bich Diep, Seres-Szabó Márton, Szabó 991 Kornél, Sztranyák Gabriella, Terjék András József, Wiener Anna.
5 points:	Velich Nóra.
4 points:	1 student.
3 points:	2 students.
2 points:	2 students.
1 point:	1 student.

Problems in Mathematics of KöMaL, March 2020