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 các số không âm $a,b,c,d$ thỏa mãn $a+b+c+d=4$. Chứng minh rằng :

$$3(a^2+b^2+c^2+d^2)+4abcd\ge 16$$

Lời giải :

Cố định hai biến $c,d$, khi đó tổng $a+b$ cũng cố định. Lúc này vế trái được viết thành :

$$3\left[(a+b{)}^2-2ab\right]+3(c^2+d^2)+4abcd$$

là một hàm bậc nhất theo biến $ab$ nên sẽ đạt cực trị tại biên của biến. Mà $ab\in \left[0,\frac{(a+b{)}^2}{4}\right]$ nên vế trái đạt cực trị tại $ab=0$ hoặc $ab=(a+b{)}^2/4$. Tức là tại $a=b,a=0$ hoặc $b=0$.

Tương tự khi cố định hai biến $a,b$. Bài toán quy về hai trường hợp.

Nếu có một biến bằng $0$, giả sử $d=0$, cần chứng minh :

$$3(a^2+b^2+c^2)\ge 16$$

Điều này đúng theo Cauchy-Schwarz.

Nếu $a=b,c=d$ thì $a+c=2$ và cần chứng minh :

$$6(a^2+c^2)+4a^2{c}^2\ge 16\iff a^2{c}^2-3ac+2\ge 0$$

Điều này đúng với $ac\le (a+c{)}^2/2=1$

Bài toán : Cho các số không âm $a,b,c,d$ thỏa mãn $a+b+c+d=4$. Chứng minh :

$$(1+3a)(1+3b)(1+3c)(1+3d)\le 125+131abcd$$

Lời giải :

Cố định hai biến $c,d$ khi đó tổng $a+b$ cũng cố định. Lúc này hàm :

$$f(a,b,c,d)=(1+3a)(1+3b)(1+3c)(1+3d)-125-131abcd$$

là hàm bậc nhất theo biến $ab$ nên chỉ đạt cực trị tại biên của biến. Có $ab\in \left[0,\frac{(a+b{)}^2}{4}\right]$ nên $f$ đạt cực trị tại $ab=0$ hay $ab=(a+b{)}^2/4$. Tức $a=b,a=0$ hoặc $b=0$.

Tương tự khi ta cố định $a,b$. Bài toán quy về hai trường hợp.

Nếu có một biến bằng $0$, giả sử $d=0$ ta cần chứng minh :

$$(1+3a)(1+3b)(1+3c)\le 125$$

Đúng theo AM-GM :

$$(1+3a)(1+3b)(1+3c)\le {\left(\frac{3+3(a+b+c)}{3}\right)}^3=125$$

Nếu $a=b$ và $c=d$ thì $a+c=2$, cần chứng minh :

$$(1+3a{)}^2(1+3c{)}^2\le 125+131a^2{c}^2\iff 50a^2{c}^2-126ac+76\ge 0$$

Điều này đúng với $ac\le (a+c{)}^2/4=1$.

Bài toán hoàn tất.

Bài toán (International Mathematical Olympiad Shortlist 1993, Vietnam)

Cho bốn số không âm $a,b,c,d$ thỏa mãn $a+b+c+d=1$. Chứng minh rằng :

$$abc+bcd+cda+dab\le \frac{1}{27}+\frac{176}{27}abcd$$

Lời giải :

Ta cố định $c,d$. Khi đó tổng $a+b$ cũng cố định. Khi đó hàm số :

$$f(a,b,c,d)=\frac{176}{27}abcd+\frac{1}{27}-abc-bcd-cda-dab$$

là hàm bậc nhất theo biến $ab$, do đó nó chỉ đạt cực trị tại biên của biến. Vì $ab\in \left[0,\frac{(a+b{)}^2}{4}\right]$ nên cực trị của hàm đạt được tại $a=b$, $a=0$ hoặc $b=0$.

Lý luận tương tự với hai biến $c,d$. Bài toán quy về hai trường hợp.

Nếu có một biến bằng $0$, giả sử $a=0$ thì cần chứng minh :

$$bcd\le \frac{1}{27}$$

Điều này luôn đúng theo AM-GM :

$$bcd\le {\left(\frac{b+c+d}{3}\right)}^3=\frac{1}{27}$$

Nếu $a=b$ và $c=d$ thì có $a+c=\frac{1}{2}$ và cần chứng minh :

