Chứng minh tồn tại số tự nhiên thỏa mãn yêu cầu bài toán

Bài toán:

Cho trước $ k\in \mathbb{Z}^+$ và $ m$ lẻ .

Chứng minh rằng tồn tại $ n\in \mathbb{Z}^+$ sao cho $ 2^k| n^n-m$

Lời giải:

Ta sẽ chứng minh quy nạp theo $ k$.

Trường hợp $ k=1$ là hiển nhiên, chọn $ n=1$.

Giả sử rằng tồn tại $ n$ sao cho $ 2^k|n^n-m$,Đặt $ n=n_0$ hay $ 2^k|n_0^{n_0}-m$ hiển nhiên $ n_0$ lẻ

Tiếp theo xét 2 trường hợp

$ 1)$ Nếu $ 2^{k+1} | n_0^{n_0}-m$

Rõ ràng chỉ cần chọn $ n=n_0$.

$ 2)$ Nếu $ 2^{k+1}$ Không là ước của $ n_0^{n_0}-m$.

Đặt $ n_0^{n_0}-m=u\cdot 2^k$ Với $ u$ lẻ và theo định lý Euler,Cho mọi số lẻ $ a$ ta có $ a^{2^{k}}\equiv 1\pmod{2^{k+1}}$,Vì thế

$ (2^k+n_0)^{2^k+n_0}-m=(2^k+n_0)^{2^k}\cdot (2^k+n_0)^{n_0}-m\equiv (2^k+n_0)^{n_0}-m\\\equiv n_0^{n_0}+n_0\cdot n_0^{n_0-1}\cdot 2^k-m=(u+n_0^{n_0})2^k\equiv 0\pmod{2^{k+1}}$ Vì cả $ u$ và $ n_0$ đều lẻ.

Vì thế $ n=2^k+n_0$ thỏa mãn, nên ta có đpcm

Chứng minh tồn tại vô hạn trong số học

Đề bài: Cho m là một số nguyên dương. Chứng minh rằng tồn tại vô số nguyên dương n sao cho $m|3.2^n+n$

Lời giải:

Ta sẽ chứng minh quy nạp theo $m$, rõ ràng $m=1,2,3,4$ là hiển nhiên
Giả sử khẳng định đúng với mọi $m\leq t$ với số nguyên $t>3$
Đặt $d=ord_{t+1}{2}$ và $e=gcd(d,t+1)$, rõ ràng $e\leq d \leq \phi (t+1) \leq t$
Theo nguyên lí quy nạp phải tồn tại vô hạn số nguyên $a$ sao cho $e\mid 3\times 2^a+a$
Đặt $3\times 2^a+a=ef$ ( $f\in \mathbb{Z}^+$ )
Với mọi $g\in \mathbb{Z}^+$ Ta có $3\times 2^{a+dg}+(a+dg) \equiv 3  \times 2^a+a+dg =ef+dg (mod t+1)$
Ta cần chứng minh rằng tồn tại $g\in \mathbb{Z}^+$ sao cho $ef+dg\equiv 0 (mod t+1)$
Tương đương với $gcd(d,t+1) \mid -ef\Leftrightarrow e\mid -ef$ (luôn đúng) 9 (điều kiện cần và đủ của phương trình đồng dư)
vậy ta đã chứng minh tồn tại $n_1=a+dg\in \mathbb{Z}^+$ sao cho $t+1 \mid 3\times 2^{n_1}+{n_1}$
Nhưng vì tồn tại vô số nguyên dương a $a$, ta lấy $a$ lớn hơn $n_1$ ta lại có một số nguyên dương khác thỏa mãn đề bài,
Điều này có nghĩa là tồn tại vô số $n\in \mathbb{Z}^+$ sao cho $t+1\mid 3\times 2^n+n$ Điều phải chứng minh.

Bài toán về sự phân bố số chính phương và số nguyên tố

Bài toán: Xét tất cả các số nguyên tố $p_1 < p_2 <..p_n<..$ Đặt $a_n=p_1+p_2+..+p_n$. Chứng minh rằng với mọi n nguyên dương, nằm giữa $a_n$ và $a_{n+1}$ có ít nhất một số chính phương.

