2. Tồn tại một phần tử x ∈ S sao cho A
1∪ A
2 = S và A
1∩ A
2 = { x } . Đặt | A
1| = r + 1, | A
2| = s + 1
thì r + s = n − 1.
• Theo giả thiết quy nạp, số lớn nhất các tập A
i sao cho A
i⊂ A
1 là 2
r− 1.
• Theo giả thiết quy nạp, số lớn nhất các tập A
j sao cho A
j ⊂ A
2 là 2
s− 1.
• Bây giờ đếm tiếp xem có bao nhiêu tập dạng A
i mà không là tập con của A
1, A
2. Nếu A
ikhông là tập con của A
1, A
2 thì A
1∩ A
i6 = /0, A
i∩ A
j 6 = /0. Vì A
1∩ A
2 6 = /0, nên theo giả thiết
thì
A
1∩ A
2∩ A
i6 = /0 ⇒ A
1∩ A
2∩ A
i= { x } .
Do đó A
i = { x ∪ (A
i\ A
2) ∪ (A
i\ A
2) } . Ngoài ra co các tập khác rỗng A
i∩ A
1 và A
i\ A
2 có
thể được chọn tương ứng theo 2
s− 1 và 2
r− 1 cách, nên số lớn nhất các tập A
i dạng này là
(2
s− 1)(2
r− 1).
Từ đó suy ra số lớn nhất các tập dạng này là
2
r− 1 + 2
s− 1 + (2
r− 1)(2
s− 1) = 2
r+s− 1 = 2
n−1− 1.
Bài toán được chứng minh hoàn toàn.
TÀI LIỆU THAM KHẢO
Bạn đang xem 2. - Chuyên đề Toán chuyên