Bài 1: Một hội nghị Toán học quốc tế có 2011 nhà toán học tham dự. Biết rằng một nhà toán học bất kì trong số đó quen biết ít nhất với 1509 nhà toán học khác. Hỏi có thể lập ra một tiểu ban gồm 5 nhà toán học mà người bất kì trong 5 người đó đều quen biết những người con lại của tiểu ban đó hay không ?
Lời giải
Gọi S là tập các nhà Toán học trong hội nghị thì |S|=2011. Giả sử $x,y \in S$, ta quy ước nếu x,y quen biết nhau thì viết (x;y)=1. Xét $a,b \in S$ mà $(a;b)=1$. Đặt:
$A=\left \{ c\in S|c \ne b, (c,a)=1 \right \},B= \left \{c \in S| c \ne a, (c,b)=1 \right \}$
Thì $|A|, |B| \ge 1508, |A \cup B| \le 2009$
Suy ra: $|A \cap B|=|A|+|B|-|A \cup B| \ge 1007$ Do đó tồn tại $c \in A \cap B$, tức là tồn tại 3 nhà toán học a,b,c đôi một quen biết nhau.
Xét:$C=\left \{ d \in S|d \ne a, d\ne b,(d,c)=1 \right \}$ thì $|C| \ge 1507$ và $|(A \cap B) \cup C| \le 2009$ Suy ra:
$|A \cap B \cap C |=|A \cap B|+|C|-|(A \cap B) \cup C| \ge 505$ Do đó tồn tại $d \in A \cap B \cap C$ chứng tỏ có 4 nhà toán học a,b,c,d đôi một quen nhau. Tương tự xét $D$
Ta thu được $|A \cap B \cap C \ cap D| \ge 505+1506-2009=2$
Do đó tồn tại $e \in A \cap B \cap C \cap D$, chứng tỏ có 5 nhà toán học a,b,c,d,e đôi một quen biết nhau. Vậy có thể lập ra một tiểu ban gồm 5 nhà toán học mà bất kì trong 5 người đó đều quen biết những người còn lại của tiểu ban đó.
Bài 2: Trên đường tròn (C) có 2011 điểm. Hỏi có bao nhiêu cách xóa đi 11 điểm sao cho không có hai điểm bị xóa nào cạnh nhau.
Lời giải
Ta gọi một trong số 2011 điểm là A. Có hai trường hợp sau:
Trường hợp 1: Điểm A không bị xóa. Sau khi xóa 11 điểm còn lại 2000 điểm. Xen kẽ giữa 2000 điểm này có 2000 khoảng trông. Mười một điểm bị xóa tương ứng với 11 trong số 2000 khoảng trống nói trên. Do đó số cách thực hiện trong trường hợp này là:
$C^{11}_{2000}$
Trường hợp 2. Điểm A bị xóa. Sau khi xóa tiếp 10 điểm, còn lại 2000 điểm. Xen kẽ những 2000 điểm này có 1999 khoảng trống không kề với vị trí của điểm A. 10 điểm bị xóa (không kể điểm A) tương ứng với 10 trong số 1999 khoảng trống nói trên. Do đó số cách thực hiện trong trường hợp này bằng:
$C^{10}_{1999}$
Theo quy tắc cộng, cách xóa cần tìm thỏa mãn đề bài là:
$C^{11}_{2000}+C^{10}_{1999}$
