1. Không tồn tại i, j nào trong { 1, 2, . . . , m } để A
i∪ A
j= S và | A
i∩ A
j| = 1. Gọi x là phần tử tùy ý
thuộc S. Khi đó
• Theo giả thiết quy nạp, số tập A
i lớn nhất không chứa x là 2
n−2− 1.
• Số các tập con chứa x của S bằng 2
n−1. Nếu x ∈ A
i thì sẽ không có chỉ số j nào để A
j =
(S \ A
i) ∪ { x } , nếu không sẽ dẫn đến | A
i∩ A
j| = 1, mâu thuẫn. Do vậy, chỉ có cùng lắm là
một nửa số tập con chứa x của S xuất hiện dưới dạng các tập A
i. Như thế số lớn nhất các
tập A
ilà
2
n−2− 1 + 2
n−2= 2
n−1− 1.
Bạn đang xem 1. - Chuyên đề Toán chuyên
