5. XÂY DỰNG - QUY NẠP - TRUY HỒIVÍ DỤ 5.1. CHO N NGUYÊN DƯƠNG VÀ T...

2.5. XÂY DỰNG - QUY NẠP - TRUY HỒI

Ví dụ 2.5.1. Cho n nguyên dương và tập hợp M = { 1, 2, . . . , 20 } . Gọi A

, A

, . . . , A

là các tập con phân

biệt khác rỗng của M sao cho

| A

∩ A

| ≤ 2, ∀ 1 ≤ i < j ≤ n.

Tìm giá trị lớn nhất của n.

Chứng minh. 1. Giả sử A

, A

, . . . , A

là các tập con của M thỏa mãn điều kiện bài toán. Nếu một

trong các tập A

, A

, . . . , A

có ít nhất 4 phần tử, không mất tính tổng quát, giả sử | A

| ≥ 4. Gọi a

là một phần tử trong A

.

• Khi đó A

\{ a } là tập có ít nhất ba phần tử. Do | A

∩ A

| ≤ 2, ∀ i = 2, 3, . . . , n nên tập A

\{ a }

phải phân biệt với tất cả các tập A

, . . . , A

(vì nếu A

\{ a } ≡ A

nào đó, thì

A

\{ a } ∩ A

= A

\{ a }

có ít nhất ba phần tử. Khi đó A

∩ A

cũng có ít nhất ba phần tử, vô lý.)

• Ngoài ra

| (A

\{ a } ) ∩ A

| ≤ | A

∩ A

| ≤ 2, ∀ j = 2, 3, . . . , n.