Cho 100 số thực dương thỏa mãn điều kiện:
i) $\sum\limits_{i=1}^{100}{a_{i}}^{2} > 10000$
ii) $ \sum\limits_{i=1}^{100}a_{i} < 300$
Chứng minh rằng luôn tồn tại 3 số có tổng không nhỏ hơn 100.
Edited by E. Galois, 24-05-2013 - 16:36.
Cho 100 số thực dương thỏa mãn điều kiện:
i) $\sum\limits_{i=1}^{100}{a_{i}}^{2} > 10000$
ii) $ \sum\limits_{i=1}^{100}a_{i} < 300$
Chứng minh rằng luôn tồn tại 3 số có tổng không nhỏ hơn 100.
Edited by E. Galois, 24-05-2013 - 16:36.
Bài toán này thuộc Gameshow NHỮNG BÀI TOÁN TRONG TUẦN. Bài toán đã được công bố lại hơn 2 ngày nhưng chưa ai giải được. BTC đã đặt hoa hồng hi vọng cho bài toán này.
Hoa hồng hi vọng sẽ mang lại 50 điểm cho người đầu tiên giải đúng được bài toán này. Nếu hết ngày 28/05 mà vẫn không có ai giải được, BTC sẽ công bố bài toán khác, tuy nhiên hoa hồng hi vọng sẽ vẫn tồn tại cho đến khi có người giải được bài toán này.
Cho 100 số thực dương thỏa mãn điều kiện:
i) $\sum\limits_{i=1}^{100}{a_{i}}^{2} > 10000$
ii) $ \sum\limits_{i=1}^{100}a_{i} < 300$
Chứng minh rằng luôn tồn tại 3 số có tổng không nhỏ hơn 100.
Note: lời giải của em có hỗ trợ từ 1 người bạn và có hỗ trợ từ công nghệ.
Không mất tổng quát, giả sử $x_{i+1} \ge x_i$ và ta sẽ đi chứng minh $x_{100} + x_{99} + x_{98} \ge 100$.
Giả sử đầu bài sai, tức $\not\exists 3$ số có tổng $\ge 100 \implies S = x_{100} + x_{99} + x_{98} < 100\ \text{(iii)}$
Gọi $x_j \ge x_i \ge t \ge 0$
Xét $(x_i-t)^2+(x_j+t)^2 = x_i^2+x_j^2+2t(x_j-x_i+t) \ge x_i^2+x_j^2$ (vì $x_j - x_i + t \ge 0$)
$\implies$ nếu thay $x_i -t \to x_i,\ x_j +t \to x_j$ thì vẫn cho tổng $2$ số không đổi nhưng tổng bình phương tăng lên.
Ta cũng có thể thay $x_{100}, x_{99}, x_{98}$ bằng $a = \frac S3$ là trung bình cộng của $3$ số đó mà không ảnh hưởng tới các điều kiện bài toán. (với $a < \frac {100}{3}$)
Phần thuật toán:
$\boxed{1.}$ Gán $i = \min,\ j = \max$ (lưu ý: $0 < x_i, x_j < a$)
$\boxed{2.}$ Nếu $i \ge j \to \boxed {\text{stop}}$
$\boxed{3.}$ Còn không, $t = \min \{x_i, a-x_j\},\ x_i := x_i - t,\ x_j := x_j + t$. Như nói ở trên, khi thế $x_i -t \to x_i,\ x_j +t \to x_j$ thì vẫn cho tổng $2$ số không đổi nhưng tổng bình phương tăng lên do đó, ta được dãy mới và cũng cũng thoả điều kiện (i), (ii), (iii)
$\boxed{4.}$ Quay lại bước $\boxed 1$
Phần Output, và giải:
Sau khi vòng lặp kết thúc, ta thu được: $0 = x_1 = x_2 =\ldots = x_{i-1}< x_i \le x_{i+1} = x_{i+2} = \ldots = x_{100} = a$
$\implies x_i + (100 - i)\cdot a < 300, x_i^2 + (100-i)\cdot a^2 > 10^4, 0 < x_i \le a < \frac {100} 3$
$\implies 10^4 - ab > (300 - b)\cdot a = ca^2 > 10^4 - b$ (với $b = x_i,\ c = 100 - i$)
$\implies b = 0 \lor a<1$
$\boxed{\text{TH1:}\ a<1}\implies 10^4 < b^2 + ca^2 < b+ca < 300 \implies$ vô lí
$\boxed{\text{TH2:}\ b=0} \implies c\cdot 10^4 < (ac)^2 < (300)^2 \implies c < 9 \implies 9a^2 > ca^2 > 10^4$
$\implies 3a > 100 \iff a > \frac {100} 3 \implies$ mâu thuẫn
Vậy điều giả sử là sai, đầu bài là đúng. Bài toán được chứng minh
Cách khác:
Giả sử $x_1 \ge x_2 \ge \ldots \ge x_{100}, S = x_1 + x_2 + x_3$
$$\implies x_1^2+x_2^2+x_3^2+ \ldots +x_{100}^2\\ \le x_1^2+x_2^2+x_3^2+\left\lfloor\frac{300-S}{x_3}\right\rfloor x_3^2+\left(300-\left\lfloor\frac{300-S}{x_3}\right\rfloor x_3\right)^2 \\ \le (S-2x_3)^2+2x_3^2 + \left\lfloor\frac{300-S}{x_3}\right\rfloor x_3^2+\left(300-\left\lfloor\frac{300-S}{x_3}\right\rfloor x_3\right)^2$$
Đi tắm đã, lúc nào em làm tiếp, bây giờ em "hơi" lười
Edited by ilovelife, 14-06-2013 - 17:30.
God made the integers, all else is the work of man.
People should not be afraid of their goverment, goverment should be afraid of their people.
Đây là một bài ứng dụng đơn giản của nguyên lý cực hạn.
Giả sử 100 số đó là $a_{1} \geq a_{2} \geq ... \geq a_{100} >0$.
Nếu như $a_{1} \geq 100$, thì $a_{1} + a_{2} + a_{3} > 100$.
Do đó, ta chỉ cần chứng minh với $a_{1} <100$.
Khi đó $100 - a_{1} >0, 100 - a_{2} >0, a_{1} -a_{3}\geq 0, a_{2} - a_{3} \geq 0$.
Vì vậy:
$100(a_{1} + a_{2} + a_{3}) \geq 100(a_{1} + a_{2} + a_{3}) - (100 - a_{1})(a_{1} -a_{3}) - (100 - a_{2})(a_{2} - a_{3}) = a_{1}^{2} + a_{2}^{2} + a_{3}( 300 - a_{1} - a_{2}) > a_{1}^{2} + a_{2}^{2} + a_{3}( a_{3} + a_{4} + ... + a_{100}) \geq a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + ... + a_{100}^{2} > 10000.$
Suy ra, $a_{1} + a_{2} + a_{3} >100$
Không mất tính tổng quát, giả sử $a_{1}\geq a_{2}\geq ...\geq a_{100}$
Trường hợp 1: $a_{1}\geq 100$
$\Rightarrow a_{1} + a_{2} + a_{3} \geq 100$
Trường hợp 2: $a_{1} \leq 100$
Ta có: $100\left ( a_{1} + a_{2} + a_{3}\right ) \geq 100\left ( a_{1} + a_{2} + a_{3}\right )-\left ( 100 - a_{1} \right )\left ( a_{1}-a_{3} \right ) - \left ( 100 - a_{2} \right )\left ( a_{2} -a_{3}\right )$
$= a_{1}^{2} + a_{2}^{2} + a_{3}\left ( 300 - a_{1} - a_{2} \right )$
$\geq a_{1}^{2} + a_{2}^{2} + a_{3}\left ( a_{3} + a_{4} + ... + a_{100}\right )$
$\geq a_{1}^{2} + a_{2}^{2} + ... + a_{100}^{2} \geq 10000$
$\Rightarrow a_{1} + a_{2} + a_{3}\geq 100$
0 members, 1 guests, 0 anonymous users