Az A. 830. feladat (2022. szeptember)

A. 830. Ha \(\displaystyle H\subset \mathbb{Z}\) és \(\displaystyle n\in \mathbb{Z}\), legyen \(\displaystyle h_n\) a \(\displaystyle H\) azon véges részhalmazainak a száma, melyekben a számok összege \(\displaystyle n\). Van-e olyan \(\displaystyle H\subset \mathbb{Z}\), melyre \(\displaystyle 0\notin H\), és minden \(\displaystyle n\in \mathbb{Z}\)-re \(\displaystyle h_n\) egy (véges) páros szám? (Az üres halmaz elemeinek összege 0.)

Javasolta: Beke Csongor (Cambridge)

(7 pont)

A beküldési határidő 2022. október 10-én LEJÁRT.

1. megoldás: Legyen \(\displaystyle A_0=\{-1,1\}\), figyeljük meg, hogy ekkor a \(\displaystyle 0\) kétféleképpen áll elő. Definiáljuk rekurzívan az \(\displaystyle A_0\subset A_1 \subset \dots \subset A_n\subset \dots\) véges halmazokat úgy, hogy közben a következőkre figyelünk:

• Minden \(\displaystyle k \geq 1\) esetén az \(\displaystyle A_{2k-1}\) halmaznak páros darab olyan részhalmaza legyen, amiben az összeg \(\displaystyle k\), továbbá ne keletkezzen olyan \(\displaystyle H \subset A_{2k-1}\) részhalmaz, melyre \(\displaystyle H \not\subset A_{2k-2}\) és \(\displaystyle -k+1 \leq \sum_{x \in H} x \leq k-1\).
• Minden \(\displaystyle k \geq 1\) esetén az \(\displaystyle A_{2k}\) halmaznak páros darab olyan részhalmaza legyen, amiben az összeg \(\displaystyle -k\), továbbá ne keletkezzen olyan \(\displaystyle H \subset A_{2k}\) részhalmaz, melyre \(\displaystyle H \not\subset A_{2k-1}\) és \(\displaystyle -k+1 \leq \sum_{x \in H} x \leq k\).
• \(\displaystyle |\min\{x \in A_n\}|<\max\{x \in A_n\}\) pontosan akkor teljesüljön, ha \(\displaystyle n\) páratlan.

Vegyük észre, hogy a fenti feltételek éppen azt garantálják, hogy \(\displaystyle A_{2k-1}\)-ben minden \(\displaystyle -k+1 \leq j \leq k\) számra páros sok olyan részhalmaz legyen, amelyben \(\displaystyle j\) az összeg, mivel minden lépésben beállítjuk egy számra, hogy páros sok részhalmazban legyen éppen annyi az összeg, és utána a többi lépésben ezt már nem változtatjuk meg.

Indukcióval gyártjuk le az \(\displaystyle A_n\) halmazokat, a kezdőlépést megtettük \(\displaystyle A_0\) definiálásával.

Tegyük fel, hogy az \(\displaystyle A_{2k-2}\) már megvan. Jelölje \(\displaystyle -m\) az \(\displaystyle A_{2k-2}\) negatív elemeinek az összegét. Ha \(\displaystyle A_{2k-2}\)-nek páratlan sok olyan részhalmaza van, melyben az elemek összege \(\displaystyle k\), akkor legyen \(\displaystyle A_{2k-1}=A_{2k-2}\cup \{m+k\}\), különben legyen \(\displaystyle A_{2k-1}=A_{2k-2}\cup \{m+k+1\}\). Az indukció miatt \(\displaystyle A_{2k-2}\)-ben negatív volt az (egyik) legnagyobb abszolútértékű tag, így \(\displaystyle A_{2k-1}\)-ben az újonnan bevett tag abszolútértéke lesz a legnagyobb, tehát a harmadik feltétel teljesül, amiből az is látszik, hogy \(\displaystyle m+k, m+k+1 \notin A_{2k-2}\), tehát tényleg bővítettük egy elemmel a halmazt. Az \(\displaystyle A_{2k-1}\) új részhalmazai, amik \(\displaystyle A_{2k-2}\)-nek nem részhalmazai pontosan azok, amik tartalmazzák az újonnan bevett (\(\displaystyle m+k\) vagy \(\displaystyle m+k+1\)) elemet. Így az \(\displaystyle m\) definíciója szerint az összes új összeg legalább \(\displaystyle k\), és ha az \(\displaystyle m+k+1\)-t vettük be, akkor a \(\displaystyle k\) összeg nem is szerepel, ha pedig az \(\displaystyle m+k\)-t akkor pontosan egyszer szerepel, amikor \(\displaystyle m+k\) mellé az összes negatív elemet választjuk. Tehát tényleg mindig páros sok részhalmaz lesz, amiben az összeg \(\displaystyle k\). Ezzel tehát elértük, hogy teljesüljenek a feltételek.

