4. Ta chứng minh n = 41 là giá trị nhỏ nhất cần tìm. Giả sử ngược lại, tồn tại 15 tập con của X , sao
cho hợp của mọi 7 tập trong số 15 tập con đó chứa ít nhất 41 phần tử, nhưng không tồn tại 3 tập
trong số 15 tập này có giao khác rỗng. Do mỗi phần tử của X chỉ có thể thuộc vào tối đa 2 tập
trong 15 tập đó, ta có thể giả sử mỗi phần tử của X thuộc vào chính xác 2 trong số 15 tập đó (nếu
không, thì ta có thể một số phần tử vào một số tập hợp trong 15 tập đó, thì điều kiện đầu tiên vẫn
đảm bảo). Theo nguyên lý Dirichlet, tồn tại một tập hợp trong số 15 tập, ký hiệu là A, mà
2 × 56
| A | ≥
+ 1 = 8,
15
và gọi 14 tập còn lại là A
1, A
2, . . . , A
14.
• Do hợp của mọi 7 tập trong A
1, A
2, . . . , A
14 chứa ít nhất 41 phần tử. Do đó tổng số phần tử
trong 15 tập này
14
y ≤ 41 ×
.
7
• Với mỗi a ∈ X, nếu a
not ∈ A thì a thuộc vào chính 2 2 tập trong số A
1, A
2, . . . , A
14. Do đó a được tính lặp
− binom127 lần. Nếu a ∈ A, thì A chỉ thuộc vào đúng một tập A
1, A
2, . . . , A
14. Do đó a
147được tính lặp T 147 −
137 lần. Do đó
≤ y
41 ×
12
13
−
+ | A |
≤ (56 − | A | )
− | A |
≤ 56
− 8
,
từ đây dẫn đến 196 ≤ 195, mâu thuẫn.
Định lý 3.1 (Erdos). Cho F là một họ các tập con của tập n phần tử X thỏa mãn
Bạn đang xem 4. - Chuyên đề Toán chuyên
