SỬ DỤNG CÁC NGUYÊN LÝ TỔ HỢPVÍ DỤ 1. GỌI A LÀ TẬP TẤT CẢ CÁC...

2.2. SỬ DỤNG CÁC NGUYÊN LÝ TỔ HỢP

Ví dụ 2.2.1. Gọi A là tập tất cả các số tự nhiên lẻ không chia hết cho 5 và nhỏ hơn 30. Tìm số k nhỏ

nhất sao cho mỗi tập con của A gồm k phần tử đều tồn tại hai số chia hết cho nhau.

Giải. Ta có

A = { 1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29 } , | A | = 12.

Xét tập

B = { 9, 11, 13, 17, 19, 21, 23, 29 } .

Khi đó hai phần tử bất kì thuộc B thì không chia hết cho nhau. Từ đó ta suy ra được k ≥ 9. Ta chứng

minh k = 9 thỏa đề bài. Xét S là một tập con bất kì của A và | S | = 9. Xét ba cặp { 21, 7 } , { 27, 9 } , { 1, 11 }

ta thấy mỗi cặp là bội của nhau. Nếu trong 3 cặp trên có ít nhất một cặp thuộc S thì bài toán được giải

quyết. Giả sử trong ba cặp trên không có cặp nào cùng thuộc S, do | S | = 9 nên S phải chứa một số trong

mỗi cặp và chứa 6 số còn lại. Từ đó suy ra trong S phải có cặp { 3, 9 } hoặc { 3, 27 } và mỗi cặp này là

bội của nhau. Hay nói cách khác trong S luôn tồn tại hai số chia hết cho nhau. Vậy min k = 9.

Nhận xét 2. Mấu chốt trong bài toán trên là chúng ta phát hiện ra tập A

để từ đó ta khẳng định được

k ≥ 9 và dự đoán min k = 9. Để tìm tập B, ta liệt kê hết các số trong A mà không có hai số nào là bội

của nhau. Với bài toán này, việc tìm ra tập B khá đơn giản.

Ví dụ 2.2.2 (KMO 1990). Cho n tập hợp A

, A

, . . . , A

thỏa mãn



| A

| = 30, ∀ i = 1, 2, . . . , n

 

| A

∩ A

| = 1, ∀ i 6 = j

 

A

∩ A

∩ ··· ∩ A

= /0.

Chứng minh n < 872.

Chứng minh. 1. Giả sử n ≥ 872. Xét tập hợp A

, | A

| = 30. Do

| A

∩ A

| = 1, ∀ i = 2, 3, . . . , n

nên theo nguyên lý Dirichlet, tồn tại phần tử a ∈ A

thuộc vào ít nhất là

872

h n

i

+ 1 = 30

+ 1 ≥

30

tập hợp. Không mất tính tổng quát, gọi các tập hợp đó là A

, A

, . . . , A

.