Problem B. 4625. (April 2014)

B. 4625. How many ordered pairs \(\displaystyle (A,B)\) are there such that \(\displaystyle A\) and \(\displaystyle B\) are subsets of a fixed \(\displaystyle n\)-element set, and \(\displaystyle A\subseteq B\)?

(4 pont)

Deadline expired on May 12, 2014.

Sorry, the solution is available only in Hungarian. Google translation

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\).

Statistics:

79 students sent a solution.
4 points:	63 students.
3 points:	9 students.
2 points:	1 student.
1 point:	5 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, April 2014