$ac(a+c)$$\le \frac{1}{54}+\frac{88}{27}{a}^2{c}^2$$\iff \frac{88}{27}{a}^2{c}^2-\frac{1}{2}ac+\frac{1}{54}$$\ge 0$$\iff ac$$\le \frac{1}{16}\vee ab$$\ge \frac{1}{11}$

Điều này là luôn đúng vì ta có :

$$ac\le \frac{(a+c{)}^2}{4}=\frac{1}{16}$$

Bài toán hoàn tất.

Bài toán : Cho các số không âm $a,b,c$ thỏa mãn không có hai số nào đồng thời bằng $0$. Chứng minh :

$\left(\frac{4a}{b+c}+1\right)\left(\frac{4b}{c+a}+1\right)\left(\frac{4c}{a+b}+1\right)$$\ge 25$

Lời giải 1 :

Ta đặt $x=\frac{2a}{b+c},y=\frac{2b}{c+a},z=\frac{2c}{a+b}$ thì ta được đẳng thức đẹp mắt :

$$xy+yz+zx+xyz=4$$

Và cần chứng minh :

$(2x+1)(2y+1)(2z+1)$$\ge 25$$\iff 8xyz+4(xy+yz+zx)+2(x+y+z)$$\ge 24$$\iff 4(xy+yz+zx+xyz)+4xyz+2(x+y+z)$$\ge 24$$\iff 2xyz+x+y+z$$\ge 4$

Với giả thiết $xy+yz+zx+xyz=4$, ta nghĩ ngay đến kết quả quen thuộc của kỳ thi VMO 1996 :

$$x+y+z\ge xy+yz+zx$$

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

$$2xyz+xy+yz+zx\ge 4\iff xyz\ge 0$$

Và điều này là luôn đúng. Bất đẳng thức đã cho được chứng minh, chú ý đẳng thức xảy ra khi $a=b,c=0$ hoặc các hoán vị.

Lời giải 2 :

Cố định $c$ và tổng $a+b$. Khi đó vế trái của BĐT viết dưới dạng :

$$\frac{(4a+b+c)(4b+c+a)(4c+a+b)}{(a+b)(b+c)(c+a)}=\frac{\alpha ab+\beta }{\gamma ab+\delta }$$

Trong đó $\alpha ,\beta ,\gamma ,\delta =const$. Như vậy vế trái là hàm đơn điệu theo biến $t=ab$, dễ thấy $t\in \left[0,\frac{(a+b{)}^2}{4}\right]$. Hàm đơn điệu thì luôn đạt cực trị tại biên nên vế trái sẽ đạt giá trị nhỏ nhất tại $t=0$ hoặc $t=(a+b{)}^2/4$.

Nếu $t=0$ thì $a=0$ hoặc $b=0$. Nếu $t=(a+b{)}^2/4$ thì $a=b$. Như vậy bài toán được chia thành hai trường hợp.

Nếu có một biến bằng $0$, giả sử $a=0$ thì ta cần chứng minh :

$$\left(\frac{4b}{c}+1\right)\left(\frac{4c}{b}+1\right)\ge 25$$

Dễ dàng thấy được điều này bằng Cauchy-Schwarz.

Nếu có hai biến bằng nhau, giả sử $a=b$. Do tính thuần nhất ta có thể giả sử $a=b=1$, cần chứng minh :

$${\left(\frac{4}{c+1}+1\right)}^2\left(2c+1\right)\ge 25\iff c(2c^2-4c+10)\ge 0$$

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

Bài toán hoàn tất.

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 (Đề 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_1{A}_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_i{A}_{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}{\sum ^8}{A}_i{A}_{i+1}{)}^2$$=\underset{i=1}{\sum ^8}{A}_i{A}_{i+1}^2+2\sum _{1\le i=j\le 8}{A}_i{A}_{i+1}.A_j{A}_{j+1}$

Ta có

$\underset{i=1}{\sum ^8}{A}_i{A}_{i+1}^2$$=\underset{i=1}{\sum ^8}\left((a_{i+1}-a_i{)}^2+(b_{i+1}-b_i{)}^2\right)$$=2\underset{i=1}{\sum _8}(a_i^2+b_i^2)-2\underset{i=1}{\sum ^8}(a_i{a}_{i+1}+b_i{b}_{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.