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 [RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] |