Feladat:	B.4625	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Gáspár Attila
Füzet:	2015/március, 149. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Halmazelmélet, Részhalmazok, Kombinatorikai leszámolási problémák
Hivatkozás(ok):	Feladatok: 2014/április: B.4625

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. Ha $B$-nek $k$ eleme van, akkor, mivel egy $k$ elemű halmaznak összesen $2^k$ részhalmaza van, az $A$ halmaz $2^k$ féle lehet. Az $n$ elemű alaphalmaznak $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ darab $k$ elemű részhalmaza van, így a feladat feltételeinek megfelelő $\left(A\mathrm{,}B\right)$ párok száma összesen $\begin{array}{c}{\displaystyle \sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k\mathrm{.}}\end{array}$ A binomiális tétel szerint ennek az összegnek az értéke éppen ${\left(1+2\right)}^n=3^n$. Tehát az $A\subseteq B$ feltételnek eleget tevő rendezett $\left(A\mathrm{,}B\right)$ párok száma $3^n$.   II. megoldás. Legyen a feladatban szereplő $n$ elemű halmaz egy tetszőleges eleme $x$. Mivel $A\subseteq B$, ezért a következő három lehetőség közül pontosan az egyik teljesül, továbbá az $A$ és $B$ halmazok egyértelműen meghatározzák, hogy melyik: $•$ $x\in A$  és  $x\in B$; $•$ $x\notin A$  és  $x\in B$; $•$ $x\notin A$  és  $x\notin B$. Ugyanis, ha $x\in A$ és $x\notin B$, akkor $A$ nem részhalmaza $B$-nek, ezért ez nem lehetséges. Megfordítva, ha mind az $n$ elemre a fenti három lehetőség valamelyike áll fenn, vagyis nincs olyan $x$ elem, amelyre $x\in A$, de $x\notin B$ teljesülne, akkor $A\subseteq B$ is teljesül. A különböző elemekre egymástól függetlenül (az összes lehetséges módon) eldönthető, hogy a három lehetőség közül melyik teljesül, és ez már meghatározza $A$-t és $B$-t, ezért a feladat kérdésére a válasz $3^n$.