Feladat: 19.27.
Egy
n elemű halmazból
H kiválasztottunk néhány
l elemű részhalmazt úgy, hogy bármely kettőnek legfeljebb egy közös eleme van.
a) Bizonyítsuk be, hogy legfeljebb
n(n-1)/l(l-1) halmazt választottunk ki.
b) Tudjuk még azt is, hogy a kiválasztott halmazok a
H halmaz minden elempárját pontosan egyszer fedik le. Bizonyítsuk be, hogy akkor
n-1 osztható
l-1-gyel és
n(n-1) oszható
l(l-1)-gyel.
Megoldás: 19.27
a) Egy
l elemű részhalmaz
l(l-1)/2 elempárt fed le. A feltétel szerint egyetlen elempár sem szerepel többször, tehát ha
k részhalmazt választottunk ki, akkor
, azaz a kiválasztott halmazok száma legfeljebb
n(n-1)/k(k-1).
b) Minden
x elem pontosan
n-1 elempárban van benne, ezek közül egy-egy
x-et tartalmazó halmaz
l-1-et fed le (az
x-et nem tartalmazó halmazok pedig egyet sem). Ha minden elempár pontosan egyszer van lefedve, akkor tehát
x pontosan
(n-1)/(l-1) kiválasztott halmazban szerepel, így ez a szám egész szám. Másrészt a részhalmazok száma is pontosan
n(n-1)/l(l-1), tehát ez is egész szám.