Problem B. 5314. (April 2023)
B. 5314. Let \(\displaystyle S\) be an \(\displaystyle n\)-element set, and let \(\displaystyle 1\le k\le n\) be an odd integer. What is the largest number of subsets of \(\displaystyle S\) that can be selected so that the symmetric difference of no pair of subsets should have exactly \(\displaystyle k\) elements?
Proposed by P.\(\displaystyle \,\)P. Pach, Budapest
(5 pont)
Deadline expired on May 10, 2023.
Sorry, the solution is available only in Hungarian. Google translation
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}.\)
Statistics:
37 students sent a solution. 5 points: 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 points: Op Den Kelder Ábel, Vigh 279 Zalán. 3 points: 2 students. 2 points: 2 students. 1 point: 1 student.
Problems in Mathematics of KöMaL, April 2023