Donald Trump

Sử dụng bổ đề sau : Nếu $a$ không phải là số chính phương thì tồn tại vô hạn số nguyên tố $p$ sao cho $a$ không phải là số chính phương mod $p$

Chứng minh tham khảo IMOSL 2009 N7

Nếu có điều kiện duy nhất thì có thể quy nạp và tìm được công thức tổng quát của $a_n$ luôn.

Kết quả bài này hình như không đúng lắm. 

Ta xét số $m$ sao cho $a_m$ $=$ $m^{2017}$. Ký hiệu $f(i_1,...,i_{2017})$ $=$ $a_{i_1}+2017a_{i_2}+...+2017^{2016}a_{i_{2017}}$

Do $a_m$ $=$ $m^{2017}$ nên $ \left \{ 0,1,...,m^{2017}-1 \right \} $ $\subset $ $\left \{ f(i_1,i_2,...,i_{2017}) | i_j < m \forall j = 1,2,...,2017 \right \}$ mà $\left | \left \{ f(i_1,i_2,...,i_{2017}) | i_j < m \forall j = 1,2,...,2017 \right \} \right | \leq m^{2017}$ $=$ $\left | \left \{ 0,1,...,m^{2017} -1 \right \} \right |$ nên $f(i_1,i_2,...,i_{2017})$ là đôi một phân biệt với mọi $i_j$ $<$ $m$. Từ đây đánh giá dễ thấy $a_{m-1-2017k-r}$ $=$ $a_{m-1} - k(2016A + 1) - r$ với $A$ $=$ $\frac{2017^{2017} - 1}{2016}$

Xét $n$ $=$ $0,1, ... , 2016$ ta suy ra $a_i$ $=$ $i$ $\forall i = 0,1, ... , 2016$

Do đó $a_{m-1} - k(2016A+1)$ $=$ $2016$ nên $a_{m-1}$ $=$ $2016 + k(2016A +1)$

Mà ta có $m^{2017} - 1$ $=$ $a_{m-1}A$ nên $m^{2017} - 1$ $=$ $2016A + k(2016A^2+A)$ do đó $m^{2017} - 2017^{2017}$ $\vdots $ $2017^{2017} A$.

Chỗ này nếu chọn $m = 2017 A$ thì sao?

5. Giả sử $a_1\leq a_2 \leq a_3 \leq ... \leq a_{2017}$ và $s_1\leq s_2 \leq ... \leq s_{C^{2}_{2017}}$. Ta xác định $S_m$ $( m = \overline{1,2017} )$  như sau :

\[S_ m =  \left \{ T_i | \frac{\sum_{i=1}^m a_i}{2} \leq s_i \leq \sum_{i=1}^m a_i \right \} \]

Ta chỉ cần chứng minh hợp của các $S_m$ phủ hết tập các $s_i$.

Giả sử phản chứng tức là tồn tại $j$, $m$ sao cho :

\[\sum_{i=1}^m a_i < s_j < \frac{\sum_{i=1}^{m+1} a_i}{2}\]

$\Rightarrow a_{m+1} > \sum_{i=1}^m a_i$ do đó $s_j < a_{m+1}$ $\Rightarrow $ $T_j \subset \left \{ a_1,...,a_m \right \}$ $\Rightarrow $ $s_j \leq \sum_{i=1}^{m} a_i$. Mâu thuẫn. Vậy ta có điều phải chứng minh. $\square $

Phản chứng. Gọi $c_i$ là tổng các số trên cột $i$, $h_i$ là tổng các số trên hàng $i$. Do $\sum h_i < n^2/2$ nên ta có thể giả sử $h_n = \min\left \{ h_i,c_i|i=\overline{1,n} \right \} \Rightarrow h_n < n/2$ $\Rightarrow $ hàng $n$ chứa nhiều hơn $n/2$ số $0$. Do khi đổi chỗ các hàng và cột với nhau thì tính chất của bàng không thay đổi nên ta có thể giả sử $a_{ni} = 0$ với mọi $i=\overline{1,q}$ ($q>n/2$).Từ giả thiết $h_n+c_i\geq n \forall i = \overline{1,q}$ nên $c_i\geq n-h_n \forall i=\overline{1,q}$. Mà $q>n/2$ và $h_n < n/2$ nên $\sum c_i = \sum_{i=1}^{q} c_i + \sum_{i>q}^{} c_i \geq \sum_{i=1}^{q} c_i + \sum_{i>q}^{} h_n \geq n\cdot n/2 = n^2/2$ (vô lý). Vậy giả sử sai hay bài toán được chứng minh. $\square$

