dauga

Bài 1:

Từ các điều kiện của bài toán dễ dàng đoán ngay giới hạn của dãy là $1$. Từ đó ý tưởng là đặt dãy $y_n = x_n - 1$. Ta cần chứng minh dãy này có giới hạn là $0$ và với mọi $n\ge 0$ thì  $0\le y_1 + y_2 + \cdots + y_n \le 1$.

Ta có $x_{n+1} - 1 = \sqrt{x_n + 8} - 3 - (\sqrt{x_n + 3} - 2) = \frac{x_n-1}{\sqrt{x_n+8} + 3} - \frac{x_n-1}{\sqrt{x_n+3} + 2}$

nên công thức truy hồi của $y_n$ là $y_1 = 1$ và $y_{n+1} = y_n\left(\frac{1}{\sqrt{y_n + 9} + 3} - \frac{1}{\sqrt{y_n+4}+2}\right)$ với mọi $n\ge 1$.

Dễ thấy $\left|\frac{1}{\sqrt{y_n + 9} + 3} - \frac{1}{\sqrt{y_n+4}+2}\right| \le \frac{1}{2}$. Nên ta có $|y_{n+1}| \le \frac{1}{2}|y_n|$ với mọi $n\ge 1$. Do đó dãy $|y_n|$ có giới hạn là $0$. Hệ quả là giới hạn của $x_n$ là $1$ $\square$

Từ $\frac{1}{\sqrt{y_n + 9} + 3} - \frac{1}{\sqrt{y_n+4}+2} < 0$  trên thì ta có $y_n$ luôn phiên đổi dấu. Mà $y_1 = 1 > 0$ nên $y_k \ge 0$ với $k$ lẻ và $y_k \le 0$ với $k$ chẵn. Lại có $|y_{k+1}| \le |y_k|$ nên ta có $y_{2t+1}\le -y_{2t} \le y_{2t-1}$ với mọi $t\ge 1$. Hay $y_{2t} + y_{2t-1} \ge 0$ và $y_{2t} + y_{2t+1}\le 0$ với mọi $t \ge 1$.

Dó với mọi $k$ thì $y_1 + y_2 + \cdots + y_{2k} = (y_1 + y_2) +
\cdots + (y_{2k-1} + y_{2k}) \ge 0$. Vì $y_{2k+1} \ge 0$ nên cũng phải có $y_1 + y_2 + \cdots + y_{2k+1} \ge 0$.

Tương tự $y_1 + y_2 + \cdots + y_{2k-1} = y_1 + (y_2+y_3) + \cdots + (y_{2k-2} + y_{2k-1}) + y_{2k} \le 1$. Vì $y_{2k} \le 0$ nên cũng phải có $y_1 + y_2 + \cdots + y_{2k} \le 1$

$\blacksquare$

Bài 5.

a. Dễ thấy vai trò của $1, 2, 3$ là như nhau nên có thể giả sử $x_1 = 1$, $x_2 = 2$. Xét hai trường hợp, $x_3 = 1$ và $x_3 = 3$.

Nếu $x_3 = 1$ thì từ điều kiện 2. ta có $x_4, x_5$ đều khác 2. Mà $x_4$ phải khác 1 nên $x_4 = 3$. Do đó $x_5 = 1$. Dãy $1,2,1,3,1$ thỏa mãn cả hai điều kiện.

Nếu $x_3 = 3$ thì $x_4 = 1$ hoặc $2$. Nếu $x_4 = 1$ thì $x_5$ không thể là $1$ (điều kiện 1), hay $2$ và $3$ (điều kiện 2). Do đó $x_4 = 2$, khi đó dễ thấy chỉ còn có $x_5 = 1$. Ta thu được dãy $1,2,3,2,1$.

Vậy tổng cộng sẽ có $S_3(5) = 3!\times 2 = 12$ dãy thỏa mãn.

b. Ta chứng minh bằng quy nạp với mỗi $n$ thì  mọi dãy có độ dài $2n$ bất kì đều không thỏa mãn ít nhất một trong các điều kiện của bài toán bằng quy nạp.

Thật vậy với $n=1$ thì dãy có độ dài $2$ sẽ phạm vào điều kiện 1. Giả sử đã đúng tới $n-1\ge 1$. Xét với $n$. Giả sử tồn tại dãy $x_1,...,x_{2n}$ thỏa mãn các điều kiện đề bài. Nếu có số $a$ chỉ xuất hiện $1$ lần trong dãy, thì khi bỏ phần tử $a$ đi, thì ta có dãy mới gồm $2n-1$ phần tử và vẫn thỏa mãn điều kiện. Nhưng điều này mâu thuẫn với giải thiết quy nạp. Vậy mỗi số nếu xuất hiện trong dãy thì sẽ xuất hiện 2 lân. Do đó mỗi $1\le i\le n$ sẽ có hai chỉ số $t_i < l_i$ mà $x_{t_i} = x_{l_i} = i$. Không mất tính tổng quát, giả sử $t_1 < t_2 < \cdots < t_n$ thì theo điều kiện 2, phải có $l_1 > l_2 > \cdots > l_n > t_n$. Nhưng khi đó thì sẽ phải có $t_n = n$, $l_n = n+1$ và điều này mâu thuẫn với điều kiện 1. Vậy không có dãy nào có độ dài $2n$ nào thỏa mãn cả hai điều kiện. ĐPCM.

