|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
03-02-2019, 02:53 PM | #1 |
Administrator Tham gia ngày: Mar 2009 Bài gởi: 349 Thanks: 0 Thanked 308 Times in 161 Posts | Chia dãy số thành đoạn con 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 ) |
The Following User Says Thank You to chemthan For This Useful Post: | anysu (07-02-2019) |
08-02-2019, 06:45 PM | #2 |
+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 |
09-02-2019, 03:44 PM | #3 | |
Administrator Tham gia ngày: Mar 2009 Bài gởi: 349 Thanks: 0 Thanked 308 Times in 161 Posts | Trích:
Đ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. | |
The Following User Says Thank You to chemthan For This Useful Post: | sieunhanbachtang (10-02-2019) |
10-02-2019, 05:28 PM | #4 |
+Thành Viên+ Tham gia ngày: Oct 2018 Bài gởi: 28 Thanks: 14 Thanked 2 Times in 2 Posts | 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ý) |
Bookmarks |
|
|