Dấu bằng chỉ có thể xảy ra khi $n$ chẵn, để chỉ ra có thể điền $a_{ij} = 0$ nên $i+j$ lẻ, còn lại điền số $1$.

PS. Bài này nên xếp vào mục tổ hợp thì đúng hơn.

Đặt $a_i = 2^{b_i}\cdot c_i$ với $c_i$ lẻ. Do $a_i \not | \ a_j, \forall i\neq j$ nên $c_i \neq c_j, \forall i\neq j$. Vì có $n$ số $c_i$ lẻ khác nhau và $1\leq c_i<2n$ nên tập các $c_i$ chính là tập các số lẻ từ $1$ đến $2n$.

Nhận thấy nếu $c_i\mid c_j$ thì $b_i>b_j$. Do $c_i \mid 3 c_i \mid 3^2 c_i \mid ... \mid 3^a c_i < 2n$ với $a = [\log_3(2n/c_i)]$ nên $b_i \geq [\log_3(2n/c_i)]$

$\Rightarrow a_i \geq 2^{[\log_3(2n/c_i)]}c_i = 2^{[\log_3(2n) - \log_3c_i]}c_i$

Ta chỉ cần chứng minh : $2^{[\log_3(2n) - \log_3c_i]}c_i \geq 2^{[\log_3(2n)]}$ (*)

Với $c_i = 1$ thì (*) trở thành đẳng thức.

Với $c_i = 3$ thì (*) tương đương với $3\geq 2$

Với $c_i \geq 5$, ta có đánh giá $c_i \geq 2^{[\log_3c_i]+1}$ nên (*) hiển nhiên đúng. $\square$

Chấm điểm: 10.

 

Liệu rằng, dù cho con thỏ di chuyển như thế nào cũng như máy dò báo những điểm nào, người thợ săn có thể chọn cách di chuyển của mình sao cho sau $10^9$ lượt thì anh ta chắc chắn rằng mình ở cách xa con thỏ không quá $100$.

Em góp ý chút : là "cô ấy" chứ không phải "anh ta"!

Bài 1. Đáp số : $a_0\vdots 3$.

Nếu tồn tại $n_0$ sao cho $a_{n_0}\equiv 2\pmod 3$ thì $a_{n+1}=a_n+3$ với mọi $n\geq n_0$ hay $a_n$ tăng từ $n_0$ suy ra $a_n$ không thỏa mãn bài toán.

Do đó ta chỉ cần xét với $a_0\equiv 0,1 \pmod 3$

Giả sử tồn tại số $a_0$ mà $a_0\equiv 1\pmod 3$ thỏa mãn bài toán.

Theo nhận xét trên, $a_n\equiv 1\pmod 3$ với mọi $n$.

Xét một số $a_n$ bất kỳ, khi đó tồn tại $b_m$ sao cho $(3b_m)^2<a_n\leq (3b_m+1)^2$ 

$\Rightarrow $ tồn tại số $t$ sao cho $a_{n+t}=3b_m+1$

$\Rightarrow $ tồn tại số $b_{m+1}$ sao cho $(3b_{m+1})^2<3b_m+1\leq (3b_{m+1}+1)^2$

Do $3b_m+1>(3b_{m+1})^2$ nên $b_m>b_{m+1}$

Dãy $b_m$ này giảm ngặt nên với $m$ đủ lớn sẽ cho ta điều vô lý.

Bây giờ ta chứng minh nếu $a_0\vdots 3$ thì bài toán thỏa mãn.

Do $a_0\vdots 3$ nên $a_n\vdots 3$ với mọi $n$. Xét số $a_n$ bất kỳ

$\Rightarrow $ tồn tại số $m$ sao cho $m^2<a_n\leq (m+1)^2$.

Do trong ba số liên tiếp luôn tồn tại một số chia hết cho $3$ nên số chính phương chia hết cho $3$ nhỏ nhất không nhỏ hơn $n$ sẽ không lớn hơn $(m+3)^2$

Xét số $t$ sao cho $a_{n+t}+3$ là số chính phương $\Rightarrow $ $a_{n+t+1}\leq (m+3) < a_n$ nếu $m$ khác $1$.

Nếu $m$ $=$ $1$ suy ra $a_n=3$ suy ra $a_{n+t+1}=3=a_n$.

