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