Feladat: 19.25.
a) Egy húszelemű halmaznak kiválasztottunk néhány ötelemű részhalmazát úgy, hogy semelyik kettőnek nincs egynél több közös eleme. Bizonyítsuk be, hogy legfeljebb 19 részhalmazt választottunk ki. b) Igaz marad-e az állítás akkor is, ha csak azt tudjuk, hogy minden halmaz legalább ötelemű? * c) Meg lehet-e adni egy húszelemű halmaz 19 ötelemű részhalmazát úgy, hogy semelyik kettőnek ne legyen egynél több közös pontja? d) Kiválasztottuk egy 16 elemű halmaznak néhány ötelemű részhalmazát úgy, hogy semelyik kettőnek nincs egynél több közös eleme. Bizonyítsuk be, hogy legfeljebb 12 részhalmazt választhattunk ki.
 

Megoldás: 19.25
A feltétel szerint a húszelemű halmaz bármely két eleme legfeljebb egy kiválasztott részhalmazban szerepelhet egyszerre. Egy kiválasztott részhalmaz (legalább) 10 ilyen elempárt ,,fed le", tehát ha k részhalmazt választottunk ki, ezek együtt (legalább) 10k párt fednek le. A húszelemű halmaz elemeiből 190 pár képezhető, tehát k legfeljebb 19 lehet. (Az is csak akkor, ha minden halmaz pontosan ötelemű.) Ezzel a)-t is, b)-t is bebizonyítottuk.

c) Ha a 19 ötelemű halmaz közül semelyik kettőnek nincs egynél több közös pontja, akkor minden elempár legfeljebb egyszer szerepel. Ez viszont azt jelenti, hogy a húszelemű halmaz mind a 190 elempárja szerepel, mert egy ötelemű halmaz tíz elempárt ,,fed le". Vegyünk ki egy tetszőleges x elemet. Nézzük, ez hány halmazban szerepel. Nem szerepelhet öt halmazban, mert akkor húsz elempárban szerepelne, márpedig csak 19 elempárban szerepel. Tehát legfeljebb négy halmazban szerepel. Ez bármely elemről elmondható, tehát bármely elem legfeljebb négy halmazban szerepel. Vagyis a kiválasztott ötelemű halmazok elemszámának összege legfeljebb 80 (minden elemet négyszer számolhatunk). Ez azt jelenti, hogy legfeljebb 16 ötelemű halmaz választható ki a megadott tulajdonsággal.

d) A bizonyítás ugyanúgy megy, mind a) esetében: Ha k darab részhalmazt választotttunk ki, ezek együtt 10k elempárt ,,fednek le". Összesen a 16 elemű halmaz elemeiből 120 elempár készíthető, ezért k≤12.