Giải:
Bổ đề: Với $n \ge 4$ thì $p_{n+1} > 2\sqrt{p_1+p_2+..+p_n}+1$
Chứng minh:
Với n=4, đúng.

Giả sử đúng với n=k tức là:
$p_{k+1} > 2\sqrt{p_1+p_2+..+p_k}+1$

Hay là $(p_{k+1}-1)^2 >4 (p_1+p_2+..+p_k)$

Ta cần chứng minh: $(p_{k+2}-1)^2 >4 (p_1+p_2+..+p_{k+1})$

Hay chỉ cần chứng minh: $(p_{k+2}-1)^2 \ge (p_{k+1}-1)^2 +4p_{k+1}$

Điều này tương đương $(p_{k+2}-p_{k+1})(p_{k+2}+p_{k+1}-2) \ge 4p_{k+1}$

Điều này là hiển do khoảng cách 2 số nguyên tố liên tiếp bé nhất là 2. Vậy ta có đpcm

Quay lại bài toán
Với n=1, thì giữa 2 và 5 tồn tại 4 là số chính phương.
Tương tự cho n=2,3,4

Giả sử đúng với n=k tức là giữa $a_k$ và $a_{k-1}$ tồn tại ít nhất một số chính phương, ta gọi $a^2$ là số chính phương lớn nhất trong các số chính phương đó.

$(a+1)^2 > a_{k}$

Áp dụng bổ đề thì $p_{k+1}>2a+1$ nên $a_{k+1} >(a+1)^2$.

Tìm giới hạn dãy số

Bài 1 (Đề thi chọn đội tuyển Amsterdam 2016) Cho dãy số thực $(x_n)$:

$\left\{\begin{matrix}
x_1=3 &  & \\
x_{n+1}=\frac{3x_n-1}{x_n} &  &
\end{matrix}\right.$ Xét dãy số:

$y_n=\frac{(3+\sqrt{5})^n}{2^n.x_1x_2..x_n}$ Chứng minh rằng dãy $(y_n)$ có giới hạn hữu hạn và tìm giới hạn đó.

Bài giải:




Xét $f(x) = \frac{3x-1}{x} $

Có $f'(x) = \frac{1}{x^2 } >0 $

Mà mặt khác ta có $x_2 < x_1 => x_n giảm $

Mặt khác, ta có $x_1 \geq \frac{3+\sqrt{5}}{2} $

Giả sử $x_n \geq \frac{3+\sqrt{5}}{2} $ đúng với $n$, ta chứng minh đúng với $n+1 $

Tức là chứng minh

$\frac{3x_n-1}{x_n} \geq \frac{3+\sqrt{5}}{2} <=> x_n \geq \frac{3+\sqrt{5}}{2} $

Do đó ta có $x_n$ giảm, bị chặn dưới bởi $\frac{3+\sqrt{5}}{2} $ do đó, tồn tại $L$ bằng $lim x_n $

Mà khi chuyển sang giới hạn, ta tính đc $L=\frac{3+\sqrt{5}}{2} $

Mặt khác $\frac{y_{n+1}}{y_n } = \frac{3+\sqrt{5}}{2x_{n+1}} \leq 1$

Do đó $y_n $ giảm, bị chặn dưới bởi $0$

Suy ra tồn tại $L'= lim y_n $

Thay vô $L'=\frac{3+\sqrt{5}}{2L} . L' => L'=0 $

Bài tổ hợp nhỏ

Bài toán: Có một số học sinh xếp thành một vòng tròn. Cô giáo yêu cầu các bạn học sinh đứng cạnh nhau bắt tay nhau. Gọi b là số học sinh nam, g là số học sinh nữ, B là số cặp học sinh nam bắt tay nhau và G là số cặp học sinh nữ bắt tay nhau. Chứng minh rằng: b-g=B-G. 

Lời giải của bài toán rất đơn giản như sau:

Dĩ nhiên số học sinh là $1$ thì không có gì để nói. Ta sẽ xét số học sinh từ $2$ trở lên
i) Với số học sinh là hai, ta xét là TRAI - TRAI, GÁI - GÁI, GÁI - TRAI thì thấy khẳng định bài toán đúng.
ii) Bây giờ giả sử bài toán đúng với số học sinh $n$. Bây giờ ta thêm một em học sinh vô. Vai trò mấy em này như nhau, nên giả sử ta thêm bạn nữ vào
Khi đó $B' = B$ và $G' = G + 1$.
a) TH1. Ta nhét em ấy vào giữa GÁI - GÁI thì $b' = b$ và $g' = g + 1$. Khi đó $B' - G' = B - G - 1 = b - g - 1 = b' - g'$.
b) TH2. Ta nhét em ấy vào giữa TRAI - GÁI thì $b' = b$ và $g' = g + 1$. Tương tự trên ta cũng có đpcm.
c) TH3. Ta nhét em ấy vào giữa TRAI - TRAI thì $b' = b - 1$ và $g' = g$. Lúc đó $B' - G' = B - G - 1 = b - 1 - g = b' - g'$. Xong.

