Phan Đình Trung: Tổ hợp rời rạc

Bài toán 1 (Đề nghị Olympic 30-4 toán 10 năm 2013 THPT Chuyên Vị Thanh, Hậu Giang)

Trong hình vuông cạnh bằng $8$ ta lấy $100$ điểm bất kì. Chứng minh rằng có ít nhất $4$ điểm nằm trong hình tròn có bán kính bằng $1$ .

Lời giải :

Vẽ hình vuông $ABCD$ có cạnh bằng $10$ có cùng tâm, các cạnh tương ứng song song với hình vuông ban đầu.

Vẽ $100$ hình tròn bán kính bằng $1$ có tâm tương ứng là $100$ điểm đã cho.

Khi đó $100$ hình tròn này đều nằm trong hình vuông $ABCD$ .

Ta có tổng diện tích hình tròn là $100\pi$ , diện tích hình vuông $ABCD$ là $100$ .

Vì $100\pi > 3.100$ nên theo nguyên lí $Dirichlet$ tồn tại $4$ hình tròn $(M,1),(N,1),(P,1),(Q,1)$ có điểm chung là $I$ .

Suy ra đường tròn $(I,1)$ sẽ chứa bốn điểm $M,N,P,Q$ . Đây là điều phải chứng minh.

Bài toán 2(Đề nghị Olympic 30-4 toán 10 năm 2010 THPT Chuyên Lê Qúy Đôn, Bình Định)

Cho bát giác $A_1A_2...A_8$ có tính chất : Tất cả các đỉnh có tọa độ nguyên và độ dài tất cả các cạnh là những số nguyên. Chứng minh rằng chu vi đa giác là một số chẵn.

Lời giải :

Ta gọi $A_i\left ( a_i,b_i \right ),\;\forall i=\overline{1,8}$ trong đó $a_i,b_i\in \mathbb{Z},\;\forall i=\overline{1,8}$

Ta có :

$A_iA_{i+1}=\sqrt{(a_{i+1}-a_i)^2+(b_{i+1}-b_i)^2}$ với quy ước $A_9\equiv A_1,a_9=a_1,b_9=b_1$

Gọi $P$ là chu vi bát giác. Ta có :

$P^2=(\underset{i=1}{\overset{8}{\sum}} A_iA_{i+1})^2=\underset{i=1}{\overset{8}{\sum}} A_iA_{i+1}^2+2\underset{1\leq i=j\leq 8}{\sum} A_iA_{i+1}.A_jA_{j+1}$

Ta có

$\underset{i=1}{\overset{8}{\sum}} A_iA_{i+1}^2=\underset{i=1}{\overset{8}{\sum} }\left ( (a_{i+1}-a_{i})^2+(b_{i+1}-b_i)^2 \right )=2\underset{i=1}{\underset{8}{\sum}}(a_i^2+b_i^2) -2\underset{i=1}{\overset{8}{\sum}} (a_ia_{i+1}+b_ib_{i+1})$

Là một số chẵn

Do vậy :

$P^2$ chẵn, kéo theo $P$ chẵn.

Ta có điều phải chứng minh.

Bài toán 3 : Giả sử rằng trong một nhóm $n$ người thỏa điều kiện cứ $n-2$ người bất kì thì có $3^k$ số cặp người quen nhau. Tìm $n$ .

Lời giải :

Theo đề bài cứ một nhóm gồm $n-2$ người thì có $3^k$ số cặp quen nhau, mà trong $n$ người, số nhóm $n-2$ người là $C_{n}^{n-2}$ . Do đó số cặp quen nhau trong $n$ người (tính cả các cặp trùng nhau trong các nhóm) là $C_{n}^{n-2}.3^k$ .

Xét hai người $A,B$ quen nhau. Trong $n-2$ người còn lại ta chọn ra $n-4$ người để tạo thành một nhóm $n-2$ người với $A,B$ . Số cách chọn như vậy là $C_{n-2}^{n-4}$ , tức là hai người quen nhau này có mặt trong $C_{n-2}^{n-4}$ nhóm.

Như vậy số cặp người quen nhau trong $n$ người là $m=\dfrac{3^k.C_{n}^{n-2}}{C_{n-2}^{n-4}}$

Ta có :

$m=\dfrac{3^k.C_{n}^{n-2}}{C_{n-2}^{n-4}}\in \mathbb{Z}^{+}\Rightarrow \dfrac{3^k.\dfrac{n!}{2!(n-2)!}}{\dfrac{(n-2)!}{2!(n-4)!}}=\dfrac{3^k.n(n-1)}{(n-2)(n-3)} \in \mathbb{Z}^{+}$

Xét $n\in \left \{ 1,2,3,4 \right \}$ thì nhận $n=4$

Nếu $n-3$ chẵn, đặt $n-3=2t,\;t\in \mathbb{N}^{*}$

