[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Xin chào tất cả các bạn!
Chuyên đề này hứa hẹn sẽ là một thử thách thật sự dành cho những bạn muốn chinh phục đỉnh núi của vinh quang, bởi vì đây là một dạng toán chưa khi nào là quá dễ, cũng như đây là dạng bài cuối cùng của đề thi HSG, là bài chọn ra ai là người giỏi nhất.
Độ khó của dạng toán này chắc là khỏi bàn rồi nhỉ, nhưng mình hy vọng các bạn đừng quan tâm đến nó mà hãy cố gắng hết sức của bản thân nhé. ╰(*°▽°*)╯
Sau đây mình sẽ giới thiệu cho các bạn 2 nguyên lí cơ bản của tổ hợp, rời rạc; đó là nguyên lí Dirichlet và bất biến.
I. Nguyên lí Dirichlet
1. Cơ sở lý thuyết.
1.1. Nguyên lí Dirichlet dạng tổ hợp.
Nếu nhốt [imath]n[/imath] con thỏ vào [imath]m[/imath] chuồng [imath](n \not \vdots m)[/imath] thì phải có ít nhất 1 chuồng chứa không ít hơn [imath]\left [ \dfrac{n}{m} \right ]+1[/imath] con thỏ.
1.2. Nguyên lí Dirichlet dạng độ đo(hình học)
Giả sử hình [imath](H)[/imath] được chia thành [imath]n[/imath] hình con [imath](H_1),(H_2),...,(H_n)[/imath]. Nếu tổng diện tích [imath]n[/imath] hình con lớn hơn [imath]k\cdot S_{(H)}[/imath] thì tồn tại ít nhất 1 điểm là điểm chung của [imath]k+1[/imath] hình con. Nếu tổng diện tích [imath]n[/imath] hình con nhỏ hơn [imath]k.S_{(H)}[/imath] thì tồn tại ít nhất 1 điểm là điểm chung của không quá [imath]k-1[/imath] hình con.
(Lưu ý nếu hình (H) suy biến thành đoạn thẳng thì nguyên lí đó áp dụng cho "độ dài" thay cho "diện tích").
2. Một số kỹ thuật ứng dụng định lí Dirichlet
2.1. Phân chia tập hợp để tạo các n-tập ("chuồng").
Ví dụ mở đầu. Trong hình vuông có cạnh bằng 1 đặt 51 điểm bất kì phân biệt. Chứng minh có ít nhất 3 trong 51 điểm đó nằm trong đường tròn có bán kính [imath]\dfrac{1}{7}[/imath].
Nhận xét. Nội dung cơ bản của phương pháp là chia một đối tượng lớn thành nhiều đối tượng nhỏ (các đối tượng này như các “chuồng”); sau đó áp dụng nguyên lí Dirichlet.
Ví dụ 2. Trong hình tròn có diện tích bằng 8 đặt 17 điểm bất kì sao cho không có 3 điểm nào thẳng hàng. Chứng minh rằng có ít nhất ba điểm tạo thành một tam giác có diện tích nhỏ hơn 1.
Ví dụ 3. Trong hình tròn (C) tâm O, bán kính R = 2,5 cho 10 điểm bất kì; CMR có hai điểm có khoảng cách nhỏ hơn 2.
Ví dụ 4. Cho hình bình hành ABCD và 25 đường thẳng. Mỗi đường thẳng chia ABCD thành 2 hình thang với tỉ số diện tích là [imath]\dfrac{1}{3}[/imath]. CMR trong 25 đường thẳng đó có 7 đường thẳng đồng quy.
Nhận xét. Việc phát hiện ra các m – tập ở đây dựa trên tính chất đặc trưng của các đường thẳng.
2.2. Xây dựng n-tập theo đối tượng xuất phát.
Ví dụ mở đầu. Trong mặt phẳng cho 2009 điểm. Biết rằng trong 3 điểm bất kì lấy từ các điểm đã cho luôn có hai điểm có khoảng cách không lớn hơn 1. CMR có 1005 điểm nằm trong hình tròn bán kính 1.
Nhận xét. Trong ví dụ trên, việc chọn ra các n - tập được bắt đầu từ việc chọn ra một “đối tượng xuất phát” là điểm M. Từ “đối tượng xuất phát” này ta lập luận để suy ra các đối tượng (trường hợp) còn lại ... Đây là một kĩ thuật hay dùng trong các bài toán sử dụng nguyên lí Đirichlet.
Ví dụ 2. Trong mặt phẳng cho 9 đường thẳng song song nằm ngang và 3 đường thẳng song song nằm dọc. Người ta đánh dấu các giao điểm của các đường thẳng này bởi hai màu xanh (X) và đỏ (Đ). CMR tồn tại 2 đường thẳng nằm ngang và 2 đường thẳng nằm dọc sao cho 4 giao điểm của chúng được tô cùng màu.
Ví dụ 3. Trên đường tròn cho 16 điểm tô bởi một trong ba màu: X, Đ, V. Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi hai màu: T, L. Chứng minh rằng ta luôn có 3 trong 16 điểm trên tô cùng màu và 3 cạnh của nó cũng được tô cùng màu.
Ví dụ 4. Cho đa giác đều A1A2…A1981 nội tiếp (O). CMR trong số 64 đỉnh bất kì của đa giác luôn có 4 đỉnh là các đỉnh của một hình thang.
Luyện tập:
!!!
Bất ngờ không =)) Chúc mừng bạn đã tìm ra gợi ý của chúng mình nhé ^^
Gợi ý của bạn là: [imath]1,1,2,3,5,\cdots[/imath]
Chuyên đề này hứa hẹn sẽ là một thử thách thật sự dành cho những bạn muốn chinh phục đỉnh núi của vinh quang, bởi vì đây là một dạng toán chưa khi nào là quá dễ, cũng như đây là dạng bài cuối cùng của đề thi HSG, là bài chọn ra ai là người giỏi nhất.
Độ khó của dạng toán này chắc là khỏi bàn rồi nhỉ, nhưng mình hy vọng các bạn đừng quan tâm đến nó mà hãy cố gắng hết sức của bản thân nhé. ╰(*°▽°*)╯
Sau đây mình sẽ giới thiệu cho các bạn 2 nguyên lí cơ bản của tổ hợp, rời rạc; đó là nguyên lí Dirichlet và bất biến.
I. Nguyên lí Dirichlet
1. Cơ sở lý thuyết.
1.1. Nguyên lí Dirichlet dạng tổ hợp.
Nếu nhốt [imath]n[/imath] con thỏ vào [imath]m[/imath] chuồng [imath](n \not \vdots m)[/imath] thì phải có ít nhất 1 chuồng chứa không ít hơn [imath]\left [ \dfrac{n}{m} \right ]+1[/imath] con thỏ.
1.2. Nguyên lí Dirichlet dạng độ đo(hình học)
Giả sử hình [imath](H)[/imath] được chia thành [imath]n[/imath] hình con [imath](H_1),(H_2),...,(H_n)[/imath]. Nếu tổng diện tích [imath]n[/imath] hình con lớn hơn [imath]k\cdot S_{(H)}[/imath] thì tồn tại ít nhất 1 điểm là điểm chung của [imath]k+1[/imath] hình con. Nếu tổng diện tích [imath]n[/imath] hình con nhỏ hơn [imath]k.S_{(H)}[/imath] thì tồn tại ít nhất 1 điểm là điểm chung của không quá [imath]k-1[/imath] hình con.
(Lưu ý nếu hình (H) suy biến thành đoạn thẳng thì nguyên lí đó áp dụng cho "độ dài" thay cho "diện tích").
2. Một số kỹ thuật ứng dụng định lí Dirichlet
2.1. Phân chia tập hợp để tạo các n-tập ("chuồng").
Ví dụ mở đầu. Trong hình vuông có cạnh bằng 1 đặt 51 điểm bất kì phân biệt. Chứng minh có ít nhất 3 trong 51 điểm đó nằm trong đường tròn có bán kính [imath]\dfrac{1}{7}[/imath].
Lời giải. Chia thành 25 hình vuông con có độ dài cạnh bằng 0,2. Khi đó tồn tại một hình vuông con chứa ít nhất 3 điểm (giả sử là M, N, P) trong 51 điểm đó (vì 51 = 2.25 + 1). Giả sử ABCD là hình vuông con đó và I là tâm của nó. Xét hình tròn (C) tâm I, bán kính [imath]R=\dfrac{1}{7}[/imath]. Ta có [imath]IM,IN,IP \leq 0,1\cdot \sqrt{2}<\dfrac{1}{7}[/imath]
Vậy M, N, P nằm trong hình tròn (C).
Vậy M, N, P nằm trong hình tròn (C).
Ví dụ 2. Trong hình tròn có diện tích bằng 8 đặt 17 điểm bất kì sao cho không có 3 điểm nào thẳng hàng. Chứng minh rằng có ít nhất ba điểm tạo thành một tam giác có diện tích nhỏ hơn 1.
HD. Chia đường tròn thành 8 hình quạt bằng nhau như hình vẽ:
Sẽ có 3 điểm nằm trong một hình quạt (giả sử đó là các điểm A, B, C) Khi đó S(ABC) < S(quạt) = 1 (đpcm).
Sẽ có 3 điểm nằm trong một hình quạt (giả sử đó là các điểm A, B, C) Khi đó S(ABC) < S(quạt) = 1 (đpcm).
Lời giải. Chia hình tròn thành 9 phần như hình vẽ (gồm một hình tròn bán kính 1 ở trong và tám “hình thang cong” ở ngoài):
Theo nguyên lí Dirichlet thì có một phần chứa ít nhất hai điểm (giả sử là A và B) trong 10 điểm đã cho. Xét hai trường hợp:
+) Hai điểm A, B nằm trong hình tròn nhỏ: khi đó AB < 2.
+) Hai điểm A, B nằm trong hoặc trên các cạnh của một trong các “hình thang cong” còn lại: Giả sử “hình thang cong” đó là MNPQ. Khi đó xét hình thang MNPQ có: QP < 1; QM = 1,5; PN = 1,5; MN < 2; QN < 2; PM < 2. Do đó khoảng cách giữa hai điểm bất kì thuộc hình thang MNPQ và miền trong của nó đều nhỏ hơn 2.
· Nếu A, B thuộc hình thang MNPQ hoặc miền trong của nó thì ta có đpcm.
· Nếu A, B không nằm hoàn toàn trong hình thang thì lấy trên đoạn OM điểm A’ sao cho OA’ = OA, lấy trên đoạn ON điểm B’ sao cho OB’ = OB. Từ [imath]\widehat{AOB} \leq \widehat{A'OB'},OA=OA',OB=OB'[/imath]suy ra [imath]AB \leq A'B'<2[/imath]
Vậy trong mọi trường hợp thì AB < 2 (đpcm).
Theo nguyên lí Dirichlet thì có một phần chứa ít nhất hai điểm (giả sử là A và B) trong 10 điểm đã cho. Xét hai trường hợp:
+) Hai điểm A, B nằm trong hình tròn nhỏ: khi đó AB < 2.
+) Hai điểm A, B nằm trong hoặc trên các cạnh của một trong các “hình thang cong” còn lại: Giả sử “hình thang cong” đó là MNPQ. Khi đó xét hình thang MNPQ có: QP < 1; QM = 1,5; PN = 1,5; MN < 2; QN < 2; PM < 2. Do đó khoảng cách giữa hai điểm bất kì thuộc hình thang MNPQ và miền trong của nó đều nhỏ hơn 2.
· Nếu A, B thuộc hình thang MNPQ hoặc miền trong của nó thì ta có đpcm.
· Nếu A, B không nằm hoàn toàn trong hình thang thì lấy trên đoạn OM điểm A’ sao cho OA’ = OA, lấy trên đoạn ON điểm B’ sao cho OB’ = OB. Từ [imath]\widehat{AOB} \leq \widehat{A'OB'},OA=OA',OB=OB'[/imath]suy ra [imath]AB \leq A'B'<2[/imath]
Vậy trong mọi trường hợp thì AB < 2 (đpcm).
Lời giải. Gọi K, H, I, J lần lượt là trung điểm của các đoạn thẳng như hình vẽ:
Xét 25 đường thẳng đã cho. Với mỗi đường thẳng đó có một trong hai khả năng sau xảy ra:
+) Đường thẳng đó cắt cạnh AB và CD. Khi đó nó phải đi qua K hoặc H.
+) Đường thẳng đó cắt cạnh AD và BC. Khi đó nó phải đi qua I hoặc J.
Như vậy sẽ có 7 đường thẳng cùng đi qua một trong 4 điểm I, J, K, H nêu trên (đpcm).
Xét 25 đường thẳng đã cho. Với mỗi đường thẳng đó có một trong hai khả năng sau xảy ra:
+) Đường thẳng đó cắt cạnh AB và CD. Khi đó nó phải đi qua K hoặc H.
+) Đường thẳng đó cắt cạnh AD và BC. Khi đó nó phải đi qua I hoặc J.
Như vậy sẽ có 7 đường thẳng cùng đi qua một trong 4 điểm I, J, K, H nêu trên (đpcm).
2.2. Xây dựng n-tập theo đối tượng xuất phát.
Ví dụ mở đầu. Trong mặt phẳng cho 2009 điểm. Biết rằng trong 3 điểm bất kì lấy từ các điểm đã cho luôn có hai điểm có khoảng cách không lớn hơn 1. CMR có 1005 điểm nằm trong hình tròn bán kính 1.
Lời giải. Lấy điểm M trong 2009 điểm đó và xét hình tròn (C) có tâm M, bán kính bằng 1.
+) Nếu tất cả các điểm đều thuộc (C) thì (C) là hình tròn cần tìm.
+) Nếu có điểm N sao cho MN > 1 thì xét hình tròn (C’) có tâm N, bán kính 1. Khi đó với mọi điểm P trong 2007 điểm còn lại luôn xảy ra một trong hai khả năng sau: [imath]PM \leq 1 \Rightarrow P \in (C)[/imath] hoặc [imath]PN \leq 1 \Rightarrow P \in (C')[/imath] (vì AB > 1). Từ 2007 điểm này sẽ có ít nhất 1004 điểm cùng thuộc (C) (hoặc (C’)). Khi đó hình tròn (C) (hoặc (C’)) là hình tròn cần tìm.
+) Nếu tất cả các điểm đều thuộc (C) thì (C) là hình tròn cần tìm.
+) Nếu có điểm N sao cho MN > 1 thì xét hình tròn (C’) có tâm N, bán kính 1. Khi đó với mọi điểm P trong 2007 điểm còn lại luôn xảy ra một trong hai khả năng sau: [imath]PM \leq 1 \Rightarrow P \in (C)[/imath] hoặc [imath]PN \leq 1 \Rightarrow P \in (C')[/imath] (vì AB > 1). Từ 2007 điểm này sẽ có ít nhất 1004 điểm cùng thuộc (C) (hoặc (C’)). Khi đó hình tròn (C) (hoặc (C’)) là hình tròn cần tìm.
Nhận xét. Trong ví dụ trên, việc chọn ra các n - tập được bắt đầu từ việc chọn ra một “đối tượng xuất phát” là điểm M. Từ “đối tượng xuất phát” này ta lập luận để suy ra các đối tượng (trường hợp) còn lại ... Đây là một kĩ thuật hay dùng trong các bài toán sử dụng nguyên lí Đirichlet.
Ví dụ 2. Trong mặt phẳng cho 9 đường thẳng song song nằm ngang và 3 đường thẳng song song nằm dọc. Người ta đánh dấu các giao điểm của các đường thẳng này bởi hai màu xanh (X) và đỏ (Đ). CMR tồn tại 2 đường thẳng nằm ngang và 2 đường thẳng nằm dọc sao cho 4 giao điểm của chúng được tô cùng màu.
Lời giải. Xét 3 giao điểm đầu của các đường thẳng nằm ngang. Trên mỗi đường thẳng này có 23 cách tô màu 3 giao điểm đầu. Có 9 đường thẳng nằm ngang với 23 = 8 cách tô màu nên có hai đường thẳng có cùng cách tô màu 3 điểm đầu tiên. Trên hai đường đó thì trong 3 cách tô màu phải có hai màu trùng nhau nên ta có đpcm.
HD. Có ít nhất 6 điểm tô cùng màu, giả sử là A, B, C, D, E, F. Xét 5 dây cung AB, AC, AD, AE, AF sẽ có ít nhất 3 dây cùng màu, giả sử đó là màu T.
Không mất tính tổng quát giả sử AB, AC, AD cùng màu T. Khi đó:
Nếu BC màu T thì kết thúc bài toán; nếu BC màu L thì xét CD:
Nếu CD màu T thì kết thúc; nếu CD màu L thì xét BD:
Nếu BD là T thì kết thúc; nếu BD màu L thì tam giác BCD có ba cạnh cùng màu L và 3 đỉnh B, C, D cùng màu bài toán kết thúc.
Không mất tính tổng quát giả sử AB, AC, AD cùng màu T. Khi đó:
Nếu BC màu T thì kết thúc bài toán; nếu BC màu L thì xét CD:
Nếu CD màu T thì kết thúc; nếu CD màu L thì xét BD:
Nếu BD là T thì kết thúc; nếu BD màu L thì tam giác BCD có ba cạnh cùng màu L và 3 đỉnh B, C, D cùng màu bài toán kết thúc.
Nhận xét: Nếu có hai dây cung (được tạo thành từ 1981 đỉnh của đa giác) có độ dài bằng nhau và không có đỉnh chung thì ta sẽ có một hình thang.
Xét độ dài các dây cung A1A2, A1A3,…, A1A1981. Ta thấy A1A2 = A1A1981, A1A3 = A1A1980,…, A1A991 = A1A992 và các độ dài này đôi một khác nhau. Vậy có 990 độ dài các dây cung có một đỉnh là A1 và đó cũng là tất cả các độ dài của các dây cung được tạo thành từ 1981 điểm đã cho.
Trong 64 đỉnh sẽ có [imath]\dfrac{64\cdot 63}{2}=2016[/imath]dây cung. Vì có 990 độ dài suy ra có ít nhất 3 dây cung có cùng độ dài. Nếu các dây cung này đều đôi một có đỉnh chung thì sẽ tạo thành một tam giác đều (vì chỉ có đúng 2 dây cung chung đỉnh có cùng độ dài) như hình vẽ:
View attachment 184882
Khi đó đường tròn sẽ được chia ra thành 3 cung bằng nhau suy ra số đỉnh của đa giác phải là số nguyên lần của 3, điều này là vô lí vì 1981 không chia hết cho 3. Vậy trong 3 dây cung có cùng độ dài này có ít nhất hai dây cung không có chung đỉnh, hai dây cung đó tạo thành một hình thang cân có 4 đỉnh là 4 đỉnh của đa giác ban đầu.
Xét độ dài các dây cung A1A2, A1A3,…, A1A1981. Ta thấy A1A2 = A1A1981, A1A3 = A1A1980,…, A1A991 = A1A992 và các độ dài này đôi một khác nhau. Vậy có 990 độ dài các dây cung có một đỉnh là A1 và đó cũng là tất cả các độ dài của các dây cung được tạo thành từ 1981 điểm đã cho.
Trong 64 đỉnh sẽ có [imath]\dfrac{64\cdot 63}{2}=2016[/imath]dây cung. Vì có 990 độ dài suy ra có ít nhất 3 dây cung có cùng độ dài. Nếu các dây cung này đều đôi một có đỉnh chung thì sẽ tạo thành một tam giác đều (vì chỉ có đúng 2 dây cung chung đỉnh có cùng độ dài) như hình vẽ:
View attachment 184882
Khi đó đường tròn sẽ được chia ra thành 3 cung bằng nhau suy ra số đỉnh của đa giác phải là số nguyên lần của 3, điều này là vô lí vì 1981 không chia hết cho 3. Vậy trong 3 dây cung có cùng độ dài này có ít nhất hai dây cung không có chung đỉnh, hai dây cung đó tạo thành một hình thang cân có 4 đỉnh là 4 đỉnh của đa giác ban đầu.
Luyện tập:
Chứng minh trong 1007 số nguyên dương phân biệt không vượt quá 2011 luôn chọn được ra 2 số sao cho tổng của chúng bằng 2012.
Xét 100 số nguyên dương bất kỳ có tổng là 101. Chứng minh ta có thể chọn trong chúng một vài số sao cho có tổng bằng 100.
Cho 100 số tự nhiên bất kỳ. Chứng minh ta luôn chọn được 1 số số có tổng chia hết 100.
Các số từ 1 đến 200 được chia thành 50 tập hợp. Chứng minh tồn tại 1 tập hợp có 3 số là độ dài 3 cạnh của tam giác.
!!!
Bất ngờ không =)) Chúc mừng bạn đã tìm ra gợi ý của chúng mình nhé ^^
Gợi ý của bạn là: [imath]1,1,2,3,5,\cdots[/imath]
Last edited:
