Giải bài 5

Gọi $S(n)$ là tích số thứ tự phòng của tất cả mọi người ngày thứ $n$

Như vậy ta có

$\frac{S(n+1)}{S(n)}=\frac{n(n+1)}{(n-1)(n+2)}=\frac{n^{2}+n}{n^{2}+n-2}< 1$

$\Rightarrow S(n+1)<S(n)$

Như vậy $S(n)$ là một đơn biến. Do $S(n)$ giảm và $S(n)>0$ nên việc chuyển phòng sẽ dừng sau một số ngày

 

------------------------------------------

Lời giải này chưa chặt chẽ vì có thể mẫu bằng $0$ hoặc âm thì chưa thể đánh giá được.

 

Bài 7 (bất đẳng thức tổ hợp)

Gọi $X=\left \{ 1,2,...,2003 \right \}$. Lấy số tự nhiên $n\geq 1$ và $n\leq 2003$ sao cho nếu lấy tập hợp con gồm $n$ phần tử của $X$, thì ta có thể tìm được một phần tử là lũy thừa của $2$ hoặc $2$ phần tử có tổng là lũy thừa của $2$. Chứng minh rằng: $n\geq 999$

Giải bài 7. Xét tập $A=\left \{ 5, 6, 7, 12, 13, 14, 15, 21, 22, 23, 24, 28, 29, 30, 31, 37, 38, 39, 44\right \}$ và $B=\left \{n|n \in \mathbb{N}, 1025 \le n \le 2003\right \}$.

Xét tập $C=A \cup B$. Dễ thấy $|C|=998$.

Các phần tử trong $B$ nằm giữa $2^{10}$ và $2^{11}$ nên không thể là luỹ thừa của $2$ và  $\forall x \neq y; x, y \in B$ thì $2^{11} < x+y < 2^{12}$ nên tổng $x+y$ cũng không thể là luỹ thừa của $2$.

Với $x \in A$ và $y \in B$ thì $1030 \le x+y \le 2047$ nên tổng $x+y$ cũng không là luỹ thừa của $2$.

Dễ kiểm tra các phần tử của $A$ không là luỹ thừa của $2$ và tổng của $2$ số bất kỳ trong số chúng cũng vậy.

$\Rightarrow \forall n \le 998$ ta chỉ cần lấy một tập con $n$ phần tử của $C$ thì tập này sẽ không có phần tử nào và cũng không có tổng của $2$ phần tử nào là luỹ thừa của $2$.

$\Rightarrow n \geq 999$.

 

Với bài này có lẽ ta phải chia bàn cờ ra 4 phần.
Cái đáp số hơi lằng nhằng, không biết có đúng không.

Đáp số của cả $2$ TH đều là $d \le 10\sqrt{2}$, dùng chung $1$ lập luận và chỉ hơi khác nhau cách đưa quân cờ thỏa mãn .

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

Topic này có nên thêm cả phần đồ thị vào không nhỉ?

Giải bài 1. Số giao điểm: Xét một tứ giác bất kỳ lập thành từ $4$ đỉnh của đa giác, do đa giác lồi nên giao điểm 2 đường chéo của tứ giác này nằm trong đa giác và cũng là giao điểm 2 đường chéo của đa giác.

Ngược lại với $1$ giao điểm của $2$ đường chéo bất kỳ trong đa giác thì $2$ cặp đầu mút của $2$ đường chéo này lập thành $1$ tứ giác có $4$ đỉnh là $4$ đỉnh phân biệt của đa giác. Tóm lại ta lập được song ánh giữa số giao điểm và số tứ giác tạo bởi $4$ đỉnh phân biệt của đa giác.

$\Rightarrow$ Số giao điểm là $C^4_n$.

Số miền: Ta xuất phát từ đầu với $1$ miền (chính là $n$-giác) và lần lượt nối các đường chéo. Mỗi đường chéo chia đa giác thêm $1$ phần, và mỗi khi nó giao với đường chéo khác nó lại chia đa gíc thêm $1$ phần nữa.