Do đó $a_n$ bị chặn bởi $(m+3)^2-3$ suy ra $a_n$ thỏa bài toán.

Bài 5. Ta ký hiệu $a_i$ ($i=\overline{1,200}$) là các học sinh, $A_i$ ($i=\overline{1,6}$) là các bài toán, $\left | A_i \right |$ là số học sinh giải được bài toán $A_i$, $F(a_i)$ là tập các bài toán mà $a_i$ giả được. Bài toán tương đương với việc chứng minh tồn tại $i,j$ sao cho $F(a_i)\cup F(a_j)=\left \{ A_i|i=\overline{1,6} \right \}$

Gọi $S$ là số cặp $(a_i,A_j)$ mà học sinh $a_i$ giải được bài toán $A_j$.

Đếm theo $A_i$ : $S\geq 720$

Đếm theo $a_i$ : $S=\sum \left | F(a_i) \right |$

$\Rightarrow $ tồn tại $a_i$ mà $\left | F(a_i) \right |\geq 4$

Mặt khác theo nguyên lý bù trừ, $\left | A_i\cap A_j \right |=\left | A_i \right |+\left | A_j \right |-\left | A_i\cup A_j \right |\geq 120 +120-200=40$ nên với mỗi cặp bài toán thì tồn tại ít nhất $40$ học sinh giả được cả hai bài toán đó.

Chọn học sinh $a_j$ giải được các bài còn lại của $a_i$ ta thu được điều phải chứng minh.

Bài 3. Sử dụng dạng yếu của định lý Dirichlet: tồn tại vô hạn số nguyên tố dạng $nk+1$ với $k$ cố định (chứng minh sơ cấp cái này có thể tham khảo đáp án của Olympic toán học HS - SV năm nay)

Chọn $p \equiv 1 \pmod k$ thì hiển nhiên tồn tại một dãy $a_n$ thỏa mãn bài toán.

Bài này là Romania TST 1998, có lời giải sơ cấp rất đẹp mà không cần dùng hai định lý trên, anh tham khảo tại đây.

Lời giải không sử dụng nghịch đảo cho bài toán 1. Do $MN$ vuông góc với đối trung qua $A$ của $\triangle ABC$ nên $MN$ cắt $BC$ tại $S$ là giao điểm của tiếp tuyến tại $A$ của đường tròn $(O)$ với $BC$. Lấy $T$ thuộc $BC$ sao cho $AT$ là đối trung của $\triangle ABC$, $K$ là giao điểm của $MN$ với $AT$. Do $K(S,T;B,C)$ $=$ $-1$ và $\angle TKO$ $=$ $90^\circ$ nên $KO$ là phân giác ngoài $\angle BKC$, mặt khác do $O$ thuộc trung trực $BC$ nên tứ giác $BKOC$ nội tiếp. Do đó $\angle BKC$ $=$ $\angle BOC$ $=$ $2 \angle BAC$ suy ra $\angle BKT$ $=$ $\angle BAC$, từ đó $\angle ABK$ $=$ $\angle KAC$ $=$ $\angle ANK$ nên tứ giác $ANBK$ nội tiếp. Từ đó $\angle ABN$ $=$ $90^\circ$, tương tự ta thu được $\angle ACM$ $=$ $90^\circ$. Gọi $Q$ là giao điểm khác $A$ của đường tròn $(L,LB)$ với $AS$, $Q'$ là trung điểm $AQ$. Do $\angle QBS$ $=$ $\angle SAB$ $=$ $\angle ACB$ nên $BQ$ $\parallel $ $AC$, do đó $\angle Q'LA$ $=$ $\angle QBA$ $=$ $\angle BAC$ $=$ $\angle AMC$ suy ra $\triangle AMC$ $\sim$ $\triangle ALQ'$, từ đó $\tfrac{AM}{AL}$ $=$ $\tfrac{AQ'}{AC}$ $=$ $\tfrac{AQ}{2AC}$. Gọi $G$ là giao điểm của $QT$ với $AC$, do $\tfrac{TB}{TC}$ $=$ $\tfrac{SB}{SC}$ nên theo định lý Thales ta thu được $AS$ $=$ $2AC$, do đó $\tfrac{AM}{AL}$ $=$ $\tfrac{AQ}{AS}$. Mặt khác do $\angle QAG$ $=$ $\angle LAM$ nên các tam giác $LAM$ và $QAG$ đồng dạng suy ra $\angle TQA$ $=$ $\angle ZLA$, từ đó $AZ$, $TQ$ cắt nhau trên đường tròn $ABQ$. Gọi điểm đó là $Z'$ thì $Z'$ là đối xứng của $A$ qua $ML$. Tương tự ta xác định các điểm $R$ và $Y'$. Gọi $X'$ là giao điểm của hai đường tròn $(L,LB)$ và $(K,KC)$ thì $X'$ là đối xứng của $A$ qua $KL$, do $SA$ $=$ $SX'$ nên $X'$ thuộc đường tròn Apollonius chia $BC$ theo tỉ số $\tfrac{AB}{AC}$, từ đó $\tfrac{X'B}{X'C}$ $=$ $\tfrac{AB}{AC}$. Mặt khác do $\tfrac{TB}{TC}$ $=$ $\tfrac{AB^2}{AC^2}$ $=$ $\tfrac{X'B^2}{X'C^2}$ nên $X'T$ là đối trung của $\triangle X'BC$. Ta có biến đổi góc : $\angle Z'X'Y'$ $=$ $\angle BX'C$ $-$ $\angle BQT$ $-$ $\angle CRT$ $=$ $\angle BQR$ $+$ $\angle CRQ$ $-$ $\angle BQT$ $-$ $\angle CRT$ $=$ $180^\circ $ $-$ $\angle RTQ$ nên tứ giác $X'Y'TZ'$ nội tiếp. Gọi $U$ là trung điểm $BC$, do $UB^2$ $=$ $UC^2$ nên $U$ thuộc trục đẳng phương của $(L,LB)$ và $(K,KC)$, do đó $A$, $X'$, $U$ thẳng hàng. Do $X'T$ là đối trung của $\triangle BX'C$ nên $\angle BX'T$ $=$ $\angle UX'C$. Do đó $\angle Z'X'T$ $=$ $\angle QRC$ $-$ $\angle BQT$ $=$ $\angle QTB$. Do đó $(X'Y'Z')$ tiếp xúc $BC$, từ đó bài toán được chứng minh. $\square$

Lời giải bài toán 192. https://artofproblem...h599366p3557465 (#6)

Bài số 2 dịch chưa đúng lắm, $D$ là giao điểm của đường phân giác trong $\angle BAC$ với đường tròn ngoại tiếp $\triangle ABC$, $Z$ là giao điểm của trung trực $BC$ với đường phân giác ngoài của $\angle BAC$.

Giải. Gọi $M$ là trung điểm $BC$, $N$ là trung điểm $AC$, $P$ là hình chiếu của $D$ lên $AB$, $Q$ là hình chiếu của $D$ lên $AC$. Ta có $AP$ $=$ $AQ$ và $BP$ $=$ $CQ$ nên $AB$ $+$ $2BP$ $=$ $AC$ suy ra $MP$ $=$ $\tfrac{1}{2}$ $AC$ suy ra $MP$ $=$ $AN$. Dễ thấy $\triangle ZAN$ $\sim $ $\triangle ADP$ nên $\tfrac{AZ}{AN}$ $=$ $\tfrac{DA}{DP}$ suy ra $\tfrac{AZ}{MP}$ $=$ $\tfrac{DA}{DP}$ $\Leftrightarrow $ $\tfrac{AZ}{AD}$ $=$ $\tfrac{PM}{PD}$ suy ra $\triangle ZAD$ $\sim $ $\triangle MPD$ suy ra $\angle PMD$ $=$ $\angle AZD$, từ đó đường tròn ngoại tiếp $\triangle AZD$ đi qua trung điểm $AB$. $\square$

Bài 1. Chọn $a$ lẻ, $a\equiv 2\pmod 3$ thì tồn tại vô hạn $a$ như vậy.

Xét bộ $(a,a^2+1)$ thì $a^2+1-a\equiv 1+1-2\equiv 0\pmod 3$ $\Rightarrow $ $a^2+a+1$ $\mid$ $a^3-1$ $\mid$ $a^{a^2+1-a}-1$ $\mid$ $a^{a^2+1}-a^a$

Do $a$ lẻ nên $a^2+a+1$ $\mid$ $(a^2+1)^a$ $+$ $a^{a}$ $\Rightarrow$ $a^2+a+1$ $\mid$ $a^{a^2+1}+(a^2+1)^a$

Mặt khác $(a,a^2+1)$ $=$ $1$ nên $(a,a^2+1)$ thỏa bài toán. $\square$