Câu dãy số số học trong IMO và phương pháp suy luận

Đề bài: (IMO 18th) Cho dãy $(u_n)$ xác định như sau: $u_o=2$, $u_1=\frac{5}{2}$ và

$u_{n+1}=u_n(u_{n-1}^2-2)-u_1$

Chứng minh rằng $[u_n]=2^{\frac{2^n-(-1)^n}{3}}$

Lời giải:

Do đề bài yêu cầu chứng minh $[u_n]=2^{\frac{2^n-(-1)^n}{3}}$

Nên ta sẽ cố gắng biểu diễn $u_n$ dưới dang $2^x+a$

Bắt đầu với $u_1$

$u_1=\frac{5}{2}=2+\frac{1}{2}$

$u_2=(2+\frac{1}{2})(2^2-2)-(2+\frac{1}{2})=2+\frac{1}{2}$

$u_3=(2+\frac{1}{2})[(2+\frac{1}{2})^2-2]-(2+\frac{1}{2})$

Ta có thể đoán trước được $u_3=2^3+a (a<1)$ do thay 3 vào điều kiện đề bài

Nên ta tìm cách lấy số $2^3$ ra khỏi $u_3$, ta được:

$u_3=2^3+\frac{1}{2^3}$

Tương tự $u_4=2^5+\frac{1}{2^5}$

Bây giờ ta sẽ chứng minh: $u_n=2^{a_n}+\frac{1}{2^{a_n}}$

Do bài toán cần chứng minh $[u_n]=2^{\frac{2^n-(-1)^n}{3}}$  ta sẽ chứng minh:

Với $a_n=\frac{2^n-(-1)^n}{3}$ đây là công thức tổng quát của $a_n$ tuyến tính bậc 2 nên ta viết lại $a_{n+1}=a_n+2a_{n-1}$

Dễ thấy mệnh đề đúng với n=1,2,3,4,5.

Với n+1 thì:

$u_{n+1}=(2^{a_n}+2^{-a_{n}})(2^{a_{n-1}}+2^{-a_{n-1}-2}-(2+\frac{1}{2})$

Nhân ra ta được:

$u_{n+1}=2^{a_n+2a_{n-1}}+2^{-a_{n}-2a_{n-1}}+2^{2a_{n-1}-a_n}+2^{a_n-2a_{n-1}}-2-2^{-1}$

Mặt khác  Do: $a_{n+1}=a_n+2a_{n-1} \Rightarrow 2a_{n-1}-a_n=(-1)^n$

Thay vào ta có đpcm.

Định lý EGZ

Định lý Erdős Pál, Abraham Ginzburg és Abraham Ziv:

Từ 2n-1 số nguyên cho trước, luôn chọn được n số sao cho tổng của chúng chia hết cho n.

Lời giải:

gọi định lý trên là mệnh đề $\mathcal{E}(n)$

$\blacksquare$ ta chứng minh $\mathcal{E}(p)$ đúng với $p\in \mathbb{P}$

Với $p=2$ thì dễ thấy đúng ta xét với $p$ lẻ

gọi các số trong tập là $a_1,a_2,...,a_{2p-1}$

giả sử không tồn tại $p$ số nào chia hết cho $p$

$\Rightarrow \left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}\equiv 1(mod\ p)$

