Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Tổ Hợp

News & Announcements

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é !

* Nội quy MathScope.Org

* Một số quy định chung !

* 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

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 03-02-2019, 02:53 PM   #1
chemthan
Administrator

 
chemthan's Avatar
 
Tham gia ngày: Mar 2009
Bài gởi: 348
Thanks: 0
Thanked 304 Times in 159 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 )
[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:
anysu (07-02-2019)
Old 08-02-2019, 06:45 PM   #2
sieunhanbachtang
+Thành Viên+
 
Tham gia ngày: Oct 2018
Bài gởi: 27
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
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
sieunhanbachtang is offline   Trả Lời Với Trích Dẫn
Old 09-02-2019, 03:44 PM   #3
chemthan
Administrator

 
chemthan's Avatar
 
Tham gia ngày: Mar 2009
Bài gởi: 348
Thanks: 0
Thanked 304 Times in 159 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)
Old 10-02-2019, 05:28 PM   #4
sieunhanbachtang
+Thành Viên+
 
Tham gia ngày: Oct 2018
Bài gởi: 27
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ý)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
sieunhanbachtang is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 11:07 AM.


Powered by: vBulletin Copyright ©2000-2019, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 51.53 k/57.42 k (10.26%)]