Tuyển tập Tổ hợp - Rời rạc19 bài

Bài toán (China 1991) 

Cho dãy số $(u_n)$ nguyên thỏa mãn $u_{n+2}=u_{n+1}^2-u_n$ với mọi $n$ tự nhiên. Gỉa sử $u_0=39,u_1=45$. Chứng minh có vô hạn số hạng của dãy $(u_n)$ chia hết cho $1986$.

Lời giải :

Gọi $r_n$ là số dư của $u_n$ khi chia cho $1986$ ứng với mỗi $n$. Ta chứng minh dãy $(r_n)$ tuần hoàn.

Xét dãy gồm các bộ số dư :

$$(r_1,r_2),(r_2,r_3),...,(r_m,r_{m+1}),...$$

Dãy trên có vô số số hạng mà số bộ khác nhau là hữu hạn vì $r_i\in \left\{0,1,2,...,1985\right\}$. Như vậy theo nguyên lí Dirichlet, sẽ tồn tại hai bộ trùng nhau. Tức là tồn tại $k,m$ nguyên dương :

$$(r_{m+1},r_{m+2})=(r_{m+k+1},r_{m+k+2})$$

Từ đó :

$$r_m=r_{m+1}^2-r_{m+2}=r_{m+k+1}^2-r_{m+k+2}=r_{m+k}$$

$$r_{m-1}=r_m^2-r_{m+1}=r_{m+k}^2-r_{m+k+1}=r_{m+k-1}$$

…

$$r_1=r_2^2-r_3=r_{k+2}^2-r_{k+3}=r_{k+1}$$

Tức là ta đã được :

$$(r_1,r_2)=(r_{k+1},r_{k+2})$$

Từ đó dựa vào công thức xác định dãy, ta thu được :

$$r_n=r_{n+k},\forall n=0,1,\mathrm{2...}$$

Hơn nữa ta có $u_2=45^2-39=1986$ nên sẽ tồn tại vô hạn số hạng của dãy $(u_n)$ chia hết cho $1986$.

Bài toán : Cho dãy $(u_n)$ thỏa mãn :

