A B. 4625. feladat (2014. április)

B. 4625. Hány olyan $\displaystyle (A,B)$ rendezett pár van, ahol $\displaystyle A$ és $\displaystyle B$ egy rögzített $\displaystyle n$ elemű halmaz részhalmazai és $\displaystyle A\subseteq B$?

(4 pont)

A beküldési határidő 2014. május 12-én LEJÁRT.

Megoldás. Legyen a feladatban szereplő $\displaystyle n$ elemű halmaz egy tetszőleges eleme $\displaystyle x$. Mivel $\displaystyle A\subseteq B$, ezért a következő három lehetőség közül pontosan az egyik teljesül: (i) $\displaystyle x\in A$ és $\displaystyle x\in B$ (ii) $\displaystyle x\notin A$, de $\displaystyle x\in B$ (iii) $\displaystyle x\notin A$, $\displaystyle x\notin B$. Megfordítva, ha minden az $\displaystyle n$ elemre ezen három lehetőség valamelyike áll fenn, vagyis nincs olyan $\displaystyle x$ elem, amelyre $\displaystyle x\in A$, de $\displaystyle x\notin B$ teljesülne, akkor $\displaystyle A\subseteq B$ is teljesül. Mivel a különböző elemekre egymástól függetlenül (az összes lehetséges módon) kiválasztható, hogy a három lehetőség közül melyik teljesül, és ez már meghatározza $\displaystyle A$-t és $\displaystyle B$-t, ezért a feladat kérdésére a válasz $\displaystyle 3^n$.

Statisztika:

79 dolgozat érkezett.
4 pontot kapott:	63 versenyző.
3 pontot kapott:	9 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2014. áprilisi matematika feladatai