Járjunk el hasonlóan abban az esetben, ha \(\displaystyle A_{2k-1}\) már megvan, és \(\displaystyle A_{2k}\)-t gyártjuk le. Ekkor az \(\displaystyle A_{2k-1}\)-beli pozitív elemek összegét jelölje \(\displaystyle m\), és \(\displaystyle A_{2k}\) legyen \(\displaystyle A_{2k-1} \cup \{-m-k\}\), amennyiben \(\displaystyle A_{2k-1}\) páratlan sok részhalmazában volt az összeg \(\displaystyle -k\), különben legyen \(\displaystyle A_{2k}=A_{2k-1} \cup \{-m-k-1\}\). Az előző indokláshoz hasonlóan, ekkor az újonnan bevett tag lesz a legnagyobb abszolút értékű, az összes új összeg legfeljebb \(\displaystyle -k\), és pontosan akkor keletkezik új részhalmaz \(\displaystyle -k\) összeggel, ha \(\displaystyle -m-k\)-t vettük hozzá, ekkor is pontosan egy, így páros lesz a \(\displaystyle -k\) összegű részhalmazok száma.

Végül legyen \(\displaystyle H=\cup_{n=0}^{\infty} A_n\). A definícióból \(\displaystyle 0 \notin H\), és tetszőleges véges \(\displaystyle G \subset H\) esetén \(\displaystyle G \subset A_{n}\) is teljesül valamilyen \(\displaystyle n\)-re. Tehát tetszőleges \(\displaystyle k\) szám esetén \(\displaystyle H\) véges részhalmazai közül csak olyanoknak lehet \(\displaystyle k\) az összege, amik már \(\displaystyle A_{2k}\)-ban is előfordultak, és tudjuk, hogy ilyenből páros sok van. Így ez tényleg egy megfelelő konstrukció.

2. megoldás: Legyen \(\displaystyle H_1 = \{1, -2, 4, -8, \ldots, (-2)^k, \ldots \}\). Ismert, hogy ez minden egész számot pontosan egyszer állít elő (ez lényegében a \(\displaystyle (-2)\)-es számrendszer). Írunk erre két vázlatos indoklást:

1. indoklás: Vágjuk le a halmazt az első valahány eleme után. Belátjuk, hogy az \(\displaystyle \{1, -2, 4, -8, \ldots, 2^{2k}\}\) halmazból előálló összegek éppen a \(\displaystyle -\sum_{i=1}^k 2^{2i-1} \leq j \leq \sum_{i=0}^k 2^{2i}\) számok, mindegyik pontosan egyszer, míg a \(\displaystyle \{1, -2, 4, -8, \ldots, 2^{2k+1}\}\) halmazból előálló összegek pedig éppen a \(\displaystyle -\sum_{i=1}^{k+1} 2^{2i-1} \leq j \leq \sum_{i=0}^k 2^{2i}\) számok, itt is mindegyik pontosan egyszer. Ez indukcióból nagyon egyszerű. A kezdőlépés igaz, és mindig amikor hozzávesszük a következő \(\displaystyle (-2)^n\) alakú tagot, akkor az újonnan keletkező összegek halmazát úgy kajuk meg, hogy \(\displaystyle (-2)^n\)-t hozzáadjuk az eddigi lehetséges összegekhez, és látható, hogy ez éppen a fenti állítást adja.

2. indoklás: Tekintsünk egy tetszőleges \(\displaystyle n\) számot, és írjuk fel kettes számrendszerben. Az, hogy ezt \(\displaystyle H_1\) egy részhalmazában lévő elemek összegeként felírjuk éppen azt jelenti, hogy \(\displaystyle a-b\) alakban írjuk fel, ahol \(\displaystyle a\) kettes számrendszerbeli alakjában csak a \(\displaystyle 2^{2k}\) alakú helyiértékekeken állhat nem \(\displaystyle 0\), míg \(\displaystyle b\)-ben csak a \(\displaystyle 2^{2k+1}\) helyiértékeken lehet nem 0. Ez egy írásbeli kivonás, visszafelel haladva (az egyes helyiértékről indulva) minden helyértéken egy döntésünk van, vagy az \(\displaystyle a\) megfelelő számjegyéről dönthetünk, hogy 0 vagy 1 (ha \(\displaystyle 2^{2k}\) alakú a helyiérték), vagy a \(\displaystyle b\) megfelelő jegyéről. Akármi is legyen az \(\displaystyle n\) megfelelő jegye, mindig van pontosan egy lehetőségünk hogy úgy állítsuk be, hogy tényleg azt kapjuk, tehát pontosan egyféleképpen tudjuk \(\displaystyle n\)-t előállítani.

Legyen \(\displaystyle H = H_1 \cup \{-1\}\). Világos, hogy ekkor minden egész szám pontosan kétféleképpen áll elő, így ez egy megfelelő konstrukció.

Statisztika:

23 dolgozat érkezett.
7 pontot kapott:	Czanik Pál, Duchon Márton, Lovas Márton, Mckinley D. Xie, Móra Márton Barnabás, Németh Márton, Nguyen Kim Dorka, Seres-Szabó Márton, Szakács Ábel, Sztranyák Gabriella, Varga Boldizsár, Wiener Anna.
6 pontot kapott:	Chrobák Gergő, Farkas 005 Bendegúz.
5 pontot kapott:	3 versenyző.
0 pontot kapott:	6 versenyző.

A KöMaL 2022. szeptemberi matematika feladatai