XÉT 31 TẬP HỢP A2, A3, . . . , A31 VÀ B VỚI A ∈ AJ, ∀ J = 2, 3, . ....
3. Xét 31 tập hợp A
2, A
3, . . . , A
31và B với a ∈ A
j, ∀ j = 2, 3, . . . , 30 và a 6∈ B.
• Vì | A
j∩ B | = 1, ∀ j = 2, 3, . . . , 31, các tập A
jđều chứa a, còn B không chứa a, nên { x
j} =
A
j∩ B thì x
j∈ B \{ a } .
• Có 31 phần tử x
2, . . . , x
31trong tập B \{ a } , mỗi phần tử trong chúng thuộc vào ít nhất một
tập hợp trong 30 tập A
j, j ∈ { 2, . . . , 31 } , nên tồn tại một phần tử x
t, với t ∈ { 2, 3, . . . , 29 }
thuộc vào hai tập hợp A
r, A
s(r , s ∈ { 2, 3, . . . , 31 } ).
• Khi đó { a, x
t} ⊂ A
r∩ A
s, mâu thuẫn với giả thiết | A
r∩ A
s| = 1.
Vậy điều giả sử là sai. Bài toán được chứng minh.
Ví dụ 2.2.3 (China TST1994, Ví dụ 3.1.2). Cho A
1, A
2, . . . , A
klà các tập con của X = { 1, 2, . . . , 10 }
sao cho (
| A
i| ≥ 5, ∀ i = 1, 2, . . . , k
| A
i∩ A
j| ≤ 2, ∀ 1 ≤ i < j ≤ k.
Tìm giá trị lớn nhất có thể có của k.
Chứng minh. Trong ví dụ 3.1.2 ta đã giải bài toán này bằng chặn Plotkin, và xây dựng được với k = 6.
Do đó k ≥ 6. Nếu k ≥ 7, ta trình bày một lời giải kết hợp đếm số tập hợp chứa phần tử và nguyên lý
bao hàm loại trừ (inclusion - exclusion principle). Với mỗi i ∈ X , đặt
n
i= |{ j ∈ { 1, 2, . . . , k | i ∈ A
j}}|
tức đếm số tập hợp trong A
1, A
2, . . . , A
kchứa phần tử i. Khi đó
∑
10∑
k| A
k| ≥ 5k = 35.
n
i=
i=1j=1Do đó phải tồn tại chỉ số i
0sao cho n
i0