 |
Az A. 847. feladat (2023. február) |
A. 847. Adott egy véges \(\displaystyle A\) alaphalmaz, melynek néhány részhalmazát szépnek nevezzük. Legyen egy halmaz kicsi, ha részhalmaza egy szép halmaznak. Legyen egy halmaz nagy, ha van szép részhalmaza. (Egy halmaz lehet egyszerre kicsi és nagy is, és az is előfordulhat, hogy egy halmaz se nem kicsi, se nem nagy). Legyen \(\displaystyle |A|=a\), továbbá jelölje a szép, a kicsi és nagy halmazok számát rendre \(\displaystyle s\), \(\displaystyle k\) és \(\displaystyle n\). Igazoljuk, hogy
\(\displaystyle 2^a \cdot s \le k \cdot n. \)
Javasolta: Imolay András (Budapest)
(7 pont)
A beküldési határidő 2023. március 10-én LEJÁRT.
A feladatot \(\displaystyle a\) szerinti teljes indukcióval bizonyítjuk. Ha \(\displaystyle a=1\) akkor az állítás nyilvánvalóan igaz.
Az indukciós lépéshez tegyük fel, hogy az \(\displaystyle a>1\) elemű \(\displaystyle A\) alaphalmaznak adott néhány szép részhalmaza, jelölje ezek családját \(\displaystyle \mathcal{S}\). A feladat szövege szerint legyen \(\displaystyle \mathcal{N}\) a nagy részhalmazok családja, azaz amelyek tartalmaznak \(\displaystyle \mathcal{S}\)-beli elemet, míg \(\displaystyle \mathcal{K}\) legyen a kis részhalmazok családja, azaz melyek részhalmazai valamely \(\displaystyle \mathcal{S}\)-beli halmaznak. Azt szeretnénk bizonyítani, hogy
\(\displaystyle 2^a \cdot |\mathcal{S}| \leq |\mathcal{K}| \cdot |\mathcal{N}|,\)
amennyiben tudjuk, hogy minden \(\displaystyle a\)-nál kisebb elemszámú alaphalmazon tetszőleges szép halmazok esetén igaz az állítás.
Legyen \(\displaystyle x \in A\) tetszőleges elem. Tekintsük a következő partícióit a fent megadott halmazoknak:
\(\displaystyle \mathcal{S}_0=\{S \in \mathcal{S} \ | \ x \notin S\} \quad \text{ és } \quad \mathcal{S}_1=\{S \in \mathcal{S} \ | \ x \in S\},\)
\(\displaystyle \mathcal{K}_0=\{K \in \mathcal{K} \ | \ x \notin K\} \quad \text{ és } \quad \mathcal{K}_1=\{K \in \mathcal{K} \ | \ x \in K\},\)
\(\displaystyle \mathcal{N}_0=\{N \in \mathcal{N} \ | \ x \notin N\} \quad \text{ és } \quad \mathcal{N}_1=\{N \in \mathcal{N} \ | \ x \in N\}.\)
Továbbá vezessük be azt a jelölést, hogy ha egy \(\displaystyle \mathcal{Z}\) halmazcsalád minden eleme tartalmazza \(\displaystyle x\)-t, akkor \(\displaystyle \mathcal{Z}'\)-vel jelöljük a \(\displaystyle \{Z \setminus \{x\} \ | \ Z \in \mathcal{Z}\}\) családot az \(\displaystyle A \setminus \{x\}\) alaphalmazon.
A fő ötlete a megoldásnak az, hogy alkalmazzuk az indukciós feltevést az \(\displaystyle A \setminus \{x\}\) alaphalmazon az \(\displaystyle \mathcal{S}_0\) szép halmazokra is, illevte az \(\displaystyle \mathcal{S}'_1\) szép halmazokra is. Ezekből kapunk néhány egyenlőtlenséget, amikből aztán kikeverjük a bizonyítandót.
A rövidebb jelölések érdekében minden halmaz elemszámát jelölje a megfelelő kisbetű, azaz \(\displaystyle |\mathcal{A}|=a\), \(\displaystyle |\mathcal{S}_0|=s_0\), \(\displaystyle |\mathcal{S}_1|=s_1\), \(\displaystyle |\mathcal{K}_0|=k_0\), \(\displaystyle |\mathcal{K}_1|=k_1\), \(\displaystyle |\mathcal{N}_0|=n_0\), \(\displaystyle |\mathcal{N}_1|=n_1\). Ekkor a bizonyítandó a
\(\displaystyle 2^{a} \cdot (s_0+s_1) \leq (k_0+k_1)(n_0+n_1)\)
egyenlőtlenség.
Először a következő négy egyenlőtlenséget bizonyítjuk:
\(\displaystyle 2^{a-1}s_0 \leq n_0k_0,\)
\(\displaystyle 2^{a-1}s_0 \leq n_1k_0,\)
\(\displaystyle 2^{a-1}s_1 \leq n_1k_0,\)
\(\displaystyle 2^{a-1}s_1 \leq n_1k_1.\)
Valójában mind egyszerű következménye az indukciós feltevésnek:
Tekintsük az \(\displaystyle A \setminus \{x\}\) alaphalmazon az \(\displaystyle \mathcal{S}_0\) szép halmazokat. Ekkor itt a nagy halmazok családja éppen \(\displaystyle \mathcal{N}_0\), míg a kicsi halmazok családja részhalmaza \(\displaystyle \mathcal{K}_0\)-nak. Így az indukciós feltevésből azonnal adódik az első egyenlőtlenség. Továbbá \(\displaystyle \mathcal{N}'_1\) tartalmazza a nagy halmazokat, amiből adódik a második egyenlőtlenség.
Hasonló módon az \(\displaystyle A \setminus \{x\}\) alaphalmazon az \(\displaystyle \mathcal{S}'_1\) szép halmazokat tekintve a kicsi halmazok családja éppen \(\displaystyle \mathcal{K}'_1\), amit tartalmaz \(\displaystyle \mathcal{K}_0\), és \(\displaystyle \mathcal{N}'_1\) tartalmazza a nagy halmazokat, így erre alkalmazva az indukciós feltevést megkapjuk a harmadik és negyedik egyenlőtlenséget is.
Ha \(\displaystyle n_1k_0 \leq n_0k_1\), akkor a négy bizonyított egyenlőtlenséget összeadva, majd ezt alkalmazva éppen a bizonyítandót kapjuk. Emiatt feltehetjük, hogy \(\displaystyle n_1 \neq 0\) és \(\displaystyle k_0 \neq 0\). Így az első és utolsó egyenlőtlenséget használva
\(\displaystyle (k_0+k_1)(n_0+n_1) \geq \left(k_0+\frac{2^{a-1}s_1}{n_1}\right)\left(\frac{2^{a-1}s_0}{k_0}+n_1\right)=2^{a-1}s_0+k_0n_1+\frac{2^{2a-2}s_0s_1}{k_0n_1}+2^{a-1}s_1,\)
így elég azt bizonyítani, hogy
\(\displaystyle k_0n_1+\frac{2^{2a-2}s_0s_1}{k_0n_1} \geq 2^{a-1}(s_0+s_1).\)
Átszorozva, 0-ra rendezve és szorzattá alakítva azt kéne látnunk, hogy
\(\displaystyle (k_0n_1)^2+2^{2a-2}s_0s_1-2^{a-1}(s_0+s_1)k_0n_1=(k_0n_1-2^{a-1}s_0)(k_0n_1-2^{a-1}s_1) \geq 0,\)
ami pedig világos a második és harmadik egyenlőtlenségből. Ezzel beláttuk az állítást.
Statisztika:
4 dolgozat érkezett. 7 pontot kapott: Sida Li. 0 pontot kapott: 3 versenyző.
A KöMaL 2023. februári matematika feladatai