Chia Sẻ Một Vài Vấn đề Về Cực Trị Rời Rạc - Diễn Đàn MathScope

Trang chủ » Nguyên Lý Cực Trị Rời Rạc » Chia Sẻ Một Vài Vấn đề Về Cực Trị Rời Rạc - Diễn Đàn MathScope

Có thể bạn quan tâm

Diễn Đàn MathScopeDiễn Đàn MathScope Diễn Đàn MathScope
Diễn Đàn MathScope > Sơ Cấp > Tổ Hợp
Chia sẻ một vài vấn đề về cực trị rời rạc
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
27-12-2013, 03:03 AM #1
huynhcongbang Administrator : Feb 2009 : Ho Chi Minh City : 2,413 : 2,165 Chia sẻ một vài vấn đề về cực trị rời rạc Thế là còn 1 tuần nữa thôi các bạn HSG Toán sẽ bước vào kì thi được trông đợi nhất của năm, đó chính là kì thi chọn học sinh giỏi cấp quốc gia mà chúng ta quen gọi là VMO. Kỳ thi VMO 2014 diễn ra trong hai ngày 04, 05/01 và có lẽ sớm nhất từ trước đến giờ. Trải qua nhiều vòng chọn lọc, làm nhiều bài kiểm tra, có lẽ giờ này các thành viên của các đội tuyển đều đã sẵn sàng cho thử thách sắp tới. Năm nay có lẽ vì bận việc nhiều nên thầy Dũng không tổ chức được chương trình tiến tới kì thi VMO như mọi năm, phần giải và bình luận đề thi các tỉnh cũng vẫn còn dang dở. Dù vậy, ở hầu hết các địa phương thì các chương trình rèn luyện khác vẫn được tổ chức, tức là các thí sinh của chúng ta vẫn có điều kiện để trao đổi, học hỏi rồi, như thế là đáng mừng rồi. Năm nay mình cũng không có điều kiện tham gia các chương trình nhiều và mới chỉ tranh thủ được vài ngày cuối năm này. Mong rằng sẽ được tham gia giải và bình luận đề thi như những năm trước! Trong nội dung dưới đây, mình xin chia sẻ một vài kinh nghiệm nho nhỏ về một phần trong rất nhiều nội dung mà các bạn phải chuẩn bị cho kì thi này, cụ thể là về bài toán cực trị rời rạc. Như chúng ta đều biết, các bài toán tổ hợp đòi hỏi tư duy nhiều, nhất là tư duy trừu tượng, sáng tạo không theo lối mòn. Trong phòng thi có thời gian ít, áp lực cao, ít có thí sinh nào dám mạo hiểm làm tổ hợp khi các câu đại số, giải tích (thường có mô hình sẵn) vẫn chưa xong. Tuy nhiên, nói đi thì cũng phải nói lại, tổ hợp cũng như hình học và số học, bên cạnh các nội dung định tính thì vẫn có các câu định lượng. Chẳng hạn như xét riêng trong chủ đề hình phẳng, nếu bạn nào học hình chưa tốt nhưng lại sử dụng tốt các công cụ phụ trợ như đại số, lượng giác, tọa độ, … vào bài toán thì chỉ cần một tí cố gắng nào đó để đưa bài toán định tính thuần túy về định lượng là coi như có thể tự tin xử lý được rất nhiều bài khó. Tuy nhiên, đó lại là một câu chuyện dài khác. Đi vào vấn đề chính, chúng ta có thể thấy rằng tổ hợp cũng thế, bên cạnh các bài chứng minh đòi hỏi sử dụng các lập luận logic, các nguyên lý tổ hợp một cách bài bản thì vẫn có các bài định lượng như thế. Mình thích các dạng này hơn và có lẽ nhiều bạn khác cũng thế. Trước hết mình xin nhắc lại vài điều về dạng toán cực trị rời rạc, một nhánh của các bài toán tổ hợp thi Olympic (tạm chia thành đếm, chứng minh, cực trị). Cũng giống như cực trị đại số thông thường, xét trên miền liên tục, các bài toán loại này cũng đòi hỏi 2 bước: - Bằng cách đánh giá thích hợp, chỉ ra giá trị cực trị. - Xây dựng một mô hình thích hợp để chứng minh dấu bằng đạt được. Ở nhiều bài thì khối lượng cần xử lý cho hai bước này là 50-50, nhiều khi lại là 20-80 hoặc 80-20. Chắc các bạn vẫn còn nhớ bài 3 đề TST 2010, việc đoán và lát được gạch thì dễ nhưng chứng minh được đó là giá trị tốt nhất thì lại vô cùng phức tạp; bài 2 IMO 2013 vừa rồi thì có thể nói tỉ lệ này là cân bằng khi mà chỉ ra mô hình đa giác đều cho cách tạo thành cấu hình Colombia cũng khó ngang với việc quy nạp để chứng minh. Mình xin nêu một thống kê nhỏ về các bài toán cực trị rời rạc các năm gần đây: - Năm 2007: bài 4 VMO, bài 5 TST. - Năm 2008: bài 3 TST. - Năm 2009: không có. - Năm 2010: bài 3 TST. - Năm 2011: không có. - Năm 2012: bài 4 VMO, bài 2 TST. - Năm 2013: bài 3, bài 6 TST. Rõ ràng các bài toán cực trị rời rạc đóng một vai trò không nhỏ trong các bài toán Olympic. Nội dung và hình thức của các bài cực trị tổ hợp rất phong phú, đa dạng. Tất nhiên mình không mong muốn trình bày phương pháp giải dạng Toán này vì nó rộng quá và mình cũng không đủ năng lực. Với những gì mình biết thì phương pháp để giải những bài này cũng muôn hình muôn vẻ, nhưng nếu học được một số kỹ thuật đem đi áp dụng thì cũng tốt. Dưới đây mình xin nêu một kỹ thuật nhỏ trong các kỹ thuật như thế. Đó là việc quan sát quy luật của dãy số nguyên để đoán kết quả. Chẳng hạn như bài toán sau: VD1. Trên bàn tròn có $n \ge 3$ người ngồi. Biết rằng trong số họ, ai cũng luôn nói dối hoặc luôn nói thật và hiện tại họ nói: “Cả 2 người ngồi cạnh tôi đều là kẻ nói dối”. Hỏi trên bàn có nhiều nhất và ít nhất bao nhiêu người nói dối? Đây là một bài mình phát triển từ một câu đố vui dành cho học sinh Tiểu học trong trường hợp $n=5$ (hoàn toàn có thể thử các trường hợp nhỏ). Tất nhiên bài toán này không phải quá dễ dàng để nhìn vào là ra ngay, nhất là khi đòi hỏi phải xây dựng một cách bài bản. Mình hãy thử với các trường hợp nhỏ để cố gắng tìm cách xử lý. Các bạn có thể vẽ hình ra để dễ hình dung hơn! - Với $n=3$ thì $\min = 2$ và $\max = 2$. (Chú ý rằng phủ định của với mọi là tồn tại nhé!) - Với $n=4$ thì $\min = 2$ và $\max =2$. - Với $n=5$ thì $\min =3$ và $\max=3$. Các giá trị đầu thì lớn nhất và nhỏ nhất bằng nhau rồi, ta tiếp tục. - Với $n=6$ thì $\min=3$ và $\max = 4$. - Với $n=7$ thì $\min=4$ và $\max=4$. - Với $n=8$ thì $\min=4$ và $\max=5$. - Với $n=9$ thì $\min=5$ và $\max=6$. - Với $n=10$ thì $\min=5$ và $\max=6$. Đến đây chắc các bạn có thể dễ dàng nhận ra quy luật của 2 dãy min và max. Với dãy min thì $2,2,3,3,4,4,5,5,…$, rất dễ nhận ra. Tuy nhiên, phải mô tả được công thức tổng quát của nó chứ không thể dừng lại ở đó. Một kinh nghiệm cho thấy rằng khi sự thay đổi theo các cụm có độ dài 2 như thế thì 90% công thức có dạng phần nguyên của một hàm tuyến tính theo n khi chia cho 2. Ta có thể làm chậm hơn một chút: + Với $n=2k$ thì $\min = k$. + Với $n=2k+1$ thì $\min =k$. Như thế, công thức có thể viết gộp lại là: $\min = \left[ \frac{n+1}{2}\right]$. Tương tự với dãy max, ta đoán được $\max = \left[ \frac{2n}{3}\right]$. Như thế, đến đây, ta đã có được gì trong tay? Nếu viết hết nội dung ở trên vào thì có điểm nào chưa? Thật khó nói nhưng có lẽ muốn có điểm thì ta phải cố gắng thêm nữa. Có thể chứng minh các giá trị kia tốt nhất là điều không dễ nhưng trước mắt, việc xây dựng đã khá đơn giản. Ta chỉ cần chia trường hợp ra và “bắt chước” theo cách đã làm với các số nhỏ. Chẳng hạn trường hợp $n=2k$ thì cho những người nói dối thật ngồi xen kẽ là có được ngay kết quả. Đây cũng là một kinh nghiệm nữa khi xử lý dạng này. Khi chứng minh điều kiện đủ, tức là xây dựng cấu hình thỏa mãn thì phải chia từng trường hợp ra xét cho dễ. Nếu để nguyên xi công thức dạng phần nguyên thì rất khó, nhiều khi không dựng được. Còn phần chứng minh điều kiện cần thì cũng tương đối nhẹ nhàng và có thể nói chính kết quả trên đã gợi ý cho phần này. Ta chỉ nêu nhận xét dưới đây là xong: (1) Trong 2 người liên tiếp, phải có ít nhất một người nói dối. (2) Trong 3 người liên tiếp, phải có ít nhất một người nói thật. Hai nhận xét này có vẻ rất hiển nhiên nhưng dễ nghĩ ra được hay không thì cũng tùy người. Tính khó dễ đến đây cũng không còn khách quan nữa khi mọi chuyện đã rõ ràng rồi. Dưới đây mình xin nêu một bài toán trong kì thi Olympic Tin học toàn quốc vừa rồi. Bài này phong cách không giống Toán lắm nhưng cũng khá thú vị! VD2. Tèo dùng $n \ge 2$ que diêm để xếp thành các con số như hình bên dưới. Hỏi số lớn nhất và nhỏ nhất mà Tèo có thể nhận được là bao nhiêu? Ở bài này, ta chỉ cần dùng một ý tưởng tham lam (greedy paradigm) đơn giản sau: số càng có nhiều chữ số thì càng lớn và có càng ít chữ số thì càng nhỏ. Nhờ đó mà trường hợp số lớn nhất, Tèo có thể dễ dàng thực hiện được như sau: - Nếu $n$ chẵn thì xếp $n/2$ số 1. - Nếu $n$ lẻ thì xếp 1 số 7 ở đầu tiên và $(n-3)/2$ số 1. Rõ ràng cách xếp này cho nhiều chữ số nhất và hiển nhiên số tương ứng sẽ lớn nhất. Tuy nhiên, trường hợp nhỏ nhất lại không đơn giản như vậy. Mình đã phải viết đến $n$ gần 30 mới dự đoán được quy luật. Còn lí do tại sao có sự khác nhau này giữa lớn nhất và nhỏ nhất thì dễ thôi, vì đặc điểm của số lượng các que diêm để xếp các số. Gọi $f(n)$ là số nhỏ nhất thu được. Ta thử liệt kê các kết quả xếp được bằng tay như sau: $f(2)=1,f(3)=7,f(4)=4,f(5)=2,f(6)=0,f(7)=8,f(8)=10 ,f(9)=18,f(10)=22,$ $f(11)=20,f(12)=28,f(13)=80,f(14)=88,f(15)=108,f(1 6)=188,f(17)=200,$ $f(18)=208,f(19)=288,f(20)=688,f(21)=888,f(22)=108 8,f(23)=1888,f(24)=2008$ Đến đây ta mới thấy được có một quy luật bắt đầu rõ ràng từ 14 và nó có chu kỳ 7. Việc chứng minh hầu như chỉ mang tính hình thức vì kết quả trên đã quá cụ thể. Các bạn thử làm bài tương tự dưới đây để thấy rõ hơn ý nghĩa của việc liệt kê này: Cho số nguyên dương $n$. Tìm số nguyên dương nhỏ nhất có $n$ chữ số và chia hết đồng thời cho $2,3,5,7$. Ta xét VD tiếp theo, công thức phức tạp hơn nhiều. VD3. Có một con thỏ ăn $n$ củ cà rốt trong một số ngày theo quy luật sau: (1) Ngày đầu tiên và ngày cuối cùng, nó phải ăn 1 củ cải. (2) Hai ngày liên tiếp nhau, con thỏ phải ăn số củ cải chênh lệch không quá 1. Hỏi số ngày ít nhất mà con thỏ ăn hết số củ cải là bao nhiêu? Mô tả của bài toán khá rõ ràng và việc xây dựng tương đối đơn giản, thậm chí là trong trường hợp $n$ khá lớn. Gọi $f(n)$ là số ngày ít nhất cần tìm, ta có dãy sau: $f(1)=1,f(2)=2,f(3)=3,f(4)=3,f(5)=4,f(6)=4,f(7)=5, f(8)=5,f(9)=5,f(10)=6,$ $f(11)=6,f(12)=6, f(13)=7,f(14)=7,f(15)=7,f(16)=7,f(17)=8,f(18)=8$ Quan sát quy luật của dãy số, ta thấy rằng: - Giá trị của $f$ thay đổi tại các số có dạng $k^2+1$. - Trong khoảng từ $(k-1)^2+1$ đến $k^2$, giá trị của $f$ thay đổi một lần nữa tại điểm giữa. Từ đó suy ra: - Với $k^2-k+1 \le n \le k^2$ thì giá trị $f(n)=2k-1$. - Với $k^2+1 \le n \le k^2+k$ thì giá trị $f(n)=2k$. Cách xây dựng thì cũng dễ thấy do ta có thể dựa theo mô hình tam giác Pascal và lựa chọn khi nào cần phải có tam giác đỉnh nhọn, đỉnh bằng phù hợp. Nếu tìm công thức trên một cách tổng quát thì ta có $\left [ \sqrt{4n-3} \right]$. Rõ ràng bằng một lập luận thú vị nào đó, ta có thể tìm ra được công thức này nhưng ở đây, mọi việc hoàn toàn có thể làm một cách thủ công và trong thời gian không quá lâu. Rõ ràng công việc này đáng được xem xét và áp dụng! Ở VD dưới đây, chính việc kiểm tra kết quả trong trường hợp nhỏ đã cho mình cách chứng minh cho bài toán. VD4. Cho số nguyên dương $n$. Xét dãy số nguyên dương hữu hạn $(a_k)$ gồm $k$ số hạng sao cho với mọi $1 \le i < j \le n$ thì tồn tại $t$ với $1 \le t \le k$ sao cho $a_t = i, a_{t+1}=j$ hoặc $a_t=j, a_{t+1}=i$. Hỏi giá trị nhỏ nhất của $k$ là bao nhiêu? Bài toán phát biểu hơi rắc rối nhưng nếu ngẫm nghĩ kĩ thì mọi chuyện cũng tương đối rõ ràng. Ta thử xét các trường hợp nhỏ: Với $n=1$ thì $k=1$. Với $n=2$ thì $k=2$ ứng với dãy $1,2$. Với $n=3$ thì $k=4$ ứng với dãy $1,2,3,1$. Với $n=4$ thì $k=8$ ứng với dãy $1,2,3,4,1,3,2,4$. Với $n=5$ thì $k=11$ ứng với dãy $1,2,3,4,5,1,4,2,5,3,1$. Trong quá trình xây dựng này, mình đã gặp một số vấn đề sau: Do có tất cả $C_n^2$ cặp số và có $C_2^2=1, C_3^2=3$ nên dự đoán kết quả là $C_n^2+1$. Trường hợp $n=5$ hoàn toàn hợp lý nhưng $n=4$ thì lại không xây dựng được $k=7$. Để kiểm tra cẩn thận và trực quan, mình đã vẽ ra mô hình có các số và các cạnh nối chúng nếu cặp đó thỏa mãn điều kiện đề bài. Từ đó phát hiện ra bài toán này có liên hệ mật thiết với bài toán về chu trình Euler trong đồ thị đầy đủ và dãy $(a_k)$ trên chính là sự liệt kê thứ tự đỉnh trong chu trình đó. Việc cộng thêm 1 ở đây là do dãy không tạo thành mô hình khép kín nên cần liệt kê dư ra 1 đỉnh. Từ điều kiện về tồn tại đường đi Euler, ta thấy cần phải chia thành 2 trường hợp chẵn lẻ mới có thể giải quyết được bài toán. Cụ thể là: - Nếu $n$ lẻ thì tất cả các đỉnh đều bậc chẵn nên thỏa mãn điều kiện có chu trình Euler, số $k$ cần tìm là $C_n^2+1 = \frac{n^2-n+2}{2}$. - Nếu $n$ chẵn thì tất cả các đỉnh đều bậc lẻ nên phải thêm vào $\frac{n}{2}$ cạnh nữa để có được đa đồ thị có các bậc đều chẵn và số $k$ cần tìm là $C_n^2+\frac{n}{2}=\frac{n^2}{2}$. VD5. (TST 2006) Trong không gian cho 2006 điểm mà trong đó không có 4 điểm nào đồng phẳng. Người ta nối tất cả các điểm đó lại bởi các đoạn thẳng. Số tự nhiên m gọi là số tốt nếu ta có thể gán cho mỗi đoạn thẳng trong các đoạn thẳng đã nối bởi một số tự nhiên không vượt quá m sao cho mỗi tam giác tạo bởi ba điểm bất kì trong số các điểm đó đều có hai cạnh được gán bởi hai số bằng nhau và cạnh còn lại gán bởi số lớn hơn hai số đó. Tìm số tốt có giá trị nhỏ nhất. Cũng như nhiều bài toán khác, ở bài này, ta thấy số 2006 không có ý nghĩa lớn lắm và thử tổng quát trong trường hợp $n \ge 2$ tùy ý. Bài toán này mình đã biết trước kết quả có liên quan đến lũy thừa của 2, nghĩa là giá trị của hàm cực trị thay đổi khi giá trị của $n$ tăng gấp đôi nên cố gắng hướng lập luận theo hướng này. Tuy nhiên, khi giải lại, xây dựng không tối ưu, mình đã mắc sai lầm như sau: Với $n=2$ thì chỉ cần $m=0$ là được. Với $n=3$ thì cần đến 2 số để đánh nên chọn $m=1$. Với $n=4$ thì cũng chỉ cần 2 số nên $m=1$. Với $n=5$ thì ta cần 3 số và $m=2$. Đến đây dễ thấy rằng luôn tồn tại một cạnh nào đó được đánh số 0, giả sử cạnh đó nối A và B. Ta chia $n-2$ đỉnh còn lại thành 2 phần thì rõ ràng mỗi đỉnh đó đều phải nối với A hoặc B bởi cạnh đánh số 0. Ta lại chia chúng thành 2 tập hợp: X chứa các đỉnh nối với A bởi cạnh đánh số 0, Y chứa các đỉnh nối với B bởi các cạnh đánh số 0. Khi đó ta có thể cho: - Từ mỗi đỉnh tập X sang mỗi đỉnh tập Y, cạnh nối với nhau đánh số 0. - Từ đỉnh A sang tập Y và từ đỉnh B sang tập X, cạnh nối với nhau đánh số 1. - Còn lại trong nội bộ X và Y, ta cần sử dụng $\max \{ f(|X|), f(|Y|) \}$ số. Tuy nhiên, do cần chọn nhỏ nhất nên $f(n)= 2 + \min \{ \max \{ f(|X|), f(|Y|) \} \}$. Hơn nữa, $f(n)$ là hàm đơn điệu và $|X|+|Y| = n-2$ nên $\min \{ \max \{ f(|X|), f(|Y|) \} \} = f([(n-1)/2])$. Từ đó đi đến kết luận $f(n)= 2 + f([(n-1)/2])$. Kết luận này sai và với phản ví dụ khi xây dựng trong trường hợp $n=7, n=8$ mình mới phát hiện ra vấn đề nằm ở chỗ cách xây dựng mô hình. Trên thực tế, ta có thể chia ra ngay từ đầu chứ không cần phải xét thêm điểm A, B và công thức đúng là $f(n)= 1 + f([(n+1)/2])$. Bài này cho ta thấy rằng trong nhiều trường hợp, ta xây dựng các mô hình dựa theo kinh nghiệm nhưng cũng có lúc cần phải xét các giá trị cụ thể trong trường hợp nhỏ thì mới phát hiện ra được vấn đề. Ngoài ra, việc xây dựng cho các giá trị nhỏ tạo thành dãy rồi tìm quy luật như đã nêu trên không chỉ áp dụng được cho dạng toán cực trị rời rạc mà một số bài toán định tính khác vẫn được. Thử thử xét bài toán kinh điển sau: Có hai người A, B chơi trò chơi bốc sỏi và ban đầu có $n$ viên sỏi, A đi trước. Mỗi người có thể bốc 2,3 hoặc 6 viên và ai bốc được viên cuối cùng thì thắng. Nếu chỉ còn 1 viên thì người chơi ở lượt đó bốc và thắng luôn. Hỏi với những giá trị nào của $n$ thì A có chiến lược thắng? Trước khi tiến hành xây dựng tương tự như trên, các bạn có thể cần 2 định nghĩa sau về trò chơi tổ hợp cân bằng (tức là hai bên có cách chơi như nhau): - Vị trí thắng: là vị trí mà tồn tại một cách đi đến vị trí thua (vị trí ở đây ý nói giá trị $n$ hiện tại, thắng này chỉ người chơi hiện tại và đi đến chỉ số sỏi còn lại sau lượt chơi đó). - Vị trí thua: là vị trí mà luôn phải đi đến một vị trí thắng. Có vẻ hơi mơ hồ, ta thử phân tích với bài toán cụ thể ở trên. Đặt $f(n)$ là hàm số đi từ tập $\mathbb{N}*$ vào tập $\{0,1 \}$ và nó nhận giá trị 1 khi A có chiến lược thắng, 0 khi B có chiến lược thắng. Hiển nhiên A thắng thì B thua và ngược lại nên ta có: $f(1)=1,f(2)=1,f(3)=1$. Đến đây để tính $f(4)$, ta thấy rằng nếu A bốc 2 hoặc 3 thì đều dẫn đến vị trí thắng của đối phương nên theo định nghĩa ở trên, 4 chính là vị trí thua và $f(4)=0$. Cứ thế, ta tính tiếp được: $f(5)=0, f(6)=1,f(7)=1,f(8)=1, f(9)=0,f(10)=0,…$ Dễ thấy quy luật: nếu $n$ chia 5 dư 0,1,2 thì A thắng; ngược lại thì B thắng. Để nghĩ ra được điều này thì rõ ràng không dễ nhưng để đoán ra được thì lại quá dễ dàng. Chứng minh được thực hiện một cách nhanh chóng bằng quy nạp. Dưới đây là một số bài toán tương tự để các bạn có thể tự lặp lại các thao tác trên để dự đoán kết quả, một công việc hết sức thú vị, tuy là thủ công nhưng lại mang đến những hiệu quả bất ngờ. Bài 1. (bài toán page shuffle) a. Có 3 chú ếch vàng và 3 chú ếch xanh ngồi trên lá sen theo mô hình sau: $VVV _ XXX$ (dấu “_” chỉ lá sen còn trống, V chỉ ếch vàng, X chỉ ếch xanh). Mỗi bước ta thực hiện điều khiển ếch di chuyển tuân theo các quy tắc sau: 1. Mỗi lần chỉ được di chuyển một con ếch. 2. Ếch chỉ có thể nhảy sang lá sen còn trống bên cạnh nó hoặc nhảy qua đầu đúng một con ếch khác để nhảy vào lá sen còn trống. 3. Ếch chỉ được nhảy tới, không được nhảy lùi. Hỏi sau ít nhất bao nhiêu bước nhảy thì ta có thể đưa ếch về trạng thái $XXX _ VVV$? b. Câu hỏi tương tự nếu thay 3 chú ếch vàng, 3 chú ếch xanh bởi $n$ chú ếch vàng và $n$ chú ếch xanh? Bài 2. (một phiên bản của bài toán tháp Hà Nội) Có ba hộp bóng đặt cạnh nhau trên đường thẳng, đánh số thứ tự là 1, 2, 3 từ trái sang phải. Hộp đầu tiên chứa $n$ quả bóng, kích thước đôi một khác nhau. Hai hộp còn lại rỗng. Người ta cho phép chuyển bóng theo quy tắc sau: 1. Mỗi lần chuyển chỉ chuyển được một quả bóng sang hộp đặt cạnh nó. 2. Quả bóng được chuyển phải là quả bóng lớn nhất trong hai hộp. Hãy tính số bước chuyển nhỏ nhất để chuyển tất cả các quả bóng sang hộp thứ 3. Bài 3. (TST 2008) Cho số nguyên $n>1$. Kí hiệu $T$ là tập hợp gồm n số nguyên dương đầu tiên. Một tập con $S$ của $T$ được gọi là tập khuyết trong $T$ nếu $S$ có tính chất: Tồn tại số nguyên dương $c$ không vượt quá $\frac{n}{2}$ sao cho với $s_1,s_2$ là hai số bất kì thuộc $S$, ta luôn có $|s_1-s_2| \neq c$. Hỏi tập khuyết trong $T$ có thể có tối đa bao nhiêu phần tử ? Bài 4. Cho bảng ô vuông $n \times n$. Hỏi phải tô màu ít nhất bao nhiêu ô vuông của bảng sao cho: a. Mỗi ô vuông đều được tô màu hoặc kề cạnh với ít nhất một ô được tô màu? b. Mỗi ô vuông đều được tô màu hoặc kề đỉnh với ít nhất một ô được tô màu? Bài 5. Có $n$ đống sỏi và đống thứ $i$ có đúng $i$ viên sỏi, $1 \le i \le n$. Hỏi sau ít nhất bao nhiêu lần thao tác, người ta có thể lấy hết số sỏi ở $n$ đống nếu như: a. Mỗi thao tác cho phép chọn một số nguyên dương $k$ và bốc đi bớt $k$ viên sỏi ở một số đống tùy ý (chỉ cho phép các đống có số sỏi không nhỏ hơn $k$). b. Mỗi thao tác cho phép chọn một số nguyên dương $k$ và bốc đi bớt hoặc thêm vào $k$ viên sỏi ở một số đống tùy ý (chỉ cho phép các đống có số sỏi không nhỏ hơn $k$). Bài 6. Trong một trò chơi truyền hình, có $n$ câu hỏi. Một người chơi trả lời các câu hỏi này sẽ nhận kết quả là đúng hoặc sai. Nếu trả lời đúng sẽ được điểm, nếu trả lời sai sẽ bị chia đôi số điểm hiện tại. Xét trong tất cả các tình huống trả lời các câu hỏi đúng/sai, hỏi người chơi sẽ nhận được tất cả bao nhiêu điểm? Bài 7. Có $n$ chiếc cốc được úp thành một vòng tròn và dưới 1 trong các chiếc cốc này, có một đồng xu. Ở mỗi lượt, người chơi có thể chọn ra 4 chiếc cốc liên tiếp và mở lên. Nếu có đồng xu thì trò chơi kết thúc. Nếu không thì người chơi sẽ trả 4 chiếc cốc về vị trí cũ và bằng một cách nào đó, đồng xu sẽ di chuyển sang một trong hai cốc kề nó. Người chơi luôn suy luận, phân tích kĩ trong quá trình bốc. Hỏi trong trường hợp xấu nhất thì số lần cần phải thao tác là bao nhiêu? Bài 8. Ở một cửa hàng nọ, người chủ chỉ sử dụng các đồng tiền có giá trị là lũy thừa tự nhiên của 3. Có một người khách cần mua một món hàng có giá trị là $n$. Dù đã chuẩn bị sẵn một số loại đồng tiền có giá trị là lũy thừa của 3 (mỗi loại có số lượng tùy ý) nhưng không may là với các loại đồng tiền đó không thể nào trả được vừa đúng giá tiền $n$. Người bán cũng không muốn thối lại tiền thừa. Thế là người khách đành phải trả nhiều hơn giá trị của món hàng. Để tiết kiệm, ông đã trả số tiền $m>n$ với $m$ nhỏ nhất có thể. Hỏi trong các cách trả số tiền $m$ đó, số đồng tiền nhiều nhất đã sử dụng là bao nhiêu? Bài 9. Để mở một cánh cửa, tên trộm cần phải bấm đúng thứ tự của $n$ cái nút mà người chủ quy định trước. Nếu bấm nút đúng thứ tự thứ thì các nút sẽ giữ nguyên vị trí, nếu chỉ cần bấm sai một nút thì toàn bộ các nút đã bấm sẽ bị bật lên và tên trộm sẽ phải thử lại từ đầu. Chẳng hạn với $n=3$ và thứ tự các nút cần bấm là $\left\{ 2,3,1 \right\}$. Nếu ban đầu, tên trộm bấm nút 1 hoặc 3 thì nút sẽ bật lên ngay lập tức. Nếu hắn bấm nút 2 thì nút sẽ giữ nguyên (do nút 2 có thứ tự đầu tiên). Tiếp theo, nếu hắn bấm nút 1 thì do sai thứ tự nên cả nút 2 đã bấm trước đó và nút 1 sẽ bị bật lên. Nếu hắn bấm nút 3 tiếp theo nút 2 thì cả hai nút sẽ giữ nguyên và còn lại hắn chỉ cần bấm nút 1. Dù một tên trộm có thông minh đến đâu thì trong tình huống xấu nhất, hắn cũng phải bấm nút 7 lần. Hỏi với $n$ nút trong trường hợp xấu nhất, tên trộm phải bấm nút bao nhiêu lần để mở được cái cửa? Nếu có vấn đề gì ở các bài toán trên thì các bạn trao đổi trực tiếp tại đây nhé! Trong các bài tập trên, bài 6 có công thức khác với các bài kia một tí nhưng vẫn có thể dự đoán được, đây cũng là bài toán được một bạn gửi lên mathscope cách đây 2 năm mà đến giờ mình vẫn chưa chứng minh được công thức mình dự đoán được là đúng! Mong rằng các nội dung mình trên bày ở trên sẽ giúp các bạn có một chút cảm hứng mới nào đó với các bài toán cực trị rời rạc nói riêng và tổ hợp nói chung. Tất nhiên nó chỉ là một con đường, một kỹ thuật để tư duy chứ không phải là một phương pháp gì to lớn nhưng nếu đi thi, ta có thể sử dụng thuần thục một công cụ gì đó thì quả thật rất tốt! Chúc các bạn thí sinh có những ngày ôn luyện cuối cùng thật tốt và có một kỳ thi thành công! [RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
number.png (16.8 , )
__________________ Sự im lặng của bầy mèo
AnhIsGod (28-12-2013), batigoal (27-12-2013), cuongpbc (04-01-2014), dangvip123tb (27-12-2013), dbm3001 (27-12-2013), henry0905 (27-12-2013), hoangqnvip (27-12-2013), khi gia (27-12-2013), MathForLife (27-12-2013), nghiepdu-socap (27-12-2013), NguyenThanhThi (27-12-2013), pco (27-12-2013), portgas_d_ace (27-12-2013), quocbaoct10 (27-12-2013), Short_list (27-12-2013), thaygiaocht (19-12-2014), Trànvănđức (28-12-2013), Trầm (27-12-2013), tson1997 (29-12-2013)
huynhcongbang

Từ khóa » Nguyên Lý Cực Trị Rời Rạc

Liên Hệ

TRUYỀN HÌNH CÁP SÔNG THU ĐÀ NẴNG

Địa Chỉ: 58 Hàm Nghi - Đà Nẵng

Phone: 0904961917

Web: truyenhinhcapsongthu.net

Facebook: https://fb.com/truyenhinhcapsongthu/

Twitter: @ Capsongthu

Copyright © 2022 | Thiết Kế Truyền Hình Cáp Sông Thu