A B. 5314. feladat (2023. április)

B. 5314. Legyen \(\displaystyle S\) egy \(\displaystyle n\)-elemű halmaz, \(\displaystyle 1\le k\le n\) pedig páratlan egész szám. Legfeljebb hány részhalmaza választható ki \(\displaystyle S\)-nek úgy, hogy semelyik kettő szimmetrikus differenciája ne legyen pontosan \(\displaystyle k\)-elemű?

Javasolta: Pach Péter Pál (Budapest)

(5 pont)

A beküldési határidő 2023. május 10-én LEJÁRT.

Megoldás. Azt fogjuk igazolni, hogy a válasz – \(\displaystyle k\) értékétől függetlenül – \(\displaystyle 2^{n-1}\).

Legyen \(\displaystyle H\) az \(\displaystyle S\) halmaz egy rögzített \(\displaystyle k\)-elemű részhalmaza. Állítsuk párba az \(\displaystyle S\) részhalmazait úgy, hogy \(\displaystyle X,Y\subseteq S\) pontosan akkor alkossanak párt, ha \(\displaystyle X\Delta Y=H\), vagyis ha \(\displaystyle X\) és \(\displaystyle Y\) szimmetrikus differenciája éppen \(\displaystyle H\). (Ha \(\displaystyle X\) párja \(\displaystyle Y\), akkor \(\displaystyle Y=X\Delta H\) és \(\displaystyle X=Y\Delta H\).) Világos, hogy ezzel a \(\displaystyle 2^n\) részhalmazt valóban párokba soroltuk, hiszen \(\displaystyle X\Delta X=\emptyset\ne H\). Egy pár két tagja közül legfeljebb az egyik választható ki, így a kiválasztható részhalmazok száma legfeljebb a párok száma, vagyis \(\displaystyle 2^{n-1}\) (az \(\displaystyle S\) halmaz részhalmazai számának fele).

\(\displaystyle 2^{n-1}\) részhalmaz pedig valóban kiválasztható a feltételeknek megfelelően: például, ha a páros elemszámú részhalmazokat választjuk. Ha \(\displaystyle A\) és \(\displaystyle B\) páros elemszámúak, akkor \(\displaystyle |A\Delta B|=|A|+|B|-2|A\cap B|\) is páros, és így \(\displaystyle |A\Delta B|\ne k\), hiszen \(\displaystyle k\) páratlan, tehát ez a kiválasztás valóban megfelelő. A részhalmazoknak pontosan a fele páros, hiszen például a fenti párbaállításnál egy pár két tagja közül mindig az egyik páros, a másik páratlan, ugyanis ha \(\displaystyle X\Delta Y=H\), akkor \(\displaystyle |X|+|Y|-2|X\cap Y|=|H|=k\) páratlan, tehát \(\displaystyle |X|+|Y|\) is páratlan. Vagyis ily módon \(\displaystyle 2^{n-1}\) részhalmazt választottunk ki a feltételeknek megfelelően.

Tehát a válasz \(\displaystyle 2^{n-1}.\)

Statisztika:

37 dolgozat érkezett.
5 pontot kapott:	Ali Richárd, Aravin Peter, Bodor Mátyás, Chrobák Gergő, Czanik Pál, Czirják Márton Pál, Görömbey Tamás, Hodossy Réka, Holló Martin, Horváth 530 Mihály, Juhász-Molnár Erik, Kerekes András, Kocsis 827 Péter, Kovács Benedek Noel, Melján Dávid Gergő, Mizik Lóránt, Nguyen Kim Dorka, Petrányi Lilla, Sági Mihály, Sárdinecz Dóra, Sütő Áron, Szabó 810 Levente, Szakács Ábel, Szakács Domonkos, Szemlér Bálint, Tarján Bernát, Teveli Jakab, Varga Boldizsár, Virág Lénárd Dániel, Zhai Yu Fan.
4 pontot kapott:	Op Den Kelder Ábel, Vigh 279 Zalán.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2023. áprilisi matematika feladatai