Ta được $m=\dfrac{3^k.(2t+3)(2t+2)}{(2t+1).2t}=\dfrac{3^k(2t+3)(t+1)}{(2t+1).t}\in \mathbb{Z}^{+}$

Dễ dàng thấy rằng $gcd(2t+3,2t+1)=gcd(2t+1,t+1)=1$ nên $2t+1\mid 3^k\Rightarrow 2t+1=3^s\;\;,(s<k,s\in \mathbb{N}^*)$

Từ đó suy ra $t=\dfrac{3^s-1}{2}$ . Lúc này :

$m=\dfrac{3^k.(3^s+2).(\dfrac{3^s-1}{2}+1)}{3^s.\dfrac{3^s-1}{2}}=\dfrac{3^{k-s}.(3^s+2)(3^s+1)}{3^s-1}\in \mathbb{Z}^{+}$

Rõ ràng $gcd(3^{k-s},3^s-1)=gcd(3^s+2,3^s-1)=1$ nên $\dfrac{3^s+1}{3^s-1}\in \mathbb{Z}^{+}$ mà $gcd(3^s-1,3^s+1)=2\Rightarrow 3^s-1=2\Rightarrow s=1\Rightarrow n=5$

Nếu $n-3$ lẻ, đặt $n-3=2t+1,\;\;\left ( t\in \mathbb{N}^{*} \right )$

Ta được $m=\dfrac{3^k(2t+4)(2t+3)}{(2t+2)(2t+1)}=\dfrac{3^k(t+2)(2t+3)}{(t+1)(2t+1)}\in \mathbb{Z}^+$

Dễ dàng thấy rằng $gcd(t+1,t+2)=gcd(t+1,2t+3)=1$ nên phải có $t+1\mid 3^k\Rightarrow t=3^s-1,\;\left ( s=k,s\in \mathbb{N}^{*} \right )$

Lúc này :

$m=\dfrac{3^k.(3^s+1)(2.3^s+1)}{3^s(2.3^s-1)}=\dfrac{3^{k-s}.(3^s+1)(2.3^s+1)}{2.3^s-1}\in \mathbb{Z}^{+}$

Dễ thấy $gcd(2.3^s-1,3^s+1)=gcd(2.3^s+1,2.3^s-1)=gcd(3^{k-1},2.3^s-1)=1$ nên trường hợp này bị loại.

Kết luận : $\boxed{n\in \left \{ 4,5 \right \}}$

Bài toán 4 : Trong một trường học có $b$ thầy cô giáo và $c$ học sinh thỏa điều kiện :

a) Mỗi thầy cô giáo dạy đúng $k$ học sinh.

b) Với hai học sinh bất kì có đúng $h$ thầy cô dạy chung.

Chứng minh rằng

$\dfrac{b}{h}=\dfrac{c(c-1)}{k(k-1)}$

Lời giải :

Gọi $T_r$ là thầy dạy hai học sinh $S_i,S_j$ . Ta đếm số bộ ba $(T_r,S_i,S_j)$ bằng hai cách.

Số cách chọn $T_r$ là $b$ . Vì $T_r$ dạy đúng $k$ học sinh nên số cách chọn cặp học sinh $S_i,S_j$ là $C_{k}^{2}=k(k-1)$

Do đó số cách chọn bộ ba $(T_r,S_i,S_j)$ là $bk(k-1)$

Mặt khác vì $S_i,S_j$ có đúng $h$ thầy cô dạy chung nên $T_r$ có $h$ cách chọn. Mà số cặp $(S_i,S_j)$ có thể chọn là $C_{c}^{2}=c(c-1)$

Do đó số cách chọn bộ ba $(T_r,S_i,S_j)$ là $hc(c-1)$

Từ hai điều trên ta có :

$\dfrac{b}{h}=\dfrac{c(c-1)}{k(k-1)}$

Đây là điều phải chứng minh.

Bài toán 5 (Đề nghị Olympic 30-4 toán 10 năm 2011 THPT Chuyên Lê Hồng Phong TpHCM) Chứng minh rằng trong $17$ số nguyên tùy ý ta luôn chọn được $9$ số có tổng chia hết cho $9$ .

Lời giải :

Bổ đề : Trong $5$ số nguyên tùy ý thì luôn tồn tại $3$ số có tổng chia hết cho $3$

Chứng minh bổ đề :

Nếu như trong $5$ số đã cho có nhiều hơn $3$ số có cùng số dư khi chia cho $3$ thì hiển nhiên ta có điều phải chứng minh.

Nếu như trong $5$ số đã cho có ít hơn $3$ số có cùng số dư khi chia cho $3$ thì sẽ tồn tại ba số chia $3$ dư $0,1,2$ . Suy ra tổng của ba số này chia hết cho $3$ .

Bổ đề được chứng minh.

