Diễn Đàn MathScope - Xem bài viết đơn

sieunhanbachtang · 08-02-2019, 06:45 PM

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

08-02-2019, 06:45 PM	#2
sieunhanbachtang +Thành Viên+ Tham gia ngày: Oct 2018 Bài gởi: 28 Thanks: 14 Thanked 2 Times in 2 Posts	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