3. Bây giờ ta gọi S
m là họ các tập con, mỗi tập con m phần tử của tập X. Trường hợp "xấu nhất",
tức là cần nhiều tập con nhất trong S
m mà mỗi tập đó đều nhận một phần tử trong F
k là tập
con, là mỗi phần tử A của F
k, riêng biệt, là tập con của một tập Y trong S
m.
A
Y
F
k S
mĐến đây ta có ngay được kết luận bài toán nếu chứng tỏ được
| S
m| ≥ | F
k| .
(khi đó sẽ có một phần tử trong S
m không nhận bất cứ tập nào trong F
k là tập con, tập này có m
phần tử. Dĩ nhiên ta có thể bổ sung vào tập này một số phần tử nữa nếu không bị vi phạm.) Ta
có được kết luận nếu chứng tỏ được
n
n!
1
≤
⇔ 1
m!(n − m)!
k!(n − k)! ≤ n!
k
n − k + 1
m
hay
n − k
m
m!
.
(n − m)!(m − k)! ⇔ 1
(n − m)! ⇔ 1
k!(m − k)! ≤ (n − k)!
k! ≤ (n − k)!
m − k
Nhưng kết quả trên là hiển nhiên, vì ta có được khẳng định mạnh hơn là
< 1 ( ∗ ).
Bạn đang xem 3. - Chuyên đề Toán chuyên
