TỪ TRÊN TA THẤY F LÀ MỘT ĐƠN ÁNH TỪ X \ S VÀO CÁC TẬP CON CHỨA 3 PH...

4. - Chuyên đề Toán chuyên
Toán Chuyên đề Toán chuyên

4. Từ trên ta thấy f là một đơn ánh từ X \ S vào các tập con chứa 3 phần tử của S. Do đó

k

| X \ S | ≤ | S | ⇔ n − k ≤

.

3

Từ đây suy ra

+ 6k = k

3

− 3k

2

+ 8k ≤ k

3

− 3 ⇒ k ≥ √

3

6n + 3.

6n ≤ 6

Bài toán được chứng minh hoàn toàn.

Ví dụ 2.3.3 (India Postal Coaching 2014 Set 5 Problem 4). Tập M được viết dưới dạng M = A

1

∪

A

2

∪ . . . ∪ A

n

và A

i

∩ A

j

= /0 với mọi 1 ≤ i < j ≤ n, thì các tập A

1

, A

2

, . . . ,A

n

được gọi là một n_phân

hoạch của M. Giả sử A

1

, A

2

, . . . , A

n

và B

1

, B

2

, . . . , B

n

là hai n_phân hoạch của M thỏa mãn

| A

i

∪ B

j

| ≥ n, ∀ 1 ≤ i, j ≤ n.

Chứng minh | M | ≥ n

2