Problem B. 5043. (September 2019)

B. 5043. Prove that the set \(\displaystyle \{1,2,3,4,5,6,7,8,9,10,11,12,13\}\) has an odd number of nonempty subsets in which the arithmetic mean of the elements is an integer.

Proposed by S. Róka, Nyíregyháza

(5 pont)

Deadline expired on October 10, 2019.

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

Megoldás. Tegyük fel, hogy \(\displaystyle A\) az \(\displaystyle S:=\{1,2,\dots,13\}\) halmaz egy részhalmaza. Legyen \(\displaystyle A'\) az a halmaz, melyet úgy kapunk, hogy \(\displaystyle A\)-t tükrözzük a 7-re, vagyis:

\(\displaystyle A'=\{14-a:a\in A\}.\)

Világos, hogy ekkor \(\displaystyle A'\) is \(\displaystyle S\) egy részhalmaza, továbbá, ha \(\displaystyle A\)-ban az elemek átlaga \(\displaystyle s\), akkor \(\displaystyle A'\)-ben az elemek átlaga \(\displaystyle 14-s\) lesz. (Ugyanis, ha \(\displaystyle A=\{a_1,a_2,\dots,a_k\}\), akkor \(\displaystyle A'\)-ben az elemek összege \(\displaystyle (14-a_1)+(14-a_2)+\dots+(14-a_k)=14|A'|-(a_1+a_2+\dots+a_k)=14|A'|-s|A'|\).)

Tehát \(\displaystyle A\)-ban pontosan akkor egész az elemek átlaga, ha \(\displaystyle A'\)-ben is az. Ezen kívül megjegyezzük, hogy \(\displaystyle A''=(A')'=A\), vagyis a részhalmazok \(\displaystyle \{A,A'\}\) alakú párokba rendezhetők. Előfordulhat viszont, hogy bizonyos részhalmazokra \(\displaystyle A'=A\), vagyis őket saját magukkal állítjuk párba. Ha megmutatjuk, hogy ilyen nemüres részhalmazból páratlan sok van, akkor készen vagyunk, hiszen a többi megfelelő részhalmaz (valódi) párokba rendezhető, így számuk páros. Pontosan azokra a részhalmazokra lesz \(\displaystyle A'=A\), amelyek a 7-re tükrösek, vagyis minden \(\displaystyle a\in \{1,2,3,4,5,6\}\) esetén \(\displaystyle a\in A\) pontosan akkor teljesül, ha \(\displaystyle 14-a\in A\). (\(\displaystyle 7\in A\) és \(\displaystyle 7\notin A\) bármelyike fennálhat.) Az összes ilyen részhalmazban 7 (vagyis egész) az elemek átlaga, vagyis mind megfelelők, számuk pedig \(\displaystyle 2^7-1\), hiszen \(\displaystyle A\cap \{1,2,3,4,5,6,7\}\) bármi lehet, kivéve az üres halmazt, és ez már egyértelműen meghatározza \(\displaystyle A\)-t.

Ezzel igazoltuk a feladat állítását.

Statistics:

73 students sent a solution.
5 points:	Andó Viola, Argay Zsolt, Baski Bence, Beke Csongor, Bursics András, Fekete Richárd, Füredi Erik Benjámin, Hegedűs Dániel, Jánosik Áron, Jánosik Máté, Kovács 129 Tamás, Kökényesi Márk Péter, Lengyel Ádám, Lovas Márton, Mátravölgyi Bence, Mezey Dorottya, Móra Márton Barnabás, Nádor Benedek, Nagy Eszter Zsófia, Nagy Nándor, Németh Márton, Noszály Áron, Sebestyén Pál Botond, Seres-Szabó Márton, Szabó 248 Eszter, Szabó 991 Kornél, Szanyi Attila, Szűcs 064 Tamás, Terjék András József, Tiderenczl Dániel, Török Mátyás, Világi Áron, Wiener Anna.
4 points:	Bán-Szabó Áron, Bukva Dávid, Csizmadia Miklós, Dezső Kende Barnabás, Fleiner Zsigmond, Geretovszky Anna, Kerekes Boldizsár, Laki Anna, Lenkey Gyöngyvér, Molnár Lehel, Molnár-Szabó Vilmos, Móricz Benjámin, Reimann Kristóf, Stomfai Gergely.
3 points:	5 students.
2 points:	5 students.
1 point:	6 students.
0 point:	10 students.

Problems in Mathematics of KöMaL, September 2019