Feladat:	B.3301	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Breuer János ,  Gyürki István ,  Kiss Gergely
Füzet:	2000/március, 162 - 163. oldal		PDF  |  MathML
Témakör(ök):	Részhalmazok, Halmazok számossága, Feladat
Hivatkozás(ok):	Feladatok: 1999/szeptember: B.3301

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. A $H$ halmaz tetszőleges $R$ részhalmazára jelölje $\overline{R}$ az $R$ komplementerét, azaz $H$ azon elemeinek a halmazát, amelyek nem elemei $R$-nek. Képezzünk $H$ részhalmazaiból $\left(A\mathrm{,}B\right)$ rendezett párokat; $H$-nak $2^n$ darab részhalmaza lévén e rendezett párok száma $2^n\cdot 2^n=4^n$. A rendezett párokat négyes csoportokra osztjuk; minden ilyen csoport álljon az $\left(A\mathrm{,}B\right)$, $\left(\overline{A}\mathrm{,}B\right)$, $\left(A\mathrm{,}\overline{B}\right)$, $\left(\overline{A}\mathrm{,}\overline{B}\right)$ párokból, ahol $A$, $B\subseteq H$. Könnyen látható, hogy minden rendezett pár pontosan egy ilyen csoporthoz tartozik, így e csoportok száma $\frac{1}{4}\cdot 4^n=4^{n-1}$. Tekintsük $H$-nak egy $h$ elemét, és az $A$, $B\subseteq H$ halmazokat; mivel $h$ az $A$ és $\overline{A}$ közül pontosan az egyiknek eleme (hasonlóan $B$ és $\overline{B}$ közül is), azért $h$ az $A\cap B$, $\overline{A}\cap B$, $A\cap \overline{B}$, $\overline{A}\cap \overline{B}$ halmazoknak is pontosan az egyikében van benne. Tehát az $A\cap B$, $\overline{A}\cap B$, $A\cap \overline{B}$, $\overline{A}\cap \overline{B}$ halmazok elemszámának összege $|H|=n$. A számlálást a $4^{n-1}$ csoport mindegyikére elvégezve az elemszámok összegének összegére $n\cdot 4^{n-1}$ adódik, és ez éppen a feladat állítása.  Gyürki István (Zseliz, Magyar Tannyelvű Gimn., 12. o.t.)   II. megoldás. Használjuk az I. megoldás jelöléseit. A $H$ elemeit sorbarendezzük, és minden $A$, $B\subseteq H$ halmazpárhoz hozzárendeljük azt a 4-es számrendszerbeli $n$-jegyű számot, amelynek $i$-edik jegye 0, 1, 2 vagy 3 aszerint, hogy a $H$ halmaz $i$-edik eleme az $A\cap B$, $\overline{A}\cap B$, $A\cap \overline{B}$, $\overline{A}\cap \overline{B}$ halmazok melyikéhez tartozik. Így összesen $4^n$ darab különböző számot kapunk, vagyis az összes $n$-jegyű szám előáll ezen a módon. Ezekben a számokban összesen ugyanannyi 0 van, mint ahány 1-es vagy ahány 2-es vagy amennyi 3-as. Tehát a bennük előforduló 0 jegyek száma összesen $\frac{1}{4}\cdot 4^n\cdot n=4^{n-1}\cdot n$; másrészt a nullák együttes száma éppen az $|A\cap B|$ elemszámoknak az összege.  Breuer János (Budapest, ELTE Apáczai Cs. J. Gyak. Gimn., 11. o.t.)   III. megoldás. A $H$ mindegyik $x$ eleméhez meghatározzuk azoknak az $A$, $B$ pároknak ($A$, $B\subseteq H$) a számát, amelyekre $x\in A\cap B$; a kapott számokat az $x$ elemekre összegezve éppen a feladatban szereplő összeghez jutunk. Ha $x\in A$, akkor a $H$ minden további eleme vagy eleme $A$-nak, vagy nem; ez két lehetőség, tehát $A$ megválasztása $2^{n-1}$-féleképpen történhet, akárcsak a $B$ halmazé. Az $x$-et tartalmazó $\left(A\mathrm{,}B\right)$ halmazokból tehát $2^{n-1}\cdot 2^{n-1}=4^{n-1}$ rendezett pár készíthető, a $H$ elemeire pedig összesen $n\cdot 4^{n-1}$.  Kiss 345 Gergely (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)