Chia dãy số thà nh đoạn con

[chemthan]

Cho một dãy số gồm $n$ số $a_1, a_2, ..., a_n$ và một số $x$. Một số $k$ được gọi là tốt nếu có một cách chia dãy số đã cho thành $k$ đoạn con liên tiếp nhau mà tổng của mỗi đoạn con là nhỏ hơn $x$. Gọi $a$ là số tốt nhỏ nhất, $b$ là số tốt lớn nhất. Chứng minh rằng mọi số trong đoạn $[a, b]$ đều là số tốt.
(Bài này tình cờ xem được, chắc cũ rồi )
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[sieunhanbachtang]

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] 

[chemthan]

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] 

[sieunhanbachtang]

Hjhj em cảm ơn anh, tết bánh lấp não ạ
Lỗi các đoạn không lấp hết do em xử lí hơi phức tạp, thực tế có thể ép luôn được mỗi cách chia chứa $a_1$ như vậy có số dạy nhỏ nhất là $a-1$ và $b-1$ luôn ạ.
Còn đoạn biến đổi sau em xin sửa lại lỗi:
$(m−2)x+x>(u_2+u_3+...+u_{m-1})+(u_1+u_2+...+u_m)=(u_1+2u_2+...+2u_{m−1} +u_m)\ge (m-1)x$ (vô lý)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]