Gọi $N$ là số nghiệm nguyên của phương trình $x^2-y^2=z^3-t^3$, với điều kiện $0\leq x, y, z, t\leq 10^6$, và $M$ là số nghiệm nguyên của phương trình $x^2-y^2=z^3-t^3+1$, với điều kiện tương tự. Chứng minh $N> M$.
(IMO Shortlist 1979)
Có 96 mục bởi redfox (Tìm giới hạn từ 26-04-2020)
Đã gửi bởi redfox on 22-07-2016 - 16:36 trong Tổ hợp và rời rạc
Gọi mặt bàn là hình tròn $(O;R)$. Chọn hình tròn $(O_1;R_1)$ có bán kính $R_1$ lớn nhất. Trong các hình tròn còn lại, chọn hình tròn $(O_2;R_2)$ không giao với hình tròn $(O_1;R_1)$ và có bán kính $R_2$ lớn nhất. Quá trình tiếp tục như vậy cho đến khi chọn được các hình tròn $(O_1;R_1);(O_2;R_2);\cdots ;(O_n;R_n)$ đôi một không giao nhau và $n$ lớn nhất. Giả sử có $k$ sao cho $R_k<R_{k+1}$. Khi đó hình tròn $(O_{k+1};R_{k+1})$ giao với hình tròn $(O_{k-1};R_{k-1})$ và có bán kính lớn hơn hình tròn $(O_k;R_k)$ (vô lí với cách chọn hình tròn $(O_k;R_k)$).Vậy $R_1\geq R_2\geq \cdots \geq R_n$.
Giả sử tổng diện tích của $n$ hình tròn trên bé hơn $S/9$. Như vậy tống diện tích các hình tròn $(O_1;3R_1);(O_2;3R_2);\cdots ;(O_n;3R_n)$ bé hơn $S$ suy ra tồn tại điểm $A$ nằm ngoài n đường tròn trên suy ra $O_iA>3R_i, \forall i\in N, 1\leq i\leq n$. Vì khăn phủ kín mặt bàn nên tồn tại hình tròn $(O_{n+1};R_{n+1})$ chứa điểm $A$. Do cách chọn hình tròn $(O_1;R_1)$ nên $R_{n+1}\leqslant R_1$. Giả sử có $k$ sao cho $R_k\geq R_{n+1}> R_{k+1}$. Khi đó $O_{n+1}O_{i}\geq O_iA-O_{n+1}A>3R_i-R_{n+1}\geq R_i+2R_i-R_{n+1}\geq R_i+R_{n+1},\forall i\in N,1\leq i\leq k$. Vậy hình tròn $(O_{n+1};R_{n+1})$ không giao với $k$ hình tròn $(O_1;R_1);(O_2;R_2);\cdots ;(O_k;R_k)$ và có bán kính lớn hơn hình tròn $(O_{k+1};R_{k+1})$(vô lí với cách chọn hình tròn $(O_{k+1};R_{k+1})$). Vậy $R_{n+1}\leq R_n$. Chứng minh tương tự ta có hình tròn $(O_{n+1};R_{n+1})$ không giao với các hình tròn $(O_1;R_1);(O_2;R_2);\cdots (O_n;R_n)$ hay $n+1$ hình tròn trên đôi một không giao nhau (trái với cách chọn $n$).
Vậy cách chọn $n$ hình tròn trên thỏa mãn đề bài.
Đã gửi bởi redfox on 25-07-2016 - 19:01 trong Số học
Đặt $x=a+b, y=b+c, z=c+a$. Khi đó $2(a+b+c)=x+y+z, x<y+z$. Ta giả sử $x\geq y\geq z$. Gọi $n$ là số chữ số của $y$.Vì $S(y)\leq 4$ nên $y\leq 4.10^{n-1}$. Ta có $10^{n-1}\leq y\leq x< y+z\leq 2y\leq 2.4.10^{n-1}=8.10^{n-1}<10^n$. Vậy $x$ có $n$ chữ số. Xét phép cộng $x+y$. Nếu phép cộng ở hàng nào không nhớ thì tổng các chữ số của $x, y$ giữ nguyên, nếu có nhớ thì tổng các chữ số giảm $9$ đơn vị. Vậy $S(x+y)\leq S(x)+S(y)$. Ta cũng có $S(kx)\leq kS(x)$. Vậy $S(x)=S(10x)\leq 5S(2x)$
Ta có $2.10^{n-1}< x+y+z\leq 12.10^{n-1}$
Nếu $n= 1$ thì $S(a+b+c)\leq 6$.
Ta giả sử $n\geq 2$ Nếu $x+y+z$ có chữ số đầu tiên là $1$ thì phép cộng trên có nhớ. Vậy $S(a+b+c)\leq 5S(2(a+b+c)=5S(x+y+z)\leq 5(S(x)+S(y)+S(z)-9)\leq 5(4+4+4-9)=15$.
Trường hợp ngược lại, ta đặt $x=k10^{n-1}+l, y=p10^{n-1}+q$ với $l,k<10^{n-1}$. Ta có $S(x)=S(k10^{n-1}+l)=S(k10^{n-1})+S(l)=k+S(l)$, tương tự $S(y)=p+S(q)$.
Vậy $S(a+b+c)=S((x+y+z)/2)=S((k+p)10^{n-1}/2+(l+q+c)/2)\leq S(5(k+p)10^{n-2})+5(S(l)+S(q)+S(c))\leq S(5(k+p))+60-5(k+p)$
Xét các trường hợp của $k+p$ ta có $S(a+b+c)\leq 51$
Vậy giá trị lớn nhắt của $S(a+b+c)$ là $51$ chẳng hạn khi $a=94445555555, b=5555554445, c=5554445555$
Đã gửi bởi redfox on 26-07-2016 - 22:05 trong Số học
Ta có $x=1$ không phải nghiệm của phương trình. Nhân hai vế phương trình với $x-1$ ta được phương trình $(2-x)x^n=1$.
Ta có $(2-x)x^n=1>0\Rightarrow 2-x>0\Rightarrow x<2$
Nếu $0<x<1$ thì $(2-x)x^n=x(2-x)x^{n-1}<(2-x+x)^2/4=1$. Vậy $x>1$. Đặt $y=x-1$ ta được phương trình $(1-y)(1+y)^n=1$ với $y>0$
Áp dụng BĐT Bernoulli (dấu $=$ không xảy ra) ta có $1=(1-y)(1+y)^n>(1-y)(1+ny)=1+(n-1)y-ny^2\Rightarrow ny^2>(n-1)y\Rightarrow y>1-1/n\Rightarrow x>2-1/n$. Vậy $2-1/n< \alpha < 2$.
(Q.E.D)
Đã gửi bởi redfox on 28-07-2016 - 10:27 trong Tổ hợp và rời rạc
Gọi $F_n$ là số số tự nhiên thỏa mãn đề bài.
Ta sẽ tính $F_{n+2}$
Nếu chữ số đứng thứ hai từ trái sang phải khác $0$ thì có $F_{n+1}$ cách chọn $n+1$ chữ số sau cùng và $8$ cách chọn chữ số đầu tiên. Vậy có $8F_{n+1}$ số.
Nếu chữ số đứng thứ hai bằng $0$ thì có $F_n$ cách chọn $n$ chữ số sau cùng và $9$ cách chọn chữ số đầu tiên. Vậy có $9F_n$ số.
Vậy $F_{n+2}=8F_{n+1}+9F_n$. Ta lại có $F_1=1, F_2=17$. Bằng quy nạp ta chứng minh được $F_n=(4(-1)^n+9^n)/5$.
Đã gửi bởi redfox on 01-08-2016 - 14:46 trong Phương trình hàm
Thay $x=0$ ta được $f(f(y))=2f(y)$ (*)
Tính $f(f(x+f(y))$ bằng hai cách ta được $f(x+2y)=f(x+y)+f(y)$.
Thay vào đề ta có $f(x+f(y))=f(x+2y)$
TH1: $\exists y, f(y)-2y=a\neq 0$ suy ra $f$ tuần hoán với chu kì $a$ nên $f$ có GTLL và GTNN, ta đặt lần lượt là $M, N$.
Đặt $S$ là tập giá trị của $f$. Từ (*) ta có $x\in S\Rightarrow f(x)=2x$.
Ta có $2M=f(M)\in S$. Từ cách chọn $M$ ta có $2M\leq M\Rightarrow M\leq 0$. Tương tự $N\geq 0$.Vậy $N=M=0$ suy ra $f(x)=0$
TH2:$\forall y, f(y)-2y=0$. Ta có $f(x)=2x$
Thử lại ta có PT có hai nghiệm như trên
Đã gửi bởi redfox on 01-08-2016 - 17:43 trong Phương trình - Hệ phương trình - Bất phương trình
Giải HPT $9$ ẩn số $x_i(x_{i+1}-x_{i+2}+x_{i+3})<0, \forall i=1;2;\cdots ;9$ (coi $x_{i+9}=x_i$)
Đã gửi bởi redfox on 01-08-2016 - 22:22 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.
Bài 2
Giả sử các số âm, số dương trong $n$ số đã cho lần lượt là $b_1;b_2;...;b_m, c_1;c_2;...;c_p$. Giả sử $m\leq p\Rightarrow m\leq \left \lfloor \frac{n}{2} \right \rfloor$. Vì $b_i\in (-1;0)$ nên $-\sum_{i=1}^{m}b_i=\sum_{i=1}^{p}c_i<m$; $b_i^2<-b_i$. Tương tự $c_i^2<c_i$. Vậy
$2k=\sum_{i=1}^{n}a_i^2=\sum_{i=1}^{m}b_i^2+\sum_{i=1}^{p}c_i^2<-\sum_{i=1}^{m}b_i+\sum_{i=1}^{p}c_i<2m\leq 2\left \lfloor \frac{n}{2} \right \rfloor\Rightarrow n\geq 2k+2$
Với $n=2k+2$ ta chọn $k+1$ số bằng $-\sqrt{\frac{k}{k+1}}$, $k+1$ số bằng $\sqrt{\frac{k}{k+1}}$ thỏa mãn. Vậy $n=2k+2$
Đã gửi bởi redfox on 02-08-2016 - 15:41 trong Số học
Ta có $1995=3.5.7.19$. Từ đề bài ta có $0<y<x$
Bổ đề: Cho hai số nguyên $x, y$ và số nguyên tố $p$ có dạng $4k+3$.Khi đó $p\mid x^2+y^2\Leftrightarrow p\mid x, p\mid y$
Giả sử $\frac{x^2+y^2}{x-y}=pk$ với $p$ là số nguyên tố có dạng $4k+3$. Khi đó theo bổ đề $p\mid x, p\mid y$. Đặt $x=pz, y=pt$ với $z, t$ nguyên dương. Khi đó $\frac{z^2+t^2}{z-t}=k$. Vậy ta chỉ xét $\frac{x^2+y^2}{x-y}$ không có ước nguyên tố dang $4k+3$
Vì $x^2+y^2>x^2>x>x-y$ nên $\frac{x^2+y^2}{x-y}=5\Rightarrow x^2=5x-y^2-5y\leq 5x-6\Rightarrow x=2;3$. Vậy $\left ( x;y \right )=\left ( 2;1 \right );\left ( 3;1 \right )$
Vậy $\left ( x;y \right )=\left ( 2q;q \right );\left ( 3q;q \right )$ với $q$ là ước của $399$
Đã gửi bởi redfox on 04-08-2016 - 08:13 trong Số học
Chọn $n=2.3^k-1$. Đặt $m=lcm(1;2;...;n)$. Gọi $v_3(i)$ là số mũ của $3$ trong phân tích thừa số nguyên tố của $i$
Ta có $\sum_{i=1}^{n}\frac{1}{i}=\frac{\sum_{i=1}^{n}\frac{m}{i}}{m}$
Ta có $max(v_3(i)\mid i\in \mathbb{Z},1\leq i\leq 2.3^k-1)=k\Rightarrow v_3(m)=k$ và $\frac{m}{i}$ không chia hết cho $3$ khi và chỉ khi $i=3^k$. Vậy $\sum_{i=1}^{n}\frac{m}{i}$ không chia hết cho $3$ nên sau khi tối giản phân số , ta có $v_3(b_n)=k$. Chứng minh tương tự ta có $2\mid b_n\Rightarrow 2.3^k\mid b_n$ hay $n+1\mid b_n$
Ta có $\frac{a_{n+1}}{b_{n+1}}=\frac{a_n}{b_n}+\frac{1}{n+1}=\frac{a_n+\frac{b_n}{n+1}}{b_n}$. Vì $\frac{a_{n+1}}{b_{n+1}}$ tối giản nên $b_{n+1}\mid b_n$.(*)
Ta có $\sum_{i=1}^{2.3^k}\frac{1}{i}=\sum_{i=1}^{3^k-1}\frac{1}{i}+\sum_{i=3^k+1}^{2.3^k-1}\frac{1}{i}+\frac{1}{3^k}+\frac{1}{2.3^k}=\sum_{i=1}^{3^k-1}\frac{1}{i}+\sum_{i=3^k+1}^{2.3^k-1}\frac{1}{i}+\frac{1}{3^{k-1}}$
Gọi $m_1$ là mẫu số chung của $\sum_{i=1}^{3^k-1}\frac{1}{i}+\sum_{i=3^k+1}^{2.3^k-1}\frac{1}{i}+\frac{1}{3^{k-1}}$. Ta có $v_3(m_1)=k-1$. Vậy $v_3(b_{n+1})\leq k-1$(**)
Từ (*) và (**) ta có $b_{n+1}<b_n$. Vậy tồn tại vô hạn số $n$ để $b_n+1<b_n$
(Q.E.D)
Đã gửi bởi redfox on 13-08-2016 - 18:27 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.
Đã gửi bởi redfox on 17-08-2016 - 05:50 trong Tổ hợp và rời rạc
Đã gửi bởi redfox on 18-08-2016 - 15:16 trong Tổ hợp và rời rạc
Đã gửi bởi redfox on 19-08-2016 - 05:25 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.
Đã gửi bởi redfox on 22-08-2016 - 17:41 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.
Câu 5(lần 3)
a) Giả sử có cách sắp như vậy. Vì bảng có $8$ điểm nên mỗi đường có số lẻ viên sỏi.
Xét $2$ cột hai bên, $2$ đường chéo ,$1$ hàng ở giữa. Ta xét tổng các viên sỏi của các đường (kể cả lặp).
Mỗi ô trừ ô giữa lặp $2$ lần nên tổng là số chẵn.
Có $5$ đường, mỗi đường có số lẻ viên sỏi nên tổng là số lẻ.
Mâu thuẫn này dẫn đến không tồn tại cách sắp như vậy.
b) Đổi trạng thái một ô góc cố định (không sỏi thành có sỏi và ngược lại). Khi đó tính chẵn lẻ của số viên sỏi của $3$ đường đi qua ô góc này thay đổi nên tính chẵn lẻ điểm của bảng thay đổi. Vậy bằng cách làm này ta thành lập một song ánh giữa bảng có điểm số chẵn và bảng có điểm số lẻ hay số cách đặt sỏi bằng nhau.
Đã gửi bởi redfox on 22-08-2016 - 18:01 trong Toán rời rạc
Chọn $20$ người cao tuổi nhất. Gọi tổng số tuổi của họ là $S$
Người trẻ nhất trong $20$ người đó có tuổi không lớn hơn $\frac{S}{20}$.
Vậy tuổi của $14$ người còn lại không lớn hơn $\frac{S}{20}$. Vậy tổng số tuổi của $34$ người là $460$ không lớn hơn $\frac{14S}{20}+S=\frac{17S}{10}$. Vậy $S>260$, cách chọn thỏa mãn.
Đã gửi bởi redfox on 27-08-2016 - 22:01 trong Các bài toán Đại số khác
Biểu thức trên là tam thức bậc hai đối với $x_i$. Hệ số của $x_i^2$ là $p_i-p_i^2\geq 0$ nên đạt giá trị lớn nhất tại một trong hai đầu mút $a$ hoặc $b$ nên ta chỉ xét trường hợp $x_i$ nhận hai giá trị trên. Đặt $k=\sum_{i\mid x_i=a}p_i, l=\sum_{i\mid x_i=b}p_i$với $k,l\in [0;1], k+l=1$. ta có
$\sum_{i=1}^{n}p_ix_i^2-(\sum_{i=1}^{n}p_ix_i)^2= ka^2+lb^2-(ka+lb)^2=(k+l)(ka^2+lb^2)-(ka+ly)^2=kl(b-a)^2\leq (\frac{k+l}{2})^2(b-a)^2=(\frac{b-a}{2})^2$
(Q.E.D)
Đã gửi bởi redfox on 29-08-2016 - 17:48 trong Tổ hợp và rời rạc
Đếm bằng hai cách. Chọn $n$ phần tử từ $2n+1$ phần tử. Dễ có vế phải.
Chia $2n$ phần tử trong $2n+1$ phần tử thành $n$ cặp $(a_1;b_1);(a_2;b_2);...;(a_n;b_n)$
Giả sử có $k$ cặp chứa đúng $1$ phần tử trong $n$ cặp. Có $2^k\binom{n}{k}$ cách chọn $k$ phần tử (chọn $k$ cặp rồi chọn phần tử $a_i$ hoặc $b_i$).
Còn lại $\left \lfloor \frac{n-k}{2} \right \rfloor$ cặp chứa $2$ phần tử được chọn trong $n-k$ cặp còn lại. Có $\binom{n-k}{\left \lfloor \frac{n-k}{2} \right \rfloor}$ cách chọn.
Phần tử còn lại chọn hay không sao cho đủ $n$ phần tử, có $1$ cách chọn.
Vậy có $2^k\binom{n}{k}\binom{n-k}{\left \lfloor \frac{n-k}{2} \right \rfloor}$ cách chọn có $k$ cặp chứa đúng $1$ phần tử được chọn. Cho $k$ từ $0$ đến $n$ ta có vế trái.
(Q.E.D)
Có ai có cách khác không?
Đã gửi bởi redfox on 01-09-2016 - 17:21 trong Tổ hợp và rời rạc
Với $n$ chẵn. Lấy đa giác lồi $A_1A_2...A_{n-1}$. $A_1A_3$ cắt $A_2A_4$ tại $O$. Lấy $A_n$ nằm trong tam giác $OA_2A_3$. Khi đó $A_n$ nằm trong đúng $n-3$ tam giác $A_2A_3A_k$ là số lẻ. Vậy nếu $n$ đẹp thì $n$ lẻ.
Ta có điểm $D$ nằm trong tam giác $ABC$ khi và chỉ khi $C$ nằm trong góc đối đỉnh của $\widehat{ADB}$.
Xét $n=2k+1$ lẻ và điểm $P$ bất kì trong $X$. Kẻ các tia $PA_i$ với $i=1;2;...;2k$ và các tia đối của $PA_i$.
Ta chứng minh được tồn tại $2$ tia $PA_i$ và $PA_j$ sao cho không có tia nào ở giữa. Khi đó không có tam giác nào có một cạnh là $A_iA_j$ chứa điếm $P$ và tam giác $A_mA_nA_i$ chứa điểm $P$ khi và chỉ khi tam giác $A_mA_nA_j$ chứa điểm $P$.
Ta dễ chứng minh bằng quy nạp với $k$, số $n$ là đẹp bằng cách loại hai điểm $A_i, A_j$ như trên, khi đó số tam giác chứa điểm $P$ giảm đi một số chẵn. Vậy các số đẹp là các số lẻ $\geq 5$.
Đã gửi bởi redfox on 02-09-2016 - 07:51 trong Tổ hợp và rời rạc
Gọi các tâm hình tròn theo thứ tự di chuyển là $O_1;O_2;...;O_k;...$. Gọi:
-Số điểm nằm trong $(O_k;r)$, tổng bình phương khoảng cách từ $O_k, O_{k+1}$ đến các điểm đó lần lượt là $s_k, S_k, S'_k$.
-Số điểm nằm trong $(O_k;r)$ và nằm ngoài $(O_{k+1};r)$, tổng bình phương khoảng cách từ $O_{k+1}$ đến các điểm đó lần lượt là $a_k, A_k$.
-Số điểm nằm ngoài $(O_k;r)$ và nằm trong $(O_{k+1};r)$, tổng bình phương khoảng cách từ $O_{k+1}$ đến các điểm đó lần lượt là $b_k; B_k$.
Ta có:
-$s_k+b_k=s_{k+1}+a_k$.
-$S'_k+B_k=S_{k+1}+A_k$.
-Dựa vào vị trí tương đối của các điểm đối với $(O_{k+1};r)$, ta có $A_k\geq a_kr^2, B_k\leq b_kr^2$.
-Áp dụng Lagrange, ta dễ có $S'_k\leq S_k$.
Từ đây ta có $S_k-s_kr^2\geq S_{k+1}-s_{k+1}r^2$, dùng đơn biến ta dễ có với $k$ đủ lớn, $O_k\equiv O_{k+1}\equiv O_{k+2}\equiv ...$ hay vị trí của $O$ không đổi.
(Q.E.D)
Đã gửi bởi redfox on 03-09-2016 - 23:52 trong Tổ hợp và rời rạc
Tìm tất cả $n$ nguyên dương sao cho tồn tại bảng ô vuông $n\times n$ thoả mãn điều kiện:
-Mỗi ô vuông chứa nhiều nhất một số nguyên dương.
-Cột thứ $k$ chứa đúng $k$ số nguyên dương từ $1$ đến $k$.
-Tổng các số trên mỗi hàng bằng nhau.
Đã gửi bởi redfox on 04-09-2016 - 19:54 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.
Bài 3.Ta có:
-$P(1)=1$ (1)
-$P(n)-P(n-1)=n^{2003}$ (2)
-Đạo hàm (2): $P'(n)-P'(n-1)=2003n^{2002}$ (3)
Ta dễ có từ (1), (2), (3) $P(0)=P(-1)=0; P'(0)=P'(-1)$ (4)
Lấy $n$ từ $-k$ đến $k$, thay vào (2), cộng lại ta được $P(-k-1)=P(k)$. Đạo hàm: $P'(-k-1)=-P'(k)$ suy ra $P'(-1)=-P'(0)$.
Kết hợp với (4), ta có $P(0)=P(-1)=P'(0)=P'(-1)=0$ hay $P(n)$ có $2$ nghiệm bội là $0$ và $-1$ suy ra $Q(n) \mid P(n)$.
(Q.E.D)
Đã gửi bởi redfox on 06-09-2016 - 14:09 trong Dãy số - Giới hạn
Với $a,b\in \mathbb{Z}^+;gcd(a,b)=1$, viết $\frac{a}{b}=k_m+\frac{1}{k_{m-1}+\frac{1}{...+\frac{1}{k_2+\frac{1}{k_1}}}}$ trong đó $m,k_1,k_2,...,k_{m-1}\in \mathbb{Z}^+;k_m\in \mathbb{N}$.
Khi đó $n=1\underbrace{0..0}_{k_1-1}1\underbrace{0...0}_{k_2-1}1...1\underbrace{0...0}_{k_{m-1}-1}1\underbrace{0...0}_{k_m}$ (viết dưới dạng nhị phân) thoả mãn $x_n=\frac{a}{b}$.
Với mỗi phân số $\frac{a}{b}$, xác định duy nhất các số $m,k_1,k_2,...,k_m$ và xác định duy nhất $n$.
Với mỗi $n\in \mathbb{Z}$, xác định duy nhất các số $m,k_1,k_2,...,k_m$ và xác định duy nhất phân số $\frac{a}{b}$
Vậy đây là song ánh, dễ suy ra bài toán.
(Q.E.D)
Community Forum Software by IP.Board
Licensed to: Diễn đàn Toán học