$\Rightarrow \sum_{1\le i_1<...<i_p\le 2p-1}\left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}\equiv \begin{pmatrix} 2p-1\\p \end{pmatrix}(mod\ p)$ $(*)$
ta có
$\begin{pmatrix} 2p-1\\p \end{pmatrix}\equiv \begin{pmatrix} 1\\1 \end{pmatrix}\begin{pmatrix} p-1\\ 0 \end{pmatrix}\not \equiv 0(mod\ p)$
ta sẽ chứng minh vế trái $(*)$ chia hết cho $p$,thật vậy ta có
$\sum_{1\le i_1<...<i_p\le 2p-1}\left ( a_{i_1}+a_{i_2}+...+a_{i_p} \right )^{p-1}=\sum_{s_1+s_2+...+s_p=p-1}\frac{(p-1)!}{s_1!s_2!...s_p!}\sum _{1\le i_1<...<i_p\le 2p-1}a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$ (thức ra từ chỉ cần $\sum _{1\le i_1<...<i_p\le 2p-1}a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$)
trong các số $s_1,s_2,...,s_p$ sẽ có $m \in \left [ 1,p-1 \right ]$ số bằng $0$ nên sẽ có $\begin{pmatrix} 2p-1-(p-m)\\m \end{pmatrix}=\begin{pmatrix} p+m-1\\ m \end{pmatrix}$ cách chọn các số $a_{i_j}$
mà $s_j=0$ do đó số $a_{i_1}^{s_1}a_{i_2}^{s_2}...a_{i_p}^{s_p}$ sẽ được lặp $\begin{pmatrix} p+m-1\\m \end{pmatrix}$ lần ( Có ý nghĩa: sau khi loại bỏ $p-m$ số có số mũ khác 0 thì cần m số (trong $2p-1-(p-m)$ số) có mũ bằng $0$ (vì $a_i^0..a_n^0=1$))

mặt khác

$\begin{pmatrix} p+m-1\\ m \end{pmatrix}\equiv \begin{pmatrix} 1\\0 \end{pmatrix}\begin{pmatrix} m-1\\m \end{pmatrix}\equiv 0(mod\ p)$ (hoặc có thể dùng định nghĩa nhị thức newton để chứng minh.)

$\Rightarrow p\mid VT_{(*)}$

điều này dẫn đến mâu thuẫn

$\blacksquare$ ta chứng minh nếu $\mathcal{E}(u)$ và $\mathcal{E}(v)$ đúng thì $\mathcal{E}(uv)$ đúng

gọi $2uv-1$ số nguyên dương là $a_1,a_2,...,a_{2uv-1}$

vì $2uv-1>2u-1$ nên tồn tại $u$ số có tổng chia hết cho $u$ và gọi tổng đó là $b_1$

lặp lại $2v-2$ lần ta có các tổng $b_1,b_2,...,b_{2v-2}$ chia hết cho $u$

do đó còn lại $2uv-1-u(2v-2)=2u-1$ số thì chọn được tổng $b_{2v-1}$ số chia hết cho $u$

mặt khác trong các số $b_1,b_2,...,b_{2v-1}$ ta sẽ chọn được $v$ số chia hết cho $v$

mặt khác $v$ số này cũng chia hết cho $u$ nên $uv$ số này $($ do mỗi tổng có $u$ số $)$ chia hết cho $uv$

vậy bài toán được chứng minh hoàn toán

Bất đẳng thức Bonse

Cho $p_1=2, p_2=3,..$ là dãy tăng các số nguyên tố. Chứng minh rằng:

$p_1p_2..p_n >p_{n+1}^2$

Giải.