$$\{\begin{array}{c}{u}_1=1,u_2=2\\ u_{n+2}=3u_{n+1}+u_n,\forall n\ge 1\end{array}$$

Với mỗi số nguyên dương $n$ ta gọi $r_n$ là số dư khi chia $u_n$ cho $2013$. Chứng minh rằng dãy $(r_n)$ là dãy tuần hoàn.

Lời giải :

Dãy số $(r_n)$ có công thức :

$$\{\begin{array}{c}{r}_1=1,r_2=2\\ r_{n+2}\equiv 3r_{n+1}+r_n(mod2013)\end{array}$$

Xét dãy các bộ hai số :

$$(r_1,r_2),(r_2,r_3),....,(r_n,r_{n+1}),(r_{n+1},r_{n+2}),...$$

Dãy trên có vô số bộ nhưng do $r_n\in \left\{1,2,...,2012,2013\right\}$ với mọi $n$ nên chỉ có hữu hạn bộ đôi một khác nhau. Vì vậy theo nguyên lí Dirichlet sẽ tồn tại hai bộ trùng nhau. Nghĩa là tồn tại các số nguyên dương $m,k$ sao cho :

$$(r_{m+1},r_{m+2})=(r_{m+k+1},r_{m+k+2})$$

Từ đó ta có :

$$r_m\equiv -3r_{m+1}+r_{m+2}=-3r_{m+k+1}+r_{m+k+2}\equiv r_{m+k}(mod2013)$$

$$r_{m-1}\equiv -3r_m+r_{m+1}=-3r_{m+k}+r_{m+k+1}\equiv r_{m+k-1}(mod2013)$$

$$...$$

$$r_1\equiv -3r_2+r_3=-3r_{k+2}+r_{k+3}\equiv r_{k+1}(mod2013)$$

Như vậy ta có :

$$\left(r_1,r_2\right)=\left(r_{k+1},r_{k+2}\right)$$

Lại kết hợp với :

$$r_{n+2}=3r_{n+1}+r_n(mod2013)$$

Ta chứng minh được :

$$r_n=r_{n+k},\forall n\in {\mathbb{Z}}^{+}$$

Từ đó dãy $(r_n)$ là dãy tuần hoàn.

 

Bài toán trên chỉ là một trường hợp cụ thể của “Định lí tuần hoàn của dãy số dư” có nội dung như sau :

Xét dãy số $(a_n)$ :

$$\{\begin{array}{c}{a}_1,a_2,...,a_k\in \mathbb{Z}\\ a_{n+k}=A_1{a}_{n+k-1}+A_2{a}_{n+k-2}+...+A_k{a}_n\end{array}$$

Với $A_i$ là các số nguyên. Khi đó với số nguyên dương $X$ bất kì, dãy số dư của $(a_n)$ theo modulo $X$ là dãy tuần hoàn.

Bài toán   (Đề 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 (Japan MO 1997) 

 Chứng minh rằng với mọi số thực dương $a,b,c$ ta đều có :

$\frac{(b+c-a{)}^2}{a^2+(b+c{)}^2}+\frac{(c+a-b{)}^2}{b^2+(c+a{)}^2}+\frac{(a+b-c{)}^2}{c^2+(a+b{)}^2}$$\ge \frac{3}{5}$

Lời giải :

Do tính thuần nhất của bất đẳng thức mà ta có thể chuẩn hóa $a+b+c=1$. Khi đó ta viết BĐT thành :

$\frac{(2a-1{)}^2}{a^2+(1-a{)}^2}+\frac{(2b-1{)}^2}{b^2+(1-b{)}^2}+\frac{(2c-1{)}^2}{c^2+(1-c{)}^2}$$\ge \frac{3}{5}$$\iff \frac{(2a-1{)}^2}{2a^2-2a+1}+\frac{(2b-1{)}^2}{2b^2-2b+1}+\frac{(2c-1{)}^2}{2c^2-2c+1}$$\ge \frac{3}{5}$

Theo nguyên lí $Dirichlet$ ta có :

$\left(b-\frac{1}{3}\right)\left(c-\frac{1}{3}\right)$$\ge 0$$\Rightarrow b^2+c^2$$={\left(b+c-\frac{1}{3}\right)}^2+\frac{1}{9}-2\left(b-\frac{1}{3}\right)\left(c-\frac{1}{3}\right)$$\le {\left(b+c-\frac{1}{3}\right)}^2+\frac{1}{9}$$={\left(\frac{2}{3}-a\right)}^2+\frac{1}{9}$

Theo BĐT $Cauchy-Schwarz$ :

$\frac{(2b-1{)}^2}{2b^2-2b+1}+\frac{(2c-1{)}^2}{2c^2-2c+1}$$\ge \frac{(2b+2c-2{)}^2}{2(b^2+c^2)-2(b+c)+2}$$=\frac{2a^2}{(b^2+c^2)+a}$$\ge \frac{2a^2}{\frac{1}{9}+{\left(\frac{2}{3}-a\right)}^2+a}$$=\frac{18a^2}{9a^2-3a+5}$

Công việc còn lại là chứng minh :

$\frac{18a^2}{9a^2-3a+5}$$\ge \frac{3}{5}-\frac{(2a-1{)}^2}{2a^2-2a+1}$$\iff (3a-1{)}^2(17a^2-8a+5)$$\ge 0$

Điều này hiển nhiên đúng.

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

 

Bài toán (Đề 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(mod9)$ 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 (Đề 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ệ :

$$\{\begin{array}{c}{x}_1^2+x_2^2\le x_2-x_1\\ x_2^2+x_3^2\le x_3-x_2\\ ...\\ x_{2001}^2+x_{2002}^2\le x_{2002}-x_{2001}\\ x_{2002}^2+x_{2003}^2\le x_{2003}-x_{2002}\end{array}$$

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

Lời giải :

Ta có $0<x_1^2+x_2^2\le 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}\le 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à $\frac{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|<\frac{1}{2002}<\frac{1}{2.10^3}$

Bài toán : 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\}$.

Theo nguyên lí $Dirichlet$ thì sẽ tồn tại hai tổng có cùng số dư $r$ khi chia cho $2001$ với $r\in A$.

Gỉa sử đó là hai tổng $S_m=a_1+a_2+...+a_m$ và $S_n=a_1+a_2+....a_n$ với $m,n\in \left\{1,2,3,...,2001\right\},m<n$.

Khi đó thì $2001\mid S_n-S_m\Rightarrow 2001\mid a_{m+1}+a_{m+2}+...a_{m+(n-m)}$.

Tức là luôn chọn được các số thỏa yêu cầu đề bài (điều phải chứng minh)

Bài toán : Cho các số dương $a,b,c$. Chứng minh bất đẳng thức :

$$abc+\sqrt[3]{(1+a^3)(1+b^3)(1+c^3)}\ge ab+bc+ca$$

Lời giải :

Áp dụng BĐT $Holder$ :

$(1+a^3)(1+b^3)(c^3+1)$$\ge (c+ab{)}^3$$\Rightarrow \sqrt[3]{(1+a^3)(1+b^3)(1+c^3)}$$\ge ab+c$

Do đó ta chỉ cần chứng minh :

$abc+ab+c$$\ge ab+bc+ca$$\iff abc+c$$\ge bc+ca$$\iff ab+1$$\ge a+b$$\iff (a-1)(b-1)$$\ge 0$

Theo nguyên lí $Dirichlet$ thì tồn tại hai trong ba số $a-1;b-1;c-1$ có cùng dấu. Gỉa sử $a-1;b-1$ cùng dấu thì ta có : $(a-1)(b-1)\ge 0$

Đây là đpcm. Đẳng thức xảy ra khi $a=b=c=1$.