NGUYÊN LÍ DIRICHLE

Chia sẻ: Võ Huệ Thi | Ngày: | Loại File: DOC | Số trang:16

Thêm vào BST

Báo xấu

249
lượt xem 58
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Điều mà chúng tôi sắp trìn bày với các bạn dưới đây, chắc hẳn đã quá quen thuộc đối với các bạn. Đó là nguyên lí Dirichle, vấn đề mà các bạn đã học ở THCS, có lẽ nó làm bạn chán vì bạn đã đọc qua nhiều lần hay là độ khó của các bài toán áp dụng nguyên lí này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: NGUYÊN LÍ DIRICHLE

NGUYÊN LÍ DIRICHLE Điều mà chúng tôi sắp trình bày với các bạn dưới đây, ch ắc hẳn đã quá quen thuộc đối với các bạn. Đó là nguyên lí Dirichle, vấn đề mà các bạn đã học ở THCS, có lẽ nó làm bạn chán vì bạn đã đọc qua nhi ều l ần hay là độ khó của các bài toán áp dụng nguyên lí này. Nh ưng đ ừng vội g ập sách lại, hãy lướt qua nó, bạn sẽ thấy mọi vấn đề sẽ trở nên đơn giản cũng như “hiệu quả đến bất ngờ” của nó trong nhiều loại toán. Trước hết chúng ta nhắc lại nguyên lí Dirichle Nguyên lí Dirichle “Nếu nhốt n + 1 con thỏ vào n cái chuồng ( n ∈ ¥ ∗ ), luôn có (ít nhất là) hai hai con thỏ bị nhối trong cùng một chuồng”. Nguyên lí Dirichle dạng tổng quát “Nếu nhốt m con thỏ vào n cái chuồng ( m, n ∈ ¥ ∗ ), luôn tồn tại  m − 1 một chuồng chứa ít nhất 1 +  con thỏ. n  Trong đó, kí hiệu [ α ] chỉ phần nguyên của số thực α tức là số nguyên lớn nhất không vượt quá α . Chứng minh: Sử dụng phương pháp phản chứng Ta giả sử ngược lại, mỗi chuồng nhốt không quá một con th ỏ thì t ổng s ố con thỏ sẽ không quá n con. Mâu thuẩn với giả thiết là số thỏ là n + 1 . Bây giờ chúng ta cùng tìm hiểu một vài ứng dụng của nguyên lí Dirichle. Ở đây, chúng tôi chia các ví dụ thành bốn dạng toán: _ Phân chia tập hợp để tạo ra các n – tập _ Xây dựng các n – tập theo đối tượng xuất phát _ Xây dựng các dãy số _ Xây dựng bảng
2 mỗi dạng là một phương pháp giải nhằm giúp các bạn hiểu sâu h ơn v ề vấn đề này cũng như tiến tới giải những bài toán khó. Dạng 1: phân chia tập hợp để tạo các n – tập 1. Phương pháp: chia một đối tượng lớn thành nhiều đối tượng nhỏ. Sau đó áp dụng nguyên lí Dirichle cho các đối tượng nhỏ đó. Ví dụ 1. Trong hình vuông có cạnh bằng 1 đặt 51 điểm bất kì phân biệt. 1 Chứng minh rằng có ít nhất 3 trong 51 điểm đó nằm trong hình tròn ( r = 7 ). Giải Chia hình vuông đã cho 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) 1 trong 51 điểm đó. Gọi I là tâm của nó. Xét hình tròn (I, r = ). 7 1 Ta có IM, IN, IP ≤ 0,1. 2 < . (đpcm) 7 Ví dụ 2. Cho hình bình hành ABCD và 25 đường thẳng. Mỗi đ ường th ẳng 1 chia ABCD thành hai hình thang với tỉ số diện tích là . Chứng minh rằng 3 trong 25 đường thẳng đó có 7 đường thẳng đồng quy. Giải Gọi M, N, P, Q, K, H, I, J lần l ượt là trung đi ểm c ủa các đo ạn th ẳng nh ư hình vẽ: M A B I Q K O H N J D P C
3 Theo đề bài, 25 đường thẳng chia hình bình hành thành hai hình thang có t ỉ 1 số diện tích . Vậy tất cả đường thẳng phải đi qua một trong 4 điểm: I, 3 K, H, J. Thật vậy, cho hai đường thẳng bất kì lần l ượt c ắt AB, CD t ại X, Y và cắt AD, BC tại Z, T. Với 6 trung điểm, ta có QK là đ ường trung bình của hình thang AZTD, KN là đường trung bình của hình thang ZBCT và đường cao AH của hình bình hành. ( ZB + CT ) .AH S ZBCT = = KN . AH 2 Ta luôn có: ( AZ + TD ) .AH = QK .AH = S AZTD 2 S QK 1 = = . (đpcm) AZTD Tỉ số diện tích: S KN 3 ZBCT Khi đó 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 nên nó phải đi qua K hoặc H. _ Đường thẳng đó cắt cạnh AD và BC nên nó phải đi qua I hoặc J. Như vậy có ít nhất 7 đường thẳng cùng đi qua một trong 4 điểm I, J, K, H. Ví dụ 3. Cho tam giác đều ABC có cạnh bằng 1. Đánh dấu 5 đi ểm phân biệt bất kỳ trong tam giác ABC. Chứng minh rằng tồn tại ít nhất là 2 điểm trong số đó mà khoảng cách giữa chúng nhỏ hơn 0,5. Giải Các đường trung bình của VABC chia nó thành bốn tam giác đều có cạnh là 0,5. Theo nguyên tắc Dirichle, tồn tại ít nhất là 2 đi ểm rơi vào m ột trong bốn tam giác nhỏ. Ta có khoảng cách giữa hai đi ểm này nh ỏ h ơn 0,5.
4 A B C 2. Dạng 2: Xây dựng các n – tập theo đối tượng xuất phát Ví dụ 4. 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 nh ỏ hơn 1. Chứng minh rằng có ít nhất 1005 điểm nằm trong hình tròn bán kính 1. Giải Lấy điểm M trong 2009 điểm đó và xét hình tròn (M, R = 1 ). _ Nếu tất cả các điểm đều thuộc (M) thì (M) là hình tròn cần tìm. _ Nếu có điểm N sao cho MN ≥ 1, khi đó xét hình tròn (N, r = 1 ). Vậy với mọi điểm P trong 2007 điểm còn lại, luôn xảy ra một trong hai  PM < 1 ⇒ P ∈ ( M ) (Vì MN ≥ 1 ) khả năng sau:   PN < 1 ⇒ P ∈ ( N )  Nên từ 2007 điểm này sẽ có ít nhất 1004 điểm cùng thuộc (M) hoặc (N) Vậy với 1004 điểm cùng với tâm của một trong hai đường tròn, chúng ta có 1005 điểm cần tìm. Phương pháp: Trong ví dụ trên, để chọn ra các n – tập, ta 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 ví uất phát”, ta lập luận để suy ra các đối tượng tiếp theo. x Ví dụ 5. Cho 5 điểm phân biệt nằm bên trong hình vuông ABCD có c ạnh là 35 + 3. Chứng minh rằng có thể tìm được ít nhất một điểm trong hình vuông đã cho sao cho, khoảng cách từ nó đến 5 điểm đã cho lớn hơn 10. Giải Gọi K, I lần lượt là trung điểm của các cạnh AB và CD. Trên đoạn KI lấy điểm M và N sao cho: KM = NI = 8
5 Ta có: MN = KI − KM − NI = 35 + 3 − 16 = 19 + 3 AM = BM = DN = CN Còn 2  35 + 3  =  2 ÷ + 8 > 20 2 ÷   Do đó nếu ta vẽ các đường tròn có tâm A, B, C, D, M, N bán kính 10 thì các đường tròn này không cắt nhau. Bởi vì chỉ có 5 điểm phân biệt nằm trong hình vuông, do đó t ồn t ại ít nh ất là một hình tròn không chứa điểm nào trong số 5 điểm đã cho. Nhận thấy, tâm của đường tròn này có khoảng cách tới 5 đi ểm đã cho l ớn hơn 10. B K A M N D I C Ví dụ 6. Trên mặt phẳng cho 100 điểm phân biệt bất kỳ. Nối m ỗi đi ểm với ít nhất 66 điểm trong số 99 điểm còn lại bằng một đoạn th ẳng. Chứng minh rằng có thể xảy ra trường hợp có 2 điểm trong số 4 điểm bất kỳ của 100 điểm đã cho không được nối với nhau. Giải Gọi các điểm đã cho là A1 , A2 , A3 ,..., A100 M = { A1 , A2 , A3 ,..., A33 } Kí hiệu: N = { A34 , A35 ,..., A66 } P = { A67 , A68 ,..., A100 } . Tập M gồm 33 điểm, tập N gồm 33 điểm và tập P g ồm 34 đi ểm. Tr ường hợp của bài toán; yêu cầu chứng minh có thể xảy ra nếu như:
6 Mỗi điểm trong tập hợp M chỉ được nối với các điểm của tập h ợp N hoặc P. Các điểm của tập hợp N chỉ được nối với các điểm của t ập h ợp P hoặc M. Các điểm của tập hợp P chỉ được nối với các đi ểm có trong t ập h ợp M hoặc tập hợp N (2 tập này gồm 66 điểm). Thật vậy, giả sử ( Ai , Aj , Ak , Al ) là 4 điểm bất kỳ trong số 100 điểm. Theo nguyên tắc Dirichle tồn tại ít nhất là 2 điểm cùng thuộc 1 tập hợp (M, N hoặc P). Do đó với cách phân chia trên đây, 2 điểm này không được nối với nhau. Ví dụ 7. Cho đa giác đều gồm 1999 cạnh. Người ta sơn các đỉnh của đa giác bằng 2 màu xanh và đỏ. Chứng minh rằng phải tồn tại 3 đỉnh được sơn cùng một màu tạo thành một tam giác cân. Giải Ta có đa giác 1999 cạnh nên có 1999 đỉnh. Do đó phải tồn tại 2 đỉnh k ề nhau là P và Q được sơn bởi cùng một màu – màu đỏ (Theo nguyên t ắc Dirichle). Vì đa giác đã cho là đa giác đều có số đỉnh lẻ, nên phải tồn tại một đỉnh nào đó nằm trên đường trung trực của đoạn thẳng PQ. Giả sử đỉnh đó là A. Nếu A tô màu đỏ thì ta có VAPQ là tam giác cân có 3 đỉnh A, P, Q được tô cùng màu đỏ. Nếu A tô màu xanh. Lúc đó gọi B và C là các đ ỉnh khác c ủa đa giác k ề với P và Q. Nếu cả 2 đỉnh B và C được tô màu xanh thì VABC cân và có 3 đỉnh cùng tô màu xanh. Nếu ngược lại, một trong hai đỉnh B và C mà tô màu đỏ thì tam giác BPQ hoặc tam giác CPQ là các tam giác cân có 3 đỉnh được tô màu đỏ. Bài tập ứng dụng: Trong hình vuông có các cạnh bằng 1 có 101 điểm tùy ý, 1. chứng minh rằng có ít nhất 5 điểm nằm trong hình tròn bán kính 1/7. Cho 9 điểm bất kì nằm trong hình vuông đơn vị. Ch ứng minh 2. rằng tìm được 3 điểm lập thành một tam giác có diện tích nhỏ hơn hay 1 bằng . 8
7 Cho đường tròn có bán kính 1 và n điểm A1 , A2 ,..., An trên mặt 3. phẳng. Chứng minh rằng trên đường tròn có thể tìm được điểm M sao cho MA1 + MA2 + ... + MAn ≥ n. Trên mặt phẳng cho 5 điểm có tọa độ nguyên, trong đó không 4. có ba điểm nào thẳng hàng. Chứng minh rằng trong số các tam giác được tạo thành từ 5 điểm trên, có ít nhất ba tam giác có diện tích nguyên. Trên đường tròn cho 16 điểm được tô bởi một trong ba màu: 5. xanh, đỏ, vàng. Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi hai màu: tím, đen. Chứng minh rằng ta luôn có 3 trong 16 điểm trên được tô cùng màu và 3 dây cung nối chúng cũng được tô cùng màu. Cho 17 điểm nằm trong mặt phẳng, trong đó không có 3 6. điểm nào thẳng hàng. Nối các điểm này lại bằng các đoạn thẳng và tô màu xanh, đỏ hoặc vàng. Chứng minh rằng tồn tại một tam giác có các cạnh cùng màu. Trên bàn cờ 10 ×10 , người ta viết các số từ 1 đến 100. Mỗi 7. hàng chọn ra số lớn thứ ba. Chứng minh rằng tồn tại một hàng có tổng các số trong hàng đó nhỏ hơn tổng các số thứ ba được chọn. Trong mặt phẳng cho 6 hình tròn sao cho tâm của mỗi hình 8. tròn nằm ngoài tất cả các hình tròn khác. Chứng minh rằng không có điểm nào chung cho cả 6 hình tròn đó. Chứng minh rằng trong một hình tròn bán kính 1 không th ể 9. chọn nhiều hơn 5 điểm có khoảng cách giữa hai điểm bất kì trong chúng đều lớn hơn 1. Trên mặt phẳng cho 2005 điểm sao cho không có ba đi ểm 10. nào thẳng hàng. Xét tất cả các đoạn thẳng nối các cặp điểm trong số 2005 điểm này. Chứng minh rằng với mỗi đường thẳng ∆ không đi qua bất kì điểm nào trong số các điểm nói trên thì số đoạn thẳng bị ∆ cắt là một số chẵn. Trên mặt phẳng cho 100 hình tròn có bán kính đôi một phân 11. biệt thỏa mãn các điều kiện sau: Không có hai hình tròn nào rời nhau cùng nằm trong i) một hình tròn khác. Nếu hai hình tròn có phần chung thì hình tròn lớn ii) chứa hình tròn bé. Với 10 hình tròn bất kì trong số đang xét luôn tồn tại iii) một cặp hình tròn mà hình tròn lớn chứa hình tròn bé. Chứng minh rằng tồn tại 12 hình tròn A1 ,...., A12 trong số trên sao Ai nằm trong Ai +1 , i = 1, 2,...,11.
8 Trên mặt phẳng cho 20 điểm phân biệt. Người ta nối một số 12. cặp điểm trong số 20 điểm này lại với nhau, sao cho với ba điểm bất kì trong chúng có ít nhất 2 điểm không được nối với nhau. Ch ứng minh rằng số đoạn thẳng không vượt quá 100. Trong mặt phẳng cho một đa giác lồi 2006 cạnh. Xét tất cả 13. các tam giác có các đỉnh là đỉnh của đa giác đã cho. Một điểm P của mặt phẳng không nằm trên bất kì cạnh nào của đa giác đó. Chứng minh rằng số tam giác đang xét chứa điểm P ở trong là một số chẵn. Bên trong một đa giác lồi có một số điểm phân biệt. Chứng 14. minh rằng có thể chia đa giác này thành những đa giác lồi nh ỏ mà m ỗi chúng chứa một điểm trong số đã cho. Cho hữu hạn hình vuông. Chứng minh rằng có th ể cắt mỗi 15. hình vuông thành hữu hạn mảnh sao cho từ các mảnh nhận được ta có th ể ghép lại thành một hình vuông. Cho một số hình tròn không giao nhau, chiếm trên mặt phẳng 16. một diện tích bằng đơn vị. Chứng minh rằng trong số đó có thể chọn ra một hình tròn hoặc một số hình tròn đôi một không giao nhau mà di ện tích tổng cộng của chúng không nhỏ hơn 1/9. Chứng minh rằng 6 đường tròn cắt nhau tại một điểm, thì ít 17. nhất một trong chúng chứa tâm của một đường tròn khác. Bài tập chọn lọc Trong hình vuông mà độ dài mỗi cạnh là 4 cho trước 33 điểm 1. phân biệt, trong đó không có 3 điểm nào thẳng hàng. Người ta vẽ các đường tròn có bán kính đều bằng 2 , có tâm là các điểm đã cho. Hỏi có hay không 3 điểm trong số các điểm nói trên sao cho chúng đều thuộc các phần chung của 3 hình tròn có các tâm cũng chính là 3 đi ểm đó? (THI CHỌN HSG 9 QUỐC GIA 1995 – 1996. BẢNG A) Giải Chia hình vuông đã cho thành 16 hình vuông, mỗi hình vuông có cạnh là 1; vì có 33 điểm chứa trong 16 hình vuông, do đó theo nguyên t ắc Dirichle tồn tại ít nhất là một hình vuông chứa không ít hơn 3 điểm. Khoảng cách giữa hai điểm bất kỳ trong hình vuông đơn v ị đã cho không thể vượt qua độ dài đường chéo của nó bằng 2. Gọi O1, O2, O3 là 3 điểm nằm trong một hình vuông đơn vị nào đó. Vẽ 3 đường tròn tâm O1, O2, O3 cùng bán kính là 2. Chắc chắn cả ba điểm O1, O2, O3 đều nằm trong cả ba đường tròn này, nghĩa là chúng n ằm trong phần chung của 3 hình tròn có tâm tại chính các điểm O1, O2, O3.
9 Cho hình vuông ABCD và chín đường thẳng phân biệt thỏa 2. mãn mỗi một đường thẳng đều chia hình vuông thành hai tứ giác có diện tích tỉ lệ 2 : 3 . Chứng minh rằng tồn tại ít nhất là ba đường th ẳng đ ồng qui t ại m ột điểm. Giải • Nhận xét: các đường thẳng đã cho không thể đi qua trung điểm các cạnh hình vuông ABCD bởi vì ngược lại thì hình vuông sẽ bị phân thành hai phần tam giác và ngũ giác. Giả sử một đường thẳng trong số đó cắt cạnh BC tại M và cắt cạnh AD tại N Các hình thang ABMN và CDNM có chiều cao bằng nhau nên từ giả thiết suy ra MN chia đoạn thẳng nối trung điểm P, Q của AB và CD theo tỉ lệ 2:3. Dễ thấy chỉ có 4 điểm chia 2 đường trung bình của hình vuông ABCD theo tỉ lệ 2:3 là I, J, K, H. Có 9 đường th ẳng đi qua 4 đi ểm này; theo nguyên tắc Dirichle tồn tại ít nhất là 3 đường thẳng đi qua một điểm. B C M C D H K I I J A D N A B Các điểm trên mặt phẳng được tô bằng một trong ba màu: 3. xanh, đỏ, vàng. Chứng minh rằng tồn tại ít nhất là 2 đi ểm đ ược tô b ởi cùng một màu mà khoảng cách giữa chúng bằng 1. Giải Dựng (O, 3 ). P là một điểm thuộc (O, 3 ). Dựng hình thoi OAPB có đường chéo OP, cạnh 1. 3 Gọi I là giao điểm 2 đường chéo, ta có OI = . 2
10 2  3 1 ⇒ AI = AO − OI = 1 −   2 ÷ =4 2 2 2 ÷   1 ⇒ AI = ⇒ AB = 1. 2 Vậy VAOB đều có cạnh bằng 1. Giả sử ngược lại, mọi cặp hai điểm có khoảng cách giữa chúng bằng 1 mà đều được tô bằng hai màu khác nhau. Không mất tổng quát, ta giả sử các điểm O, A, B lần lượt được tô bằng màu xanh, màu đỏ, màu vàng. Bởi vì PA = PB = 1 ⇒ P phải được tô bằng màu xanh. Với cách lập luận như vậy ta suy ra, tất cả các điểm trên đường tròn (O, 3 ) đều được tô bằng màu xanh. Mặt khác dễ dàng tìm được trên (O, 3 ) hai điểm mà khoảng cách giữa chúng bằng 1, nên theo giả sử chúng được tô bằng hai màu khác nhau. Vô lí. Điều vô lí đó chứng tỏ có hai điểm được tô cùng một màu mà khoảng cách giữa chúng bằng 1. O A B P Mỗi điểm của mặt phẳng được tô bằng một trong hai màu 4. xanh và đỏ. Chứng minh rằng có thể tìm được ít nh ất là ba đi ểm đ ược tô bởi cùng một màu tạo thành một tam giác đều có cạnh là 1 hoặc 3. Giải Dựng một tam giác đều có cạnh bằng 1. Nếu cả ba đỉnh được tô bởi cùng một màu (xanh hoặc đỏ) thì bài toán được chứng minh.
11 Trong trường hợp ngược lại, xét tam giác đều ABC có cạnh AB = 1 mà A và B được tô bằng hai màu khác nhau. Lấy điểm D của mặt phẳng sao cho AD = BD = 2. Vì A, B khác màu nên D cùng màu với chỉ một trong hai điểm A hoặc B. ⇒ Tồn tại đoạn thẳng AD = 2 hoặc BD = 2 có hai mút được tô bằng hai màu khác màu. Giả sử là đoạn thẳng AD. Gọi K là trung đi ểm c ủa đoạn thẳng AD thì K cùng màu với một trong hai đi ểm A ho ặc D. Gi ả s ử K và A có cùng màu xanh. Vẽ các tam giác đều APK và AQK. Nếu P hoặc Q có màu xanh thì ta có tam giác đ ều APK ho ặc AQK có cạnh bằng 1 và ba đỉnh được bằng cùng màu xanh. Nếu P và Q có màu đỏ thì tam giác PQD có 3 đỉnh được tô cùng màu đỏ. Dễ thấy tam giác PQD đều có cạnh là 3. P A K D Q Bên trong đường tròn có bán kính là 2000 có 8000 đoạn thẳng 5. có độ dài là 1. Chứng minh rằng có thể dựng được một đường th ẳng d hoặc là song song hoặc là vuông góc với một đương thẳng l cho trước, sao cho d cắt ít nhất là hai đoạn thẳng đã cho. Giải
12 Giả sử xy là một đường thẳng bất kỳ vuông góc với l. Ta đánh dấu các đoạn thẳng theo thứ tự 1, 2, 3,…, 8000. Chiếu các đoạn thẳng này lên hai đường thẳng xy và l. Kí hiệu ai và bi ( i = 1, 2,...,8000 ) tương ứng là độ dài của các đoạn thẳng đã cho trên hai đường thẳng xy và l. Ta có: ai + bi ≥ 1 với mọi i = 1, 2,...,8000 8000 8000 ∑ ai + ∑ bi ≥ 8000 = 4000 + 4000 Do đó i =1 i =1 hoặc là a1 + a2 + ... + a8000 ≥ 4000 Suy ra hoặc là b1 + b2 + ... + b8000 ≥ 4000. Ta có 8000 đoạn thẳng có thể chiếu vuông góc lên đường kính của đường tròn với độ dài là 4000. Nếu các hình chiếu của các đoạn thẳng đã cho lên đường thẳng l mà không có các điểm chung thì ta có: a1 + a2 + ... + a8000 < 4000 Vì vậy trên l tìm được một điểm là hình chiếu của các điểm thuộc ít nhất là hai trong số các đoạn thẳng đã cho Khi đó đường thẳng vuông góc với l dựng qua điểm này sẽ có điểm chung với ít nhất hai đoạn thẳng trong số 8000 đoạn thẳng đã cho. Cho 6 điểm trong mặt phẳng sao cho bất kì 3 đi ểm nào cũng 6. là đỉnh của một tam giác có các cạnh có chiều dài khác nhau. Ch ứng minh rằng tồn tại một cạnh vừa là cạnh nhỏ nhất của một tam giác vừa là cạnh lớn nhất của một tam giác khác. Giải Ta tô màu đỏ cạnh nhỏ nhất của một tam giác và tô màu xanh hai cạnh còn lại. Ta chứng minh tồn tại một tam giác có các cạnh cùng màu đỏ. Từ điểm A trong 6 điểm đã cho, nối với 5 điểm còn l ại, ta đ ược 5 cạnh, trong 5 cạnh này ít nhất có 3 cạnh cùng màu, giả s ử là c ạnh AB, AC, AD. Nếu AB, AC, AD cùng màu đỏ: VBCD có một cạnh màu đỏ, giả sử đó là BC. Khi đó ta có VABC có các cạnh cùng màu đỏ. Nếu AB, AC, AD cùng màu xanh: VBCD có các cạnh cùng màu đỏ. Với tam giác có ba cạnh cùng màu đỏ thì cạnh lớn nh ất của tam giác là cạnh cần tìm. Trong hình vuông mà độ dài mỗi cạnh bằng 4 có cho trước 7. 33 điểm, trong đó không có 3 điểm nào thẳng hàng. Người ta vẽ các đường tròn có bán kính đều bằng 2 có tâm là các điểm đã cho.
13 Giải Chia hình vuông đã cho thành 16 hình vuông có cạnh là 1. Do có 33 điểm được chứa trong 16 hình vuông nên theo nguyên tắc Dirichle, ít nhất có một hình vuông chứa không ít hơn 3 điểm ( 33 = 2.16 + 1 ). Khoảng cách giữa hai điểm bất kì trong hình vuông đơn vị không vượt quá đường chéo của nó, nghĩa là không lớn hơn 2. Gọi O1 , O2 , O3 là ba điểm cùng nằm trong một hình vuông đơn vị, có thể rơi vào cạnh hình vuông. Vẽ 3 đường tròn tâm O1 , O2 , O3 bán kính 2 , nên chắc chắn 3 điểm O1 , O2 , O3 đều nằm trong phần chung của ba đường tròn có tâm chính là các điểm O1 , O2 , O3 . A B D C Cho đa giác lồi có 8 cạnh. Chứng minh rằng có ít nh ất hai 8. đường chéo của đa giác song song hoặc góc nhọn giữa chúng không lớn hơn 90. Giải 8 ( 8 − 3) Số đường chéo của đa giác lồi 8 cạnh: = 20. 2 Nếu đa giác không có hai đường chéo nào song song, ta chọn đi ểm P tùy ý trong mặt phẳng. Qua P kẻ 20 đường thẳng tương ứng song song với 20 đường chéo của đa giác ta được 40 góc liên tiếp đỉnh P. Vì tổng các góc này bằng 3600 nên tồn tại ít nhất một góc có số đo không vượt quá 3600 = 90. 40 Trên mặt phẳng cho 2005 điểm phân biệt. Chứng minh rằng 9. tồn tại một đường tròn sao cho trong số 2005 điểm nói trên có 1000 đi ểm nằm phía trong đường tròn, các điểm còn lại nằm phía ngoài đường tròn. Giải
14 Giả sử các điểm đã cho là A1 , A2 ,..., A2005 . Xét tất cả các đường trung trực của các đoạn nối hai điểm bất kì trong số 2005 điểm này. Lấy O là m ột điểm không nằm trên bất kì đường trung trực nào trong số nói trên. Khi đó các khoảng cách từ O tới các điểm A1 , A2 ,..., A2005 đôi một phân biệt. Không mất tổng quát, giả sử OA1 < OA2 < ... < OA2005 . Lấy R sao cho OA1000 < R < OA1001. Khi đó đường tròn (O; R) thỏa mãn bài toán. Trong mặt phẳng kẻ 2004 đường thẳng sao cho không có ba 10. đường nào đồng quy. Tam giác tạo bởi ba đường thẳng trong số các đường thẳng đã cho được gọi là “tam giác xanh” nếu nó không bị đường thẳng nào trong số các đường thẳng còn lại cắt. a) Chứng minh rằng số tam giác xanh không ít hơn 668. b) Chứng minh rằng số tam giác xanh không ít hơn 1336. Giải a) Lấy một đường thẳng d bất kì trong số 2004 đường th ẳng đã cho. Xét một cặp đường thẳng a và b trong số 2003 đường thẳng còn lại có khoảng cách từ giao của a và b tới d là bé nh ất (so v ới các kho ảng cách từ giao của các cặp đường thẳng khác tới d). Ba đ ường th ẳng a, b, d gi ới hạn cho ta một tam giác xanh. Vậy với mỗi đường th ẳng d trong s ố 2004 đường thẳng, ta nhìn ra một tam giác xanh, tuy nhiên theo cách này m ỗi tam giác xanh được tính ba lần. Do đó số các tam giác xanh không ít hơn 2004 : 3 = 668. b) Theo cách làm ở câu a), nếu về hai phía của đường thẳng d đều có các giao điểm của các cặp đường thẳng khác thì ứng với d có hai tam giác xanh nằm về hai phía của d Ta sẽ chứng minh rằng có không quá hai đường thẳng mà tất cả các giao điểm của các cặp đường thẳng khác nằm về cùng một phía so với đường thẳng đó. Thật vậy, giả sử có ba đường thẳng d1 , d 2 , d 3 như vậy. Xét đường thẳng thứ tư d 4 . Gọi M 1 , M 2 , M 3 là giao của d 4 với d1 , d 2 , d 3 . Giả sử M 2 ở giữa M 1 và M 3 . Khi đó M 1 và M 3 nằm về hai phía của d 2 : vô lí. Như vậy ứng với 2004 đường thẳng sẽ có ít nhất ( 2002 × 2 + 2 × 2 ) : 3 tam giác xanh. Do đó số tam giác xanh không ít hơn 1336. Giả sử M là một đa giác lồi. Ta kí hiệu s là số bé nh ất các 11. hình tròn bán kính 1 phủ miền đa giác M, t là s ố l ớn nh ất các hình tròn đôi một rời nhau có đường kính 1 và có tâm thuộc miền đa giác. Ch ứng minh rằng s ≤ t. Giải Giả sử các hình tròn lần lượt có tâm A1 ,...., At thuộc miền đa giác, có đường kính bằng 1 và đôi một rời nhau.
15 Xét t hình tròn ( A1 ; 1), …, ( At ; 1). Rõ ràng t hình tròn này phủ kín miền đa giác M. Thật vậy, nếu trái lại, khi đó t ồn t ại m ột đi ểm At +1 thuộc miền đa giác nhưng không thuộc bất kì hình tròn nào trong s ố v ừa nói. Ta có At +1 Ai > 1, ∀i = 1, 2,..., t. Vậy ( t + 1) hình tròn có đường kính bằng 1 có tâm tại A1 ,..., At +1 đôi một rời nhau và có các tâm thuộc miền đa giác M. Đi ều này trái với giả thiết t là số lớn nhất. Vậy t hình tròn ( A1 ; 1), …, ( At ; 1) phủ kín miền đa giác M. Do s là số bé nhất nên ta đạt được s ≤ t. Cho A là tập hợp điểm trên đường tròn sinh ra bởi m ột đi ểm 12. chuyển dịch liên tiếp (theo chiều kim đồng hồ) trên đường tròn một cung 1 radian. Chứng minh một cung bất kì trên đường tròn đều chứa nh ững điểm thuộc A. Giải 2π Ta lấy một cung bất kì PP2 . Ta có thể lấy cung này P1 P2 = , ở đây 1 m m là số tự nhiên. Ta dựng các điểm sao cho chúng chia đường tròn thành m cung bằng nhau. Ta lấy điểm nào đó Q0 ∈ A và kí hiệu Qn là điểm ảnh của Q0 sau khi ta chuyển liên tiếp n radian. Ta sẽ chứng minh rằng tập hợp điểm A = { Q0 , Q1 ,..., Qn ,...} là vô hạn. Thật vậy, nếu ngược lại, thì tồn tại hai ch ỉ s ố s và t sao cho Qs = Qt . Nếu s < t thì suy ra điểm Qs dịch chuyển về chính mình sau phép lặp s – t. Nh ư t−s vậy cả vòng tròn có 2π radian, nghĩa là π = . Điều này trái với tính chất 2 số π là một số vô tỉ. Như vậy A ( Q0 ) là tập hợp vô hạn điểm. Nhưng các cung P P2 , P2 P3 ,..., Pm P hữu hạn và phủ toàn bộ đường tròn, thì tồn tại một cung 1 1 nào đó Pk Pk +1 chứa ít nhất hai điểm Qs và Qt ∈ A ( Q0 ) . Như vậy độ dài của 2π . Như lí luận phần trên, Qs ≠ Qt , nghĩa là α ≠ 0. Bây cung QsQt bằng α < m giờ ta xét các dãy điểm R0 = Qs , R1 = Qt ,..., Rn = Qs + n( t − s ) ,.... thuộc A ( Q0 ) . Với mọi n cung Rn Rn +1 nhận được từ cung R0 R1 = Qs Qt lặp lại chuyển dịch 2π n ( t − s ) radian. Suy ra cung Rn Rn +1 = α . Dễ thấy với n > , cung α Ro R1 , R1 R2 , R2 R3 ,....., Rn Rn +1 phủ kín đường tròn. Như vậy P nằm ở trong cung 1 Rk Rk +1. Nhưng vì độ dài cung Rk Rk +1 < P P2 , thì hoặc là Rk +1 , hoặc là nào đó 1 Rk −1 nằm trong P P2 (đpcm). 1
16