Bài tổ hợp

Bài toán: Cho tập hợp .Tìm số nguyên dương nhỏ nhất sao cho mỗi tập con gồm phần tử của đều chứa phần tử phân biệt sao cho là số nguyên tố.

Lời giải:

Nếu cùng chẳn thì chẳn và lớn hơn 2 nên không là số nguyên tố.

Trong tập gồm số chẵn,do đó nếu thì tồn tại tập con gồm phần tử chẳn của .Khi đó trong tập con này không tồn tại để là số nguyên tố.

Do đó .Ta sẽ chứng minh thỏa mãn.

Thật vậy,ta chia tập thành tập con gồm phần tử mà là số nguyên tố.

Các tập con đó là:

Do đó theo nguyên lí Dirichle thì trong phần tử tồn tại phần tử thuộc trong tập trên,nên ta luôn có sao cho là số nguyên tố.

Vậy là số bé nhất thỏa mãn ycbt.