Xem bài viết đơn
Old 09-02-2019, 03:44 PM   #3
chemthan
Administrator

 
chemthan's Avatar
 
Tham gia ngày: Mar 2009
Bài gởi: 349
Thanks: 0
Thanked 308 Times in 161 Posts
Trích:
Nguyên văn bởi sieunhanbachtang View Post
Ta chứng minh quy nạp theo $m=b-a$
Với $m=0$ và $m=1$ khẳng định bài toán hiển nhiên đúng
Giả sử đúng với $m\le k$, ta chứng minh đúng với $m=k+1$
Xét các cách chia dãy thành các dãy con, ta quan tâm tới dãy con chứa $a_1$ gồm các loại: $(a_1,a_{i_1}),(a_1,a_{i_2}),...,(a_1,a_{i_j})$
Với mỗi cách chia chứa dãy con $(a_1,a_{i_t})$ với $1\le t\le j$, thì số dãy lớn nhất có thể chia $a_{i_t+1},...,a_n$ $\le b-1$ và số dãy bé nhất có thể chia $a_{i_t+1},...,a_n$ $\ge a-1$
Nếu không tồn tại $t$ để đồng thời hai dấu bằng trên xảy ra, thì theo quy nạp ta có đpcm ( áp dụng giả thiết quy nạp cho từng cách chia dãy con chứa $a_1$)
Giả sử tồn tại $t$ để đồng thời hai dấu bằng trên xảy ra, ta lặp lại quá trình trên, ta đưa về bài toán:
Cho số $m \ge 3$ dãy $a_1,a_2,...,a_n$ thỏa mãn $a_1+a_2+...+a_n<x$ và $m$ là số tốt. Khi đó $m-1$ là số tốt
Lời giải:
Giả sử phản chứng
Giả sử có thể chia dãy thành $m$ phần có tổng là $u_1,...,u_m$ thỏa mãn $u_i <x$ và $\sum u_i<x$, khi đó theo giả thiết phản chứng, ta không thể gộp $u_i$ và $u_{i+1}$ hay $u_i+u_{i+1}\ge x\forall 1\le i\le m-1$
=>$(m-2)x+x>(u_1+2u_2+...+2u_{m-1}+u_m)>(m+1)x$
=>$x<0$
Khi đó $u_i<0 \forall 1\le i\le m$ nên $u_1+u_2<u_1<x$ (vô lý)
Vậy ta có đpcm
Đoạn đầu có vấn đề rồi. Giả sử số đoạn nhỏ nhất mà $a_{i_t+1},...,a_n$ có thể chia là $l_t$, và $r_t$ là số đoạn lớn nhất có thể chia. Thì $[l_1, r_1], [l_2, r_2], ..., [l_j, r_j]$ chưa chắc đã phủ đoạn $[a - 1, b - 1]$.
Đoạn sau chứng minh khi $a = 1$, em biến đổi đại số sai, nhưng nó khá đơn giản để chứng minh.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
chemthan is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to chemthan For This Useful Post:
sieunhanbachtang (10-02-2019)
 
[page compression: 9.79 k/10.87 k (9.93%)]