Trở lại bài toán :

- Chọn ra $5$ số nguyên bất kì trong $17$ số đã cho thì theo bổ đề luôn tồn tại $3$ số có tổng chia hết cho $3$ . Gọi tổng đó là $A_1=a_1+a_2+a_3$

- Trong $14$ số nguyên còn lại thì chọn ra $5$ số, sẽ có $3$ số có tổng chia hết cho $3$ . Gọi tổng đó là $A_2=a_4+a_5+a_6$

- Trong $11$ số nguyên còn lại tiếp tục chọn ra $5$ số thì sẽ có $3$ số có tổng chia hết cho $3$ . Gọi tổng đó là $A_3=a_7+a_8+a_9$ .

- Trong $8$ số nguyên còn lại thì lại chọn ra $5$ số, tồn tại $3$ số trong chúng có tổng chia hết cho $3$ . Gọi tổng đó là $A_4=a_{10}+a_{11}+a_{12}$ .

- Trong $5$ số nguyên còn lại thì tồn tại $3$ số có tổng chia hết cho $3$ . Gọi tổng đó là $A_5=a_{13}+a_{14}+a_{15}$

Do $A_1,A_2,A_3,A_4,A_5$ đều chia hết cho $3$ nên $A_{i}\equiv 0,3,6\;\;(mod\;9)$ với $i=1,2,3,4,5$

Nếu có nhiều hơn $3$ số trong $5$ số $A_i$ có cùng số dư khi chia cho $9$ thì hiển nhiên tổng ba số trong chúng chia hết cho $9$ . Gỉa sử $9\mid A_1+ A_2+ A_3\Rightarrow 9\mid (a_1+a_2+...+a_9)$ .

Nếu có ít hơn $3$ số trong $5$ số $A_i$ có cùng số dư khi chia cho $9$ thì sẽ tồn tại $3$ số khi chia cho $9$ và dư $0,3,9$ . Khi đó tổng của ba số này sẽ chia hết cho $9$ . Gỉa sử $9\mid A_1+ A_2+ A_3\Rightarrow 9\mid (a_1+a_2+...+a_9)$ .

Từ đây ta có điều phải chứng minh

.Bài toán 6 (Đề nghị Olympic 30-4 toán 10 năm 2003 THPT Hùng Vương, Gia Lai) : Cho $2003$ số dương $x_1,x_2,...,x_{2003}$ thỏa mãn hệ :

$\left\{\begin{matrix} x_1^2+x_2^2\leq x_2-x_1\\ x_2^2+x_3^2\leq x_3-x_2\\ ...\\ x_{2001}^2+x_{2002}^2\leq x_{2002}-x_{2001}\\ x_{2002}^2+x_{2003}^2\leq x_{2003}-x_{2002} \end{matrix}\right.$

Chứng minh rằng trong $2003$ số đã cho tồn tại hai số $x,y$ sao cho : $\left | x-y \right |<\dfrac{1}{2.10^{3}}$

Lời giải :

Ta có $0<x_{1}^2+x_{2}^2\leq x_{2}-x_1\Rightarrow x_1<x_{2}$

Hoàn toàn tương tự, từ đó ta có $0<x_1<x_2<....<x_{2003}$

Mặt khác thì

$x_{2002}^2+x_{2002}\leq x_{2003}-x_{2003}^2\Rightarrow x_{2003}^2<x_{2003}\Rightarrow x_{2003}<1$

Như vậy ta có $0<x_1<x_2<....<x_{2003}<1$ .

Chia đoạn $\left [ 0,1 \right ]$ thành $2002$ đoạn con bằng nhau, độ dài của mỗi đoạn là $\dfrac{1}{2002}$ .

Theo nguyên lí $Dirichlet$ thì sẽ tồn tại hai số $x,y$ thuộc cùng một đoạn.

Do đó $\left | x-y \right |<\dfrac{1}{2002}<\dfrac{1}{2.10^3}$

Bài toán 6: Cho $2001$ số tùy ý. Chứng minh rằng ta có thể chọn được một hoặc một số số nào đó mà tổng của chúng chia hết cho $2001$ .

Lời giải :

Gỉa sử $2001$ số đã cho là $a_{1},a_2,...,a_{2001}$ .

Xét $2001$ tổng sau :

$S_1=a_1$

$S_2=a_1+a_2$

$S_3=a_1+a_2+a_3$

…

$S_{2001}=a_1+a_2+...+a_{2001}$ .

Nếu có ít nhất một trong các tổng trên chia hết cho $2001$ thì hiển nhiên ta có điều phải chứng minh.

Gỉa sử không có tổng nào trong các tổng trên chia hết cho $2001$ , khi đó số dư trong phép chia mỗi tổng cho $2001$ thuộc tập $A=\left \{ 1,2,3,...,2000 \right \}$ .