TIẾP THEO, TỔNG SỐ CÁC TẬP CON CHỨA 1 PHẦN TỬ, CHỨA 2 PHẦN TỬ, CHỨA...

3. Tiếp theo, tổng số các tập con chứa 1 phần tử, chứa 2 phần tử, chứa 3 phần tử của M là

20

+

= 1350

2

1

3

và tất cả các tập này thỏa mãn điều kiện bài toán (rõ ràng hai tập phân biệt bất kỳ trong các tập

này có giao không vượt quá 2 phần tử). Do đó n = 1350 đạt được.

Từ đó suy ra giá trị lớn nhất của n là n = 1350.

Ví dụ 2.5.2 (Indian 2014). Cho số tự nhiên n và X = { 1, 2, . . . , n } . Với hai tập con A và B của X, ký

hiệu

A ∆ B = { i ∈ X | i ∈ (A \ B) ∪ (B \ A) } .

Gọi F là một họ các tập con của X sao cho với mọi A, B ∈ F thì

| A ∆ B | ≥ 2.

Chứng minh rằng | F | ≤ 2

và tìm tất cả các họ F có 2

phần tử.

Chứng minh. 1. Với mỗi tập con A ⊂ { 1, 2, . . . , n − 1 } , thì trong cặp tập hợp (A, A ∪ { n } ), tối đa

một tập hợp thuộc vào F . Thật vậy vì

A \ (A ∪ { n } ) = /0, (A ∪ { n } ) \ A = { n } ⇒ A ∆(A ∪ { n } ) = { n } .

Mặt khác, ta có tối đa 2

cặp tập hợp (A, A ∪ { n } ). Do đó tập F có tối đa 2

phần tử.