Az A. 811. feladat (2021. november)

A. 811. Adott egy \(\displaystyle n\) elemű \(\displaystyle A\) halmaz és egy \(\displaystyle k<n\) pozitív egész szám. Határozzuk meg \(\displaystyle m\) legnagyobb lehetséges értékét, ha \(\displaystyle i=1,2,\ldots,m\) esetén kiválaszthatók \(\displaystyle B_i\) és \(\displaystyle C_i\) halmazok úgy, hogy a következők teljesüljenek:

\(\displaystyle (i)\) \(\displaystyle B_i \subset A\), \(\displaystyle |B_i|=k\),

\(\displaystyle (ii)\) \(\displaystyle C_i \subset B_i\) (\(\displaystyle C_i\) elemszámára nincs további megkötés),

\(\displaystyle (iii)\) minden \(\displaystyle i \ne j\) esetén \(\displaystyle B_i \cap C_j \ne B_j \cap C_i\).

Javasolta: Imolay András (Budapest)

(7 pont)

A beküldési határidő 2021. december 10-én LEJÁRT.

Megoldás. Az \(\displaystyle m\) értéke legfeljebb \(\displaystyle 2^k\).

Alsó becslés: \(\displaystyle 2^k\) esetén könnyű konstrukciót adni. Legyen \(\displaystyle B \subset A\) egy \(\displaystyle k\) elemű részhalmaz. Minden \(\displaystyle 1 \leq i \leq 2^k\) esetén legyen \(\displaystyle B_i=B\), továbbá \(\displaystyle C_i\) fusson végig \(\displaystyle B\) részhalmazain. Világos, hogy teljesülnek a feladat feltételei.

Felső becslés: Adott a feladat feltételeit kielégítő halmazrendszer, igazoljuk, hogy \(\displaystyle m \leq 2^k\). Feleltessük meg az \(\displaystyle A\) halmaz elemeit \(\displaystyle 1\)-től \(\displaystyle n\)-ig az egész számoknak. Minden \(\displaystyle 1 \leq i \leq m\) esetén legyen \(\displaystyle S_i\) azon \(\displaystyle n\) hosszú \(\displaystyle 0-1\) sorozatok halmaza, melyre az \(\displaystyle l.\) jegy \(\displaystyle 1\), ha \(\displaystyle l \in C_i\), és \(\displaystyle 0\), ha \(\displaystyle l \in B_i \setminus C_i\). Végül ha \(\displaystyle l \notin B_i\) akkor nincs megkötés, ott bármit felvehet a \(\displaystyle 0-1\) sorozat. Tehát \(\displaystyle |S_i|=2^{n-k}\), mivel \(\displaystyle k\) helyen megmondtuk az értékét, míg \(\displaystyle n-k\) helyen tetszőlegesen választhatunk.

Vegyük észre, hogy a \(\displaystyle B_i \cap C_j \neq B_j \cap C_i\) feltétel azt jelenti, hogy \(\displaystyle a \in S_i\) és \(\displaystyle b \in S_j\) esetén \(\displaystyle a \neq b\). Ugyanis kell lennie egy olyan \(\displaystyle l\) számnak, melyre \(\displaystyle l \in B_i \cap B_j\), és a \(\displaystyle C_i\) és \(\displaystyle C_j\) közül pontosan az egyikben van benne, így az \(\displaystyle l.\) helyen \(\displaystyle a\) és \(\displaystyle b\) különböző értéket fog felvenni.

Összesen \(\displaystyle 2^n\) darab \(\displaystyle n\) hosszú \(\displaystyle 0-1\) sorozat van, az \(\displaystyle S_i\) halmazok páronként diszjunktak, az elemszámuk pedig \(\displaystyle 2^{n-k}\), így

\(\displaystyle m \leq \frac{2^n}{2^{n-k}}=2^k.\)

Statisztika:

4 dolgozat érkezett.
7 pontot kapott:	Móra Márton Barnabás.
6 pontot kapott:	Kovács 129 Tamás.
1 pontot kapott:	2 versenyző.

A KöMaL 2021. novemberi matematika feladatai