Đặt $A_k=p_1p_2...p_k$ và $a_k=k.p_1p_2..p_{n-1}-p_n$ với $1 \le k \le p_n -1$. Ta thấy rằng $a_k$ không chia hết cho $p_i$ (với i=1,..n) suy ra $a_k \ge p_{n+k}$ (Do là dãy tăng). Chọn k=$p_n-1$ ta được $a_k=A_n-A_{n-1}-p_n>p_{p_n+n-1}>p_{3n-1}$ ( có thể chứng minh $p_n \ge 2n$ bằng quy nạp). Từ đây ta nhận thấy với $n \ge 6$ thì

$p_1..p_n>(p_1..p_{[n/2]})^2>p_{3[n/2]-1}^2>p_{n+1}^2$

Hai bài số học của Mỹ và Trung Quốc.

1/ (Mỹ) Chứng minh rằng với mỗi số nguyên $n \ge 2$ đều tồn tại một tập S gồm n số nguyên thoả mãn $(a-b)^2$ là ước của ab với mọi a,b thuộc S phân biệt.
2/ ( Trung Quốc) Tìm số nguyên không âm K nhỏ nhất sao cho với mọi tập con K- phần tử của tập hợp {1,2,..50} tồn tại hai phần tử a,b phân biệt mà a+b là ước của ab

Giải

1/ Ta chứng minh bằng quy nạp rằng với mỗi số nguyên dương n đều tồn tại một tập hợp $S_n$ gồm n phần tử thoả mãn điều kiện đã cho.

Với n=2 chọn $S_2$={0,1}. Giả sử khẳng định đã đúng đến n. Ta chứng minh khẳng định đúng với n+1. Gọi L là BCNN của các số khác 0 có dạng $(a-b)^2$ và ab trong đó $a,b \in S_n$. Đặt:

$S_{n+1}$={$s+L: s \in S_n$} $\cup ${0}

Khi đó, vì $L \ge 0$ nên $S_{n+1}$ chứ n+1 phần tử phân biệt không âm. Ta chứng minh tập $S_{n+1}$ thoả mãn.

Lấy u,v, bất kì. Nếu trong u,v có một số bằng 0 thì hiển nhiên. Nếu u,v đều khác 0 thì tồn tại hai phần tử a,b thuộc S sao cho
$u=L+a, v=L+b.$

Từ các chọn ta có $uv \vdots (u-v)^2$. Vậy ta đã chứng minh với n+1. Theo nguyên lí quy nạp ta có đpcm
2/ Giá trị nhỏ nhất của k=39. Cho a,b thuộc S thoả mãn a+b chia hết ab. Đặt $c=(a,b), a=ca_1, b=cb_1$ thì $(a_1,b_1)=1$ Khi đó $c(a_1+b_1)$ chia hết $c^2a_1b_1$ Suy ra $a_1+b_1$ chia hết $ca_1b_1$. Vì $a_1, b_1$ không có ước chung nên $a_1+b_1$ không chia hết $a_1$ và $b_1$. nên c chia hết cho $a_1+b_1$.(1)

Vì S là tập con {1,..,50}, ta có $a+b \le 99$, vì thế $c(a_1+b_1) \le 99$, từ (1) suy ra $a_1+b_1 \le 9$ mặt khác, $a_1+b_1 \ge 3$ từ đây ta tìm được các cặp (a,b):



(6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24);

(12, 4); (24, 8); (36, 12); (48, 16)

(20, 5), (40, 10), (15, 10), (30, 20), (45, 30)

(30, 6)

(42, 7), (35, 14), (28, 21)

(40, 24)

(45, 36)


Có 23 cặp, 24 số. Còn lại 26 số. Suy ra K>26. Ta cần tìm giá trị nhỏ nhất của K-26 sao cho ta sẽ chọn được hai số trong 24 số thuộc 1 cặp. Ta tìm được giá trị 13 là nhỏ nhất .Thật vậy, giả sử nhỏ hơn 12 thì ta chọn 26 số đó với các số sau đây 3,4,5,7,8,9,10,14,16,28,30,36.


Vậy K nhỏ nhất là 39.