Feladat: 19.22. Egy
n elemű halmazból háromelemű részhalmazokat akarunk kiválasztani úgy, hogy semelyik elempár ne szerepeljen két kiválasztott részhalmazban. (Vagy másképp fogalmazva: hogy bármely két kiválasztott hármasnak legfeljebb egy közös eleme legyen.) Bizonyítsuk be, hogy legfeljebb a hármasok
n-2-ed részét választhatjuk ki!
Megoldás: 19.22
Minden pár legfeljebb egy kiválasztott hármasban szerepelhet, egy kiválasztott hármasban három elempár szerepel, tehát
l-lel jelölve a kiválasztott részhalmazok számát
3l≤(
n
2
). Tehát legfeljebb
n(n-1)/6 részhalmazt választhatunk ki.