Với $d=2n-1$ thì dễ thấy dãy $1,2,...,n-1,n,n-1,..,1$ thỏa mãn. Và hiển nhiên nếu dãy độ dài $d$ thỏa mãn thì chỉ cần bỏ đi một phần tử bất kì, ta thu được dãy có độ dài $d-1$ thỏa mãn. Câu b. được chứng minh hoàn toàn.

Bài 6:

Gọi dãy Fibonacci như sau: $F_{-2} = 1, F_{-1} = 0, F_0 = 1, F_1 = 1$ và $F_{n+1} = F_{n} + F_{n-1}$ với mọi $n \ge 0$.


Ta gọi một dãy $x_n$ có tính "Fibo" nếu nó thỏa mãn hệ thức truy hồi $a_{n+1} = a_{n} + a_{n-1}$ với mọi $n\ge 1$.

Bổ đề 1: Ta có tính chất sau cho dãy "Fibo":

$a_{m} = F_{k}a_{m-k} + F_{k-1}a_{m-k-1}$.

Chứng minh:

Thật vậy $a_{m} = a_{m-1} + a_{m-2} = F_1a_{m-1} + F_{0}a_{m-2}$. Nên điều trên đúng với $k=1$. Giả sử đã đúng tới $k$. Tức $a_{m} = F_{k}a_{m-k} + F_{k-1}a_{m-k-1}$, thì có

$a_{m} = F_{k}(a_{m-k-1} + a_{m-k-2}) + F_{k-1}a_{m-k-1}$

$ = (F_{k} + F_{k-1})a_{m-k-1} + F_{k}a_{m-k-2}$

$= F_{k+1}a_{m-k-1} + F_{k}a_{m-k-2}$ $\square$.

Ta có $x_0 = 2 = F_{0} + F_{-2}$, $x_1 = 1 = F_{1} + F_{-1}$, nên dễ thấy $x_{n} = F_{n} + F_{n-2}$.

Bổ đề 2:
Với mọi $n\ge 2$ thì $x_{n} | F_{2n-1}$ và $\text{gcd}(x_n, F_{2n}) = 1$.

Chứng minh:
Ta có dãy Fibonacci có tính chất "Fibo" nên theo bổ đề 1 ta có

$F_{2n-1} = F_{n}F_{n-1} + F_{n-1}F_{n-2} = (F_{n} + F_{n-2})F_{n-1} = x_nF_{n-1}$, do đó $a_{n} | F_{2n-1}$ với mọi $n$.

Lại dễ thấy $\text{gcd}(F_{k},F_{k-1}) = \text{gcd}(F_{k-1},F_{k-2}) = ...=\text{gcd}(F_{1}, F{0}) = 1$ với mọi $k\ge 0$ nên hệ quả là $\text{gcd}(F_{2n}, F_{2n-1}) = 1$. Mà $x_n |  F_{2n-1}$ và với $n\ge 2$ thì $x_{n} \ge 2$ nên phải có $\text{gcd}(x_n, F_{2n}) = 1$ $\square$

Xét số $m \neq 2$. Dãy $x_k$ tăng ngặt với $k\ge 2$ nên $x_k < x_{m}$ với mọi $0\le k < m$. Do đó $x_n$ không chia hết cho $x_m$ với mọi $ m < n$.

Với $m < n \le 2m$ thì theo bổ đề 1 ta có

$x_{n} = F_{n-m}x_{m} + F_{n-m-1}x_{m-1}$, có $\text{gcd}(x_m, x_{m-1}) = 1$ nên ta có nếu $x_m$ chia hết cho $x_m$ thì phải có $F_{n-m-1}$ chia hết cho $x_m$. Tuy nhiên $0 < F_{n-m-1} \le F_{n-1} < x_{n}$ nên điều này không xảy ra. Vậy $x_n$ không chia hết cho $x_m$ với mọi $m < n \le 2m$.

Xét với $n > 2m$ ta có

$x_{n} = F_{2m}x_{n-2m} + F_{2m-1}x_{n-2m-1}$

Theo bổ đề 2 thì $F_{2m-1}$ chia hết cho $x_m$ và $\text{gcd}(F_{2m}, x_m) = 1$ nên $x_n$ chia hết cho $x_m$ khi và chỉ khi $x_{n-2m}$ chia hết cho $x_m$. Đặt $n = 2mt + r$ với $0\le r < 2m$ thì dễ dàng có $x_n$ chia hết cho $x_m$ khi và chỉ khi $x_r$ chia hết cho $x_m$. Điều này chỉ xảy ra khi và chỉ khi $r = m$ hay $n = (2t+1)m$.

Vậy với mọi $m\ge 2$ thì $x_n$ chia hết cho $x_m$ khi và chỉ khi $n = (2t+1)m$.

Xét $m=1$ thì $x_m = 1$ nên $x_n$ chia hết cho $x_m$ với mọi $n$.

Xét $m=0$ thì khi xét module $2$ thì dễ tuần với với chu kì là $3$ là $0, 1, 1$. Do đó $x_n$ chia hết cho $x_0$ khi và chỉ khi $n = 3t$.

Vậy đáp số của câu b. là $(m, n) = (1, t)$ hoặc $(0, 3t)$ hoặc $(a, (2t+1)a)$ với mọi $t, a$$\square$

Trở lại câu a. Giả sử $n$ là hợp số và có ước nguyên tố lẻ $p$. Theo trên ta có $x_n$ chia hết cho $x_{n/p}$  và $x_n > x_{n/p}$ nên $x_n$ không thể là số nguyên tố. Do đó nếu $x_n$ là số nguyên tố thì $n$ là số nguyên tố hoặc $n$ không có ước nguyên tố lẻ $\square$.