OKTV 2008/2009 II. kategória döntő 3. feladat
(Feladat azonosítója: OKTV_20082009_2kdf3f )
Témakör: *Kombinatorika

A $ H = \left\{ 1; 2; 3; ...; 9 \right\} $ halmaz egy $ P $ partíciójának nevezzük azt, ha $ H $-t diszjunkt részhalmazainak uniójaként írjuk fel. (A részhalmazok páronként közös elem nélküliek.) Jelölje $ P (n) $ az $ n $-t tartalmazó részhalmaz elemeinek számát ($ n \in H $). Például a $ P : \{1; 4; 5\} \cup \{2\} \cup \{3; 6; 7; 8; 9\} = H $ partíció esetén $ P (6) = 5 $. Bizonyítsuk be, hogy $ H $ bármely $ P_1 $ és $ P_2 $ partíciójára található két különböző $ H $-beli $ n $ és $ m $ elem, amelyekre $ P_1 (n) = P_1 (m) $ és $ P_2 (n) = P_2 (m). $



 

Megoldás:

$  - $