Dễ tính được số đường chéo là: $C^2_n-n$.

$\Rightarrow$ Số miền là: $1+C^2_n-n+C^4_n$.

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$

 

Đáp số của cả $2$ TH đều là $d \le 10\sqrt{2}$, dùng chung $1$ lập luận và chỉ hơi khác nhau cách đưa quân cờ thỏa mãn .

 

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.

ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.

iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.

Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:

$a) 2012 \times 2013?$

$b) 2012 \times 2014?$

 

 Để giải hoàn chỉnh và chặt chẽ bài này ra thì khá dài, thế nên mình chỉ post ý tưởng của câu b ra mọi người thực hiện tính toán nhé . (Còn câu a cách xây dựng thì hoàn toàn không khó   ).

Gợi ý câu 4b)  Giả sử tồn tại cách tô màu thoả mãn điều kiện. Xét các giao điểm của các đường thẳng vuông góc nhau bên trong bảng vuông là các điểm nguyên trên mặt phẳng toạ độ với toạ độ $(i,j) (1 \le i \le 2011, 1 \le j \le 2013)$. Gọi $x_{ịj}$ là số đoạn thẳng đơn vị (đoạn thẳng độ dài $1$) nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô cùng màu, $y_{ịj}$ là số đoạn thẳng đơn vị nằm trong hình vuông $4 \times 4$ có tâm là điểm $(i,j)$ mà ngăn cách giữa $2$ ô khác màu, $X$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô cùng màu, $Y$ là số đoạn thẳng đơn vị nằm trong bảng vuông $2012 \times 2014$ ngăn cách giữa $2$ ô khác màu. Ta tính $X-Y$ theo $2$ cách.

Để ý rằng $x_{ij}=y_{ij} \forall i,j$.

Đầu tiên ta tính $X-Y$ theo tổng $\sum_{i \equiv j (mod2)} (x_{ij}-y_{ij})$ sau đó theo tổng  $\sum_{i \not\equiv j (mod2)} (x_{ij}-y_{ij})$. Có vẻ ta thấy $2$ tổng này bằng nhau và bằng $0$ nhưng với mỗi cách đếm thì có một số cạnh chưa được tính (các cạnh này toàn nằm giữa các ô vuông đỏ trên biên nên dễ đếm thôi), và 2 cách đếm cho ta số cạnh chưa được tính khác nhau nên suy ra mâu thuẫn .

Nhưng $S(n)>0$  mà bạn, với lại $S(n)$ đúng hơn là số nguyên dương, làm sao mà âm được

VD nhé, nếu có ngày mà ở phòng $1$ và $2$ có người thì họ sẽ chuyển sang phòng $0$ và $3$, thì $S(n)$ lúc này bằng $0$ thì sao thực hiện phép chia xuống mẫu được .

 

 

 

Bài 4 (Tô màu - Nguồn: Đề thi HSG lớp 10 THPT chuyên KHTN). Cho một bảng ô vuông kích thước $m \times n$. Người ta muốn tô màu các ô vuông con của bảng, mỗi ô vuông con chỉ được tô bởi 1 trong 2 màu Xanh hoặc Đỏ theo quy tắc sau:

i) Tất cả các ô vuông con ở cạnh của bảng đều được tô màu Đỏ.

ii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà $4$ ô vuông con được tô cùng màu.

iii) Không có hình vuông kích thước $2 \times 2$ nào của bảng mà hai ô ở mỗi đường chéo đều được tô cùng màu.

Hỏi người ta có thể thực hiện cách tô màu như trên trong các trường hợp với bảng ô vuông kích thước:

$a) 2012 \times 2013?$

$b) 2012 \times 2014?$

 

 

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$

Bài 9: (tập hợp,Germany 1970) Cho tập $M$ có $22222$ phần tử .Hỏi $M$ có hay không 50 tập con thoả mãn :

 1/Mỗi phần tử của $M$ là phần tử của ít nhất 1 trong các tập con.

 2/Mỗi tập con đều có $1111$ phần tử.

 3/Với 2 tập $M_i;M_j (i \neq j)$ có ${M_i} \cap {M_j}$ 22 phần tử.

Giải bài 9. Gọi các phần tử của $M$ là $a_1 \rightarrow a_{22222}$. Giả sử tồn tại $50$ tập con $M_i (1 \le i \le 50)$ thoả mãn $3$ yêu cầu trên. Ta đếm số cách chọn $2$ tập $M_i, M_j (i \neq j)$ kèm theo $1$ phần tử $a_k$ thuộc $M_i \cap M_j$. Gọi số cách chọn này là $S$.

Có $C^2_{50}$ cách chọn $2$ tập $M_i, M_j (i \neq j)$ và $22$ cách chọn phần tử $a_k$ thuộc $M_i \cap M_j$.

$\Rightarrow S=22.C^2_{50}=26950$.

Mặt khác, giả sử $a_i$ thuộc $r_i ( \forall 1 \le i \le 22222)$ tập $M_j$. Khi đó dễ CM được $$\sum_{i=1}^{22222}r_i= \sum_{i=1}^{50} |M_i|=50.1111=55550$$.

Có $22222$ cách chọn phần tử $a_i$ bất kỳ, và có $C^2_{r_i}$ cách chọn 2 tập $M_j, M_k$ sao cho $a_i \in M_j \cap M_k$ (coi $C^2_1=0$).

$\Rightarrow S=\sum_{i=1}^{22222} C^2_{r_i}$

$=\sum_{i=1}^{22222} \frac{r_i(r_i-1)}{2}$

$=\frac{1}{2}(\sum_{i=1}^{22222}r_i^2 - \sum_{i=1}^{22222}r_i)$

$\geq \frac{1}{2} (\frac{(\sum_{i=1}^{22222} r_i)^2}{22222}-\sum_{i=1}^{22222} r_i)$ (BĐT C-S)

$=\frac{55550^2-22222.55550}{2.22222}>26950=S$ (mâu thuẫn).

Vậy không tồn tại $50$ tập con của $M$ thoả mãn đề bài.

Bài 12: (Bất biến) Trong một ngày chủ nhật mỗi học sinh trong bảy học sinh có ba lần đi đến hiệu sách. Biết rằng hai học sinh bất kì trong số đó có gặp nhau tại hiệu sách. Chứng minh rằng có mội thời điểm mà trong hiệu sách có mặt cùng lúc 3 học sinh. (trong 7 học sinh nói trên)

Giải bài 12. Gọi $7$ bạn học sinh này là $X_1 \rightarrow X_7$, xét $3$ thời điểm $A_1, A_2, A_3$ mà học sinh $X_1$ đi đến hiệu sách. Do cả $6$ học sinh khác đều có gặp $X_1$ nên mỗi người trong số họ phải đến hiệu sách vào ít nhất $1$ trong $3$ thời điểm kể trên, theo nguyên lý Dirichlet thì tồn tại $2$ học sinh $X_i$ và $X_j (2 \le i,j \le 7, i \neq j)$ đến vào cùng $1$ thời điểm $A_i$. Do đó $3$ học sinh $X_i, X_j, X_1$ cùng có mặt tại hiệu sách cùng $1$ thời điểm nên ta có đpcm.

Có vẻ bài trên chỉ cần $5$ học sinh là đủ nhỉ?

Mình cũng hơi kém phần tổ hợp rời rạc này, nên cũng muốn được học tập trao đổi kinh nghiệm. Mình xin đưa ra một bài nho nhỏ:

Bài 8: (phương pháp tự do, không câu nệ cách giải) Trên một sân chơi có 10 em bé đứng. Biết rằng khoảng cách giữa các em bé đôi một khác nhau và mỗi em bé cầm trong tay một quả bóng (quả bóng là một trong bốn màu đỏ, vàng, lam, lục). Sau hiệu lệnh của chị phụ trách, mỗi em đưa quả bóng của mình cho bạn đứng gần nhất. Hỏi rằng có ít nhất bao nhiêu em bé còn có bóng trong tay?

4 màu để làm gì nhỉ?  .

Giải bài 8. Ta CM còn ít nhất 2 em bé có bóng. Gọi vị trí 10 em bé đứng lần lượt là $A_1 \rightarrow A_{10}$

Giả sử tồn tại cách đứng sao cho sau khi chuyển bóng thì còn đúng 1 em bé có bóng. Giả sử chỉ có em $A_1$ còn bóng.

Xét các góc $\angle A_jA_1A_i (\forall 2 \le i, j \le 10, i \neq j)$, theo nguyên lý Dirichlet tồn tại 1 góc nhỏ hơn $60^o$, WLOG giả sử là $\angle A_2A_1A_3 < 60^o$. Khi đó tồn tại một trong 2 góc $\angle A_1A_2A_3$ hoặc $\angle A_2A_3A_1$ lớn hơn $60^o$ và lớn hơn $\angle A_2A_1A_3$. Giả sử $\angle A_2A_1A_3< \angle A_1A_2A_3$, khi đó $A_2A_3<A_1A_3$ do vậy $A_3$ sẽ đưa bóng cho $A_2$ chứ không phải $A_1$ (mâu thuẫn).

Vậy có ít nhất 2 em còn cầm bóng.

Cấu hình sau đảm bảo có đúng 2 em cầm bóng là $A_1$ và $A_6$.

 

Bài 3 (Toán trò chơi-Nguồn: Tournament of the Towns). Trên bảng ô vuông $20$x$20$ mỗi ô có $1$ quân cờ. $A$ chọn một số thực $d$ và $B$ phải đưa mỗi quân cờ đi tới ô cách ô ban đầu nó đứng một khoảng cách ít nhất là $d$ (khoảng cách giữa $2$ ô được tính theo khoảng cách tâm của $2$ ô đó) và mỗi ô chỉ có thể có $1$ quân cờ. Hỏi với điều kiện gì của $d$ thì $B$ có thể thao tác thoả mãn điều kiện trên?

Hỏi tương tự với bảng $21$x$21$

Bài này chỉ dùng duy nhất $1$ nhận xét, tiếc là chưa ai giải.

Giải bài 3. $*$ TH bảng $20 \times 20$:

Xét toạ độ các ô (được tính ở tâm ô) là $(i, j) \forall 1 \le i, j \le 20$. Xét ô $(10, 10)$, giả sử sau bước chuyển quân cờ ở ô này chuyển đến ô $(a,b) (1 \le a,b \le 20, a, b$ không đồng thời bằng $10)$, khi đó khoảng cách giữa $2$ ô là: $\sqrt{(a-10)^2+(b-10)^2} \ge d$.

Do $1 \le a,b \le 20$ nên $|a-10| \le 10, |b-10| \le 10 \Rightarrow d \le 10\sqrt{2}$.

Cách chuyển quân: Các quân ở các ô $(i, j)$ đến ô $(i', j')$ với $\begin{cases} i'=i+10 & \text{ if } i \le 10\\ i'=i-10 & \text{ if } i > 10 \end{cases}$.

$*$ TH bảng $21 \times 21$: Lập luận tương tự với ô $(11,11)$, cách xây dựng mọi người tự tìm nhé .

Sao lại sửa đề vậy mấy bạn ! Đề đúng là (m,n,k) = 1.

Đúng là nếu (m, n, k)=1 thì sẽ cần thêm bước sau để bài toán chặt chẽ hơn: Giả sử tồn tại $p$ nguyên tố và $p|m, p|n$, khi đó do $p|k^2$ và $p$ nguyên tố nên $p|k$ suy ra $(m,n,k) \ge p >1$(mâu thuẫn) nên $(m,n)=1$ .

Bài 16 Cho $n$ là số nguyên dương. Kí hiệu $\pi (n)$ là số các số nguyên tố không vượt quá $n$. Chứng minh rằng:

$\pi (n)\leq \frac{n}{2}-1$ với mọi $n\geq 14$

Giải bài 16. Ta CM quy nạp theo $n$: $\pi (n)\leq \frac{n}{2}-1$ với mọi $n\geq 14 (*)$

• $(*)$ đúng với $n=14, 15$.
• Giả sử (*) đúng với $n \ge 15$, ta Cm nó đúng với $n+2$.

Thật vậy, trong 2 số $n+1$ và $n+2$ luôn có $1$ số chẵn, số này $\ge 15$ nên không thể là số nguyên tố.

$\Rightarrow \pi (n+2)\leq \pi(n)+1 \le \frac{n}{2}-1+1 = \frac{n+2}{2}-1$

Vậy ta có $(*)$ đúng với $n+2$ và ta có đpcm.

Hehe vừa về Thái Bình, đoàn 2 bạc 1 vàng, tiếc quá 0,5 nữa là vàng r`, chỉ tại viết nhầm số 3 thành 2, trừ mất 0,5 @@~

Bài 2 : WLOG, giả sử $x\geq y$

$\bullet$ Nếu $z\geq 1$ suy ra $2xyz\geq 2xy$ suy ra $P\geq (x+y)^2+2z^2\geq \frac{(x+y+z)^2}{2}+z^2\geq \frac{11}{2}$

 

$\bullet$ Nếu $z\leq 1$ suy ra $2x\geq x+y\geq 2$ vậy nên $2xyz\geq 2yz$, ta có :

$$P\geq x^2+(y+z)^2+z^2\geq \frac{(x+y+z)^2}{2}+z^2\geq \frac{9}{2}$$ ( Do $z^2\geq 0$ )

Vậy $\text{min P}=\frac{9}{2}$, đẳng thức xảy ra khi $x=y=\frac{3}{2},z=0$

Mình thiếu 0.25 nữa thì được vàng nè .

Bài tổ hợp chưa làm bao giờ nhưng không ngờ hôm thi mình giải đúng như đáp án, sướng phết :

Giả sử tồn tại cách viết số thoả mãn, giả sử các SCP được viết ở cột i.

Từ điều kiện 1 ta thấy tồn tại một đường đi qua các số tự nhiên liên tiếp từ 1 đến 169. Mỗi lần đi từ ô $a^2$ đến ô $(a+1)^2$ thì đường đi phải đi qua $2a$ ô không kể 2 ô này và đường đi này đi qua hết các ô trên bảng.

Gọi phần bên trái cột i là phần A, phần bên phải cột i là phần B, dễ thấy tổng số ô mỗi phần này chia hết cho 13 (Có thể bằng 0).

Không mất tổng quát giả sử tư ô số 1 đường đi đi sang phần A, nó cần phải đi $2.1=2$ ô để sang ô 4, 2 ô này nằm hoàn toàn bên phần A vì đường đi không đi qua cột i trước khi gặp ô số 4, rồi sau đó nó đi sang phần B. Lý luân tương tự ta có với $c=\bar{0,5}$ thì từ ô $(2c+1)^2$ đến ô $(2c+2)^2$ đường đi đi qua $2(2c+1)$ ô ở phần A rồi qua cột i sang phần B, còn từ ô $(2c+2)^2$ đến ô $(2c+3)^2$ nó đi $2(2c+2)$ ô ở phần B rồi qua cột i rồi sang phần A.

Do đường đi đi qua hết các ô trên bản nên tổng số ô ở phần A là: $\sum_{c=0}^{5}2(2c+1)=72$ không chia hết cho 13 nên mâu thuẫn. Vậy không tồn tại cách điền số thoả mãn .

Bài 1 ngày 1. Gọi Sultan là S cho dễ  . Giả sử số ban đầu là $a$.

Bước 1. S chọn $2$, nếu chưa được thì ta có số $a-2$ lẻ.

Bước 2. S chọn $3$, nếu chưa được thì ta có số $a-5$ chẵn và chia $3$ dư $b (b=1$ hoặc $2)$.

Bước 3. S chọn $5$, nếu chưa được thì ta có số $a-10$ lẻ và chia $3$ dư $b-2$.

Bước 4. S chọn $9$, nếu chưa được thì ta có số $a-19$ chẵn và chia $3$ dư $b-2$.

Bước 5. S chọn $6$, nếu chưa được tức là $b \neq 2$ hay $b=1$, bây giờ ta có số $a-25$ chẵn và chia $3$ dư $2$.

Bước 6. S chọn $4$ nếu chưa được tức là $a-25 \equiv 2 (mod4)$ và bây giờ ta có số $a-29$ chia $3$ dư $1$ và chia $4$ dư $2$.

Bước 7. S chọn $10$, nếu chưa được thì ta còn số $a-35$ chia hết cả $3$ và $4$.

Bước 8. S chọn $12$ và chiến thắng.

Cách làm khác: Tô đen các ô của bảng như hình vẽ, khi đó mỗi quân domino 1x4 phủ 1 và chỉ 1 ô bị tô màu, mà có 26 ô bị tô màu nên sẽ không thể phủ hết bàn cờ bằng 25 domino 1x4  

Bài này có thể làm tính toán hơn như sau:

Ta có 2 kết quả quen thuộc:

• $AH=acotA$
• $cotA=\frac{b^2+c^2-a^2}{4S}$

Áp dụng 2 kết quả và giả thiết ta có: $a(b^2+c^2-a^2)=4RS=abc$ suy ra $b^2+c^2-bc=a^2$ từ đây áp dụng định lý cos ta có $cosA=\frac{1}{2}$ hay $\widehat{A}=60^o$.

Cả 2 lời giải đều thiếu 1 TH là $\angle BAC=120^o$ vẫn thỏa đề.

Đúng rồi với TH $\bigtriangleup ABC$ tù tại $A$ thì $AH=-acotA$

Làm luôn câu 3 cho hết ngày 1

Câu 3. Đề bài chỉ ra khá rõ hướng làm là định lý Ramsey trong đồ thị, ta đưa về CM: Trong đồ thị đầy đủ $G=(V;E), |V|=C^n_{2n}$ được tô màu cạnh bằng 2 màu thì tồn tại đồ thị con đầy đủ $n+1$ cạnh cùng màu, tức là CM: $R(n+1, n+1) \leq C^n_{2n}$.

Trước tiên ta CM 2 bổ đề:

Bổ đề 1: $\forall s, t>2$ thì: $R(s,t) \leq R(s-1, t)+R(s, t-1)$.

CM: Đặt $N=R(s-1, t)+R(s, t-1)$, xét 1 cách tô màu xanh đỏ các cạnh của một đồ thị $K_N$ ($K_N$ ký hiệu đồ thị đầy đủ $N$ đỉnh). Gọi $A$ là một đỉnh bất kỳ. Trong $N-1$ cạnh kề A có không ít hơn $R(s-1, t)$ cạnh màu xanh hoặc $R(s, t-1)$ cạnh màu đỏ. WLOG giả sử có $R(s-1, t)$ cạnh màu xanh kề $A$. Các đầu mút khác $A$ của các cạnh này sẽ tạo thành $1$ đồ thị đầy đủ $R(s-1, t)$ đỉnh. Theo định lý Ramsey đồ thị này chứa một đồ thị con $K_{s-1}$ cạnh màu xanh hoặc $K_t$ cạnh màu đỏ. Trong TH đầu tiên, lấy thêm $A$ ta có đồ thị con $K_s$ với các cạnh màu xanh còn với TH2 ta có ngay đồ thị $K_t$ cạnh đỏ, từ đó ta có đpcm.

Bổ đề 2: $\forall s, t \geq 2, R(s,t) \leq C^{s-1}_{s+t-2}$.

CM: Bổ đề này dễ dàng CM được bằng quy nạp kết hợp bổ đề 1: $$R(s,t) \leq R(s-1,t)+R(s,t-1) \leq C^{s-2}_{s+t-3}+C^{s-1}_{s+t-3}=C^{s-1}_{s+t-2}$$ (đẳng thức Pascal).

Trở lại bài toán, áp dụng bổ đề 2 ta có $R(n+1, n+1) \leq C^{n+1-1}_{n+1+n+1-2}=C^n_{2n}$ (đpcm)

bài này lập phương trình đặc trưng của dãy rồi tìm được công thức tổng quát thôi mà!

Bạn up lời giải lên đi, coi như 1 cách làm khác .

Chém luôn câu số cho nó nóng :
Câu 4. Dễ thấy rằng $p, q \neq 2, 3, 5$ và $p \neq q \Rightarrow \exists$ 1 số $\geq 11$ và 1 số $\geq 7$.

Ta có $pq|(30p-1)(30q-1) \Rightarrow pq|30(p+q)-1$. Đặt $30(p+q)-1=kpq (*) (k \in \mathbb{N^*})$

$\Rightarrow 30(\frac{1}{p}+\frac{1}{q})-\frac{1}{pq}=k$

$\Rightarrow k \leq 30(\frac{1}{7}+\frac{1}{11}) $

$\Rightarrow k \leq 7$.

Lại từ $(*)$ ta phân tích thành $(kp-30)(kq-30)=900-k$.

Nhận xét: Nếu $2|k$ thì $4|VT \Rightarrow 4|VP$

$\Rightarrow 4|k$

$\Rightarrow k=4$

$\Rightarrow (2p-15)(2q-15)=224$ nên không tồn tại $p, q$ thoả mãn.

Vậy k lẻ.

• Nếu $k=3$ thì $9|VT \Rightarrow 9|VP \Rightarrow 9|897$ (vô lý).
• Nếu $k=5$ thì $25|VT \Rightarrow 25|VP \Rightarrow 25|895$ (vô lý).
• $k=1$, thay vào giải trực tiếp ta được $(p;q)=(59; 61); (61; 59); (929; 31); (31;929)$
• $k=7$, giải được $(p;q)=(11;7); (7;11)$.

KL: Có 6 bộ $(p;q)$ thoả mãn là $(59;61); (61;59)$ và $(7; 11); (11;7)$ và $(929; 31); (31;929)$

Chém câu dãy số :

Câu 2. Lập dãy phụ $(b_n): b_0=b_1=1; b_{n+1}=4b_n-b_{n-1}$, Ta CMR quy nạp rằng $a_n=(b_n)^2 \forall n (*)$.

$(*)$ đúng với $n=0; n=1$, giả sử $(*)$ đúng $\forall 0 \leq k \leq n$. Ta CMR: $a_{n+1}=(b_{n+1})^2   (1)$.

Trước tiên ta viết lại dãy $(b_n)$ dưới dạng: $b_{n+1}=\frac{b_n^2-2}{b_{n-1}} \Rightarrow b_{n+1}b_{n-1}-b_n^2=2  (2)$.

Theo công thức xác định dãy $(a_n)$ ta có: $a_{n+1}=14b_n^2-b_{n-1}^2-4$.

Do đó $(1) \Leftrightarrow (4b_n-b_{n-1})^2=14b_n^2-b_{n-1}^2-4 \Leftrightarrow b_{n+1}b_{n-1}-b_n^2=2$ (đúng theo $(2)$).

Vậy mệnh đề $(*)$ đúng $\forall n$ và ta có đpcm.

Do $x^2+x$ và $x^3\in \mathbb{Q}$ nên $\frac{x^2+x}{x^3}\in \mathbb{Q}$ hay $\frac{1}{x^2}+\frac{1}{x}\in \mathbb{Q}$. Do đó $(x^2+x)(\frac{1}{x^2}+\frac{1}{x})\in \mathbb{Q}$ hay $x+\frac{1}{x} \in \mathbb{Q}$ suy ra $x^3(x+\frac{1}{x}) \in \mathbb{Q}$ hay $x^4+x^2\in \mathbb{Q} \Rightarrow (x^4+x^2)-(x^2+x) \in \mathbb{Q} \Rightarrow x^3(x-1) \in \mathbb{Q}$ mà $x^3\in \mathbb{Q}$ nên $x\in \mathbb{Q}$  Q.E.D

P/s: Quên mất $x=0$ 

Đây là 1 bài trong đề thi China 1995 

Nam là người chiến thắng với chiến thuật sau: Đầu tiên vào mỗi lượt đi Nam điền vào tất cả các hệ số bậc chẵn (nếu còn), vì chỉ có $n-1$ hệ số bậc chẵn nên sau khi điền $2n-3$ hệ số và đến lượt Nam thì luôn còn $1$ só hạng bậc lẻ chưa được điền hệ số.

Đặt đa thức nhận được lúc này là: $P(x)=Q(x)+x^s+x^{2t-1}$ với $s, t \in \mathbb{N^*}$ và $Q(x)$ là đa thức nhận được từ các hạng tử đã được điền hệ số.

Ta tìm số $a$ để Nam điền vào hệ số bậc $s$ sao cho với mọi số thực b mà Bình điền vào bậc $2t-1$ thì đa thức luôn có nghiệm.

Ta có: $$\frac{1}{2^{2t-1}}P(2)+P(-1)=[\frac{1}{2^{2t-1}}Q(2)+Q(-1)]+a[2^{s-2t+1}+(-1)^s].$$

Do $s\neq 2t-1$ nên $2^{s-2t+1}+(-1)^s \neq 0$, ta chọn $$a=- \frac{\frac{1}{2^{2t-1}}Q(2)+Q(-1)}{2^{s-2t+1}+(-1)^s}$$

Rõ ràng $a$ không phụ thuộc $b$ và lúc này $\frac{1}{2^{2t-1}}P(2)+P(-1)=0$ nên $P(x)$ tồn tại nghiệm thuộc $[-1;2]$ Q.E.D.

Nhận xét: Có thể thay $2$ bằng một số $a$ bất kỳ chỉ cần $a \neq 1$ và $a \neq -1$ để $a^{s-2t+1}+(-1)^s \neq 0$ là được

Tính vài giá trị đầu: $x_1=1, x_2=-1, x_3=\frac{3}{4}, x_4=\frac{5}{16}, x_5=\frac{-71}{256}, x_6=\frac{-5199}{65536}.$
Ta CMR: $\forall n \geq 4: |x_n| < \frac{1}{n-1} (*)$, từ đó suy ra $\lim_{n \to +\infty }x_n=0$

• Ta thấy $(*)$ đúng với $n=4, n=5, n=6$.
• Giả sử $(*)$ đúng $\forall 4 \leq k \leq n+1$.
• Xét $k=n+2 (n \geq 5)$. Ta có:

$x_{n+2}=x_{n+1}^2-\frac{1}{2}x_n \Rightarrow |x_{n+2}| < x_{n+1}^2+\frac{1}{2}|x_n| < \frac{1}{n^2}+\frac{1}{2(n-1)}$.

Ta chỉ cần CMR: $\frac{1}{n^2}+\frac{1}{2(n-1)} < \frac{1}{n+1}$, khai triển ta có BĐT tương đương $n^3-5n^2+2 > 0 (1)$ mà do $n \geq 5$ nên BĐT $(1)$ đúng.

Vậy $(*)$ đúng $\forall n \geq 4$.

KL: $\lim_{n \to +\infty }x_n=0$.

Mình post luôn bài toán khiến mình nghĩ ra kết quả trên :
Cho $\bigtriangleup ABC$, đuờng thẳng qua $A$ song song với đường thẳng Euler của $\bigtriangleup ABC$ cắt $BC$ tại $E$. CMR: Đường thẳng Euler của $\bigtriangleup ACE$ song song với $AB$.

Cho $\bigtriangleup ABC$ với 3 đường cao $AD, BE, CF$. $DE \cap AB \equiv C^{'}, DF \cap AC \equiv B^{'}. H$ là trực tâm tam giác $AB^{'}C^{'}$. CMR: $AD$ là đường thẳng Euler của tam giác $HB^{'}C^{'}$.

Nguồn: Tự chế, không biết có đụng hàng với ai không 

Đây là phương trình Ramanujan-Nagell, lời giải của nó khá kinh khủng, có thể xem ở trang 50-51 ở file sau