Bài giảng Các bài toán về Hình học tổ hợp - Lê Phúc Lữ

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

14
lượt xem 6
download

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

Bài giảng "Các bài toán về Hình học tổ hợp - Lê Phúc Lữ” được chia sẻ dưới đây sẽ giúp bạn ôn tập và nâng cao kỹ năng giải bài tập toán học nhằm ôn tập lại kiến thức cũng như chuẩn bị cho các kì thi sắp diễn ra đạt kết quả cao. Mời các bạn cùng tham khảo chi tiết bài giảng.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Các bài toán về Hình học tổ hợp - Lê Phúc Lữ

CÁC BÀI TOÁN VỀ HÌNH HỌC TỔ HỢP Lê Phúc Lữ - Thành phố Hồ Chí Minh I. Kiến thức cần nhớ. 1. Các khái niệm cơ bản về hình học tổ hợp. - Khoảng cách: từ điểm M đến hình ( H ) là min {MN | N ∈ ( H )} . Chẳng hạn nếu ( H ) là một điểm thì khoảng cách từ M đến hình ( H ) chính là độ dài đoạn thẳng, nếu ( H ) là đường tròn (O) thì đó chính là khoảng cách từ M đến giao điểm gần nhất của MO với đường tròn,... h M N O - Lân cận: bán kính d của hình ( H ) là tập hợp các điểm M có khoảng cách đến ( H ) không vượt quá d . Chẳng hạn: lân cận của một điểm là một hình tròn, lân cận của một đường tròn là một hình xuyến, lân cận của một đoạn thẳng là hai hình chữ nhật và hai nửa hình tròn, lân cận của một đa giác là gồm nhiều hình chữ nhật và nhiều phần của một hình tròn. A B D C - Bao lồi: của một hệ điểm là đa giác lồi có đỉnh thuộc hệ điểm đã cho, có chu vi nhỏ nhất và chứa toàn bộ hệ điểm đó. Bao lồi là một công cụ mạnh, không chỉ để giải quyết các bài toán mang tính lý thuyết mà còn cả những bài mang tính thực tiễn cao. 1
- Điểm nguyên: trong hệ trục tọa độ vuông góc Oxy hoặc trong không gian Oxyz là những điểm có tọa độ đều là các số nguyên. 2. Một số định lí cơ bản. - Lân cận bán kính d của một đa giác có diện tích S , chu vi P có diện tích là S + pd + π d 2 . 1 - Một tam giác nội tiếp trong một hình chữ nhật thì có diện tích không vượt quá diện tích của 2 hình chữ nhật đó. - Một đa giác có khoảng cách lớn nhất giữa hai điểm M , N bất kì nằm trong nó không vượt quá d có thể nội tiếp được trong một hình tròn có đường kính là d . - Một đa giác có số cạnh chẵn thì tồn tại một đường chéo không song song với bất cứ cạnh nào của đa giác. - Định lí Pick: một đa giác lồi không tự cắt có a điểm nguyên trên cạnh (có tính cả đỉnh) và b a điểm nguyên nằm phía trong thì có diện tích là S = + b − 1 . 2 II. Một số bài tập áp dụng. Bài 1: Trong mặt phẳng cho n điểm A1 , A2 , A3 ,..., An sao cho không có ba điểm nào thẳng hàng và không có 4 điểm nào tạo thành một hình thang. Qua mỗi điểm Ai , i = 1, n , ta vẽ các đường thẳng song song với tất cả các đoạn thẳng Aj Ak , j ≠ k , k ∈ {1, 2,3,..., n} . Tìm số tối đa các giao điểm của các đường thẳng song song đã vẽ. Giải. (n − 1)(n − 2) Xét một điểm Ai ,1 ≤ i ≤ n nào đó, có tất cả: Cn2−1 = đường thẳng đi qua 2 trong n − 1 2 điểm còn lại. n(n − 1)(n − 2) Do có tất cả n điểm nên ta có đường thẳng trong mặt phẳng và có n − 2 đường 2 thẳng cùng song song với nhau. Ta sẽ tìm số giao điểm tối đa của một đường thẳng d đi qua điểm Ai ,1 ≤ i ≤ n nào đó với các n(n − 1)(n − 2) đường thẳng khác còn lại. Ngoài đường thẳng d ra, = ta còn M − 1 đường thẳng 2 (n − 1)(n − 2) khác và trong = đó có N − 1 đường cùng đi qua Ai như đường thẳng d. 2 Do đường thẳng d song song với P= n − 3 đường thẳng khác nên số giao điểm nhiều nhất trên đường thẳng d là: 2
 n(n − 1)(n − 2)   (n − 1)(n − 2)  n3 − 4n 2 + 3n + 4 =M −N −P  − 1 −  −= 1 − (n − 3) .  2   2  2 n(n − 1)(n − 2) Vì có tất cả đường thẳng và mỗi giao điểm như trên được tính 2 lần nên số giao 2 n(n − 1)(n − 2)(n3 − 4n 2 + 3n + 4) điểm tối đa có thể có là: . 8 Bài toán trên thú vị ở chỗ là nếu thay song song bởi vuông góc thì vẫn cho ra cùng một kết quả như trên. Bài 2. Trong mặt phẳng cho n điểm phân biệt A1 , A2 ,..., An sao cho không có ba điểm nào thẳng hàng và bốn điểm nào tạo thành hình bình hành. Gọi M i , i = 1, m là trung điểm của các đoạn thẳng Ai Aj , i ≠ j nào đó. Gọi N là tổng độ dài các đoạn Ai Aj , i ≠ j và M là tổng độ dài n 2 − 3n + 1 các đoạn M i M j , i ≠ j . Chứng minh rằng: M < N. 2 Giải. Trước hết, ta thấy rằng: - Nếu M, N, P là trung điểm của các cạnh BC, CA, AB của tam giác ABC thì: 1 MN + NP + PM= ( AB + BC + CA) . 2 - Nếu M, N, P, Q, R, S là trung điểm của các cạnh AB, CD, BC, DA, AC, BD của tứ giác ABCD thì ta có bất đẳng thức sau: 1 MN + PQ + RS < ( AB + BC + CD + DA + AC + BD) 2 B A M A N S P P Q R C D C B M N Áp dụng hai hệ thức trên cho tất cả các trung điểm. Ta thấy mỗi đoạn M i M j , i ≠ j bất kì đều thuộc về một tam giác hoặc một tứ giác nào đó, còn mỗi cạnh Ai Aj , i ≠ j bất kì thì thuộc về (n − 2)(n − 3) n – 2 tam giác hoặc thuộc về Cn2− 2 = tứ giác. Cộng từng vế các hệ thức đó, ta được: 2 3
1 1  n 2 − 3n + 2 ∑ 1≤i < j ≤ m M i M j <  (n − 2) + (n − 2)(n − 3)  ∑ Ai Aj ⇔ M < 2 4  1≤i < j ≤ n 4 N. 4
Bài 3. Trong mặt phẳng cho 3n điểm phân biệt A1 , A2 ,... A3n sao cho không có ba điểm nào thẳng hàng và khoảng cách giữa 2 điểm bất kì không vượt quá 1. Chứng minh rằng: 1. Tồn tại đường thẳng d không đi qua bất cứ điểm nào trong các điểm A1 , A2 ,... A3n và không song song với bất cứ đường thẳng chứa 2 điểm Ai , Aj , i ≠ j nào. 2. Giả sử khoảng cách từ các điểm A1 , A2 ,... A3n đến đường thẳng d tăng dần. Chứng minh rằng các tam giác: A3i +1 A3i + 2 A3i +3 , i = 1, n đôi một rời nhau. 1 3. Chứng minh rằng tổng diện tích của n tam giác trên nhỏ hơn . 2 Giải. 1. Gọi Ω là đa giác lồi chứa tất cả các điểm A1 , A2 ,... A3n . Kẻ một đường thẳng trong mặt phẳng không cắt bất cứ cạnh nào của Ω thì đường thẳng này không đi qua điểm nào trong các điểm nói trên. Do số điểm đã cho hữu hạn nên số đường thẳng qua 2 điểm bất kì cũng hữu hạn, vì vậy tồn tại một đường thẳng không song song với bất cứ đường thẳng chứa 2 điểm nào trong 3n điểmtrên. Từ đó suy ra đường thẳng d tồn tại và ta có đpcm. 2. Qua các điểm A3i +1 , kẻ các đường thẳng ∆ i song song với d. Do khoảng cách từ các điểm A1 , A2 ,... A3n đến d tăng dần nên các đường thẳng ∆ i nói trên chia mặt phẳng thành các dãy mà mỗi tam giác A3i +1 A3i + 2 A3i +3 , i = 1, n được phân cách với các tam giác khác bởi các đường thẳng ∆ i . Tức là các tam giác nói trên rời nhau. b a d D C A B 3. Gọi Si , i = 1, n là diện tích của tam giác A3i +1 A3i + 2 A3i +3 . Rõ ràng tồn tại 2 đường thẳng a, b cùng vuông góc với d và đi qua ít nhất 2 trong 3 đỉnh của tam giác A3i +1 A3i + 2 A3i +3 . Qua đỉnh A3i +3 , kẻ 5
một đường thẳng ∆ 'i song song với d. Kí hiệu các giao điểm như hình vẽ. Rõ ràng tam giác A3i +1 A3i + 2 A3i +3 nằm hoàn toàn trong hình chữ nhật ABCD nên: 1 1 1 1 Si < S ABCD = AB.BC ≤ AC.di ≤ di , 2 2 2 2 trong đó di là khoảng cách giữa các đường thẳng ∆ i và ∆ 'i . Suy ra: n n 1 1 1 ∑ S i < =i 1 =i 1 2 ∑ di ≤ A1 A3n ≤ . 2 2 Ta có đpcm. Bài 4. Trong mặt phẳng, cho tập hợp A gồm 20142 điểm phân biệt được đánh số từ 1 đến 20142 sao cho ba điểm bất kì nào trong chúng cũng không thẳng hàng. Một tứ giác (lồi hoặc lõm) được gọi là “đẹp” nếu các đỉnh của nó thuộc A và được đánh số bằng 4 số thỏa mãn một trong hai điều kiện sau: - Đó là 4 số tự nhiên cách nhau 2014 đơn vị. - Đó là 4 số tự nhiên liên tiếp và nếu trong đó có chứa số chia hết cho 2014 thì số đó phải là lớn nhất hoặc nhỏ nhất. Nối tất cả các điểm thuộc tập hợp A lại với nhau sao cho điểm nào thuộc A cũng thuộc đúng một tứ giác. Tìm số lớn nhất tứ giác “đẹp” được tạo thành. Giải. Xét một bảng ô vuông gồm 2014 × 2014 ô vuông con được điền các số theo thứ tự từ trên xuống và trái sang như sau: 1 2 3 … 2013 2014 2015 2016 2017 … 4019 4028 4029 4030 4031 … 6041 6042 … … … … … … … … … … … 20142 Trước hết, ta sẽ chứng minh rằng không thể chia tất cả 20142 điểm đã cho thành các tứ giác “đẹp” được. Rõ ràng 4 số trên các đỉnh của các tứ giác “đẹp” tương ứng với 4 số bị che đi trên bảng ô vuông khi đặt một mảnh bìa hình chữ nhật kích thước 1× 4 vào đó. Ta sẽ chứng minh rằng không thể che hết toàn bộ bảng ô vuông này bằng các hình chữ nhật 1× 4 . Thật vậy, ta tô màu các ô vuông nằm ở cột chẵn và hàng chẵn. Do bảng có 20142 ô vuông nên số 20142 ô vuông bị tô màu là: = 1014049 là số lẻ. 4 6
Giả sử ngược lại rằng ta có thể lấp kín được cả bảng ô vuông bằng các mảnh bìa. Khi đó, mỗi mảnh bìa sẽ che đi hoặc hai ô vuông hoặc không có ô vuông nào của bảng ô vuông, tức là luôn có một số chẵn ô vuông bị che đi; do đó, số ô vuông bị che đi trên bảng là một số chẵn. Từ đó ta thấy có mâu thuẫn. Vậy không thể che hết bảng ô vuông này bằng các hình chữ nhật 1× 4 được. Gọi k là số tứ giác đẹp lớn nhất cần tìm thì k < 1014049 ⇒ k ≤ 1014048 . Ta sẽ chứng minh k = 1014048 bằng cách chỉ ra cách dùng các mảnh bìa che kín bảng ô vuông. Thật vậy, chia bảng ô vuông thành hai phần: - Phần 1 gồm 2012 cột đầu, ta xếp các mảnh bìa theo các hàng, mỗi hàng có đúng 503 mảnh bìa. Khi đó, ta sẽ có thể che kín hết phần 1 bởi các mảnh bìa. - Phần 2 gồm 2 cột cuối, ta xếp nối tiếp các mảnh bìa từ trên xuống dưới thì cuối cùng sẽ còn lại một ô vuông 2 × 2 ở góc dưới cùng của bảng. Như vậy, ta dùng k = 1014048 mảnh bìa che được tối đa 20142 − 4 ô vuông của bảng. Từ đó, ta thấy, số tứ giác “đẹp” lớn nhất cần tìm là k = 1014048 . Bài 5. Cho một mảnh giấy hình vuông. Người ta cắt mảnh giấy này thành hai mảnh hình chữ nhật. Lấy một trong hai mảnh đó cắt làm hai mảnh sao cho đường cắt không đi qua đỉnh nào của mảnh giấy và tiếp tục làm nhiều lần như vậy. Hỏi sau ít nhất bao nhiêu lần cắt, ta thu được 30 đa giác có 70 cạnh? Giải. Giả sử sau n lần cắt, ta thu được 30 đa giác có 70 cạnh. Cần tìm giá trị nhỏ nhất của n. Ta thấy sau một lần cắt một mảnh giấy thành 2 mảnh, số đỉnh của các đa giác tăng lên đúng 4 đỉnh (vì các đường cắt không đi qua đỉnh nào của mảnh giấy); do đó, sau n lần cắt, số đỉnh tăng lên tổng cộng là 4n + 4. Mặt khác, sau mỗi lần cắt như vậy, ta có thêm đúng 1 đa giác nên sau n lần cắt có tất cả n + 1 đa giác; ta đã có 30 đa giác có 70 cạnh nên số đa giác còn lại là (n + 1) − 30 = n − 29 . Mà mỗi đa giác có ít nhất 3 đỉnh (trường hợp mảnh giấy hình tam giác) nên tổng số đỉnh của các đa giác còn lại là 3(n − 29) . Từ đó, ta được: 4n + 4 ≥ 30.70 + 3(n − 29) ⇔ n ≥ 2009 . Ta sẽ chứng minh n = 2009 chính là giá trị nhỏ nhất cần tìm bằng cách chỉ ra một cách cắt thỏa mãn đề bài. Trước hết, ta cắt các mảnh giấy 29 lần để được 30 hình chữ nhật. Sau đó, ở mỗi hình chữ nhật, ta cắt 66 lần (mỗi lần như vậy số đỉnh của đa giác tăng lên 1) để thu được đa giác 70 cạnh. Số lần cắt tổng cộng là: 29 + 30.66 =2009 . Vậy số lần cắt ít nhất cần tìm là 2009 lần. 7
Bài 6. Trên mặt phẳng cho n điểm A1 , A2 , A3 ,..., An sao cho khoảng cách giữa các điểm đôi một khác nhau. Trong các đoạn thẳng xuất phát từ Ai ,1 ≤ i ≤ n , ta gọi Aj , j ≠ i là điểm mà khoảng cách Ai Aj ngắn nhất và tô màu đoạn đó; tiếp tục chọn trong các đoạn thẳng xuất phát từ Aj một đoạn Aj Ak , k ≠ i, k ≠ j ngắn nhất và tô màu cho nó. Chứng minh rằng khi quá trình này kết thúc, không có đường gấp khúc khép kín nào được tô màu tất cả các cạnh. Giải: Giả sử xuất phát từ điểm A1 , ta có A1 A2 là ngắn nhất, ta tô màu đoạn thẳng này. Tiếp tục xét điểm A2 , ta có hai trường hợp xảy ra: - Nếu min A2 Ai = A2 A1 thì quá trình này dừng lại và không có đường gấp khúc khép kín nào được 1≤i ≤ n tô màu tất cả các cạnh. = - Nếu min A2 Ai A2 Aj , j ≠ 1 thì ta có thể tiếp tục quá trình này. Không mất tính tổng quát, giả sử 1≤i ≤ n j = 3 , khi đó: A2 A3 < A1 A2 , ta tô màu đoạn A2 A3 .Tiếp tục như vậy, giả sử quá trình này dừng lại tại điểm Ak ,3 ≤ k ≤ n , ta có các đoạn thẳng trong quá trình trên đã được tô màu là: A1 A2 > A2 A3 > ... > Ai Ai +1 > ... > Ak −1 Ak . Giả sử trong các đoạn này có một đường gấp khúc khép kín nào đó, tức là có một điểm nào đó là đầu mút của hai đoạn thẳng, giả sử là điểm Ai và đường gấp khúc đó là: Ai Ai +1... Am Ai . Khi đó, theo cách lựa chọn các điểm, ta có: Ai Ai +1 > Ai +1 Ai + 2 > ... > Am Ai . Từ đây suy ra có điểm Am mà Am Ai < Ai Ai +1 , mâu thuẫn với cách chọn Ai +1 . Từ đây ta có đpcm. Bài 7. Trong hình vuông cạnh 200 cm có 2010 đa giác lồi mà mỗi đa giác có diện tích không quá 2π (cm 2 ) và chu vi không quá 3π (cm) . Chứng minh trong hình vuông luôn tồn tại một hình tròn có bán kính bằng 1 cm không cắt bất cứ đa giác nào. Giải. Dựng một hình vuông có cạnh là 198cm bên trong hình vuông kia sao cho hai hình vuông này có cùng tâm với nhau (tức là thu nhỏ mỗi cạnh của hình vuông cũ 2cm). Diện tích của hình vuông cạnh 198cm này là : 1982 = 39204 (cm 2 ) . Dựng các lân cận bán kính 1 cm của các hình đa giác đã cho. Diện tích các lân cận đó chính bằng tổng của diện tích đa giác, diện tích các hình chữ nhật và diện tích các hình quạt dựng tại các đỉnh của đa giác. Ta sẽ chứng minh rằng với một đa giác n cạnh bất kì, tổng các góc ngoài bằng 3600 . Thật vậy, với mỗi đa giác như vậy, ta chia thành n – 2 tam giác có chung đỉnh và đôi một rời nhau. Tổng các góc của mỗi tam giác như vậy là 1800 nên tổng các góc trong của đa giác lồi đó là (n − 2)1800 . Do đó, tổng các góc ngoài của đa giác lồi là : n.1800 − (n − 2).1800 = 3600 . 8
Tổng các góc của các hình quạt là 3600 , hơn nữa các hình quạt này có cùng bán kính 1 cm nên tổng diện tích các hình quạt này chính bằng diện tích của hình tròn bán kính là 1 cm và là : π .12 = π (cm 2 ) . Do đó, tổng diện tích mỗi đa giác và lân cận là : 2π + 3π .1 + π = 6π (cm 2 ) ; suy ra : tổng diện tích các đa giác và lân cận là: 2010.6π < 2010.6.3, 2 = 38592 (cm 2 ) < 39204 (cm 2 ) . Vậy tồn tại một điểm A thuộc hình vuông cạnh 198 cm mà không thuộc bất cứ đa giác và lân cận 1 cm nào của chúng. Khi đó đường tròn (A,1 cm) không cắt bất cứ đa giác nào và rõ ràng nó thỏa mãn đề bài. Ta có đpcm. Bài 8. Trong một hình vuông có cạnh là 1 cho k điểm phân biệt bất kì (có thể thẳng hàng). Nối các điểm đó lại với nhau bởi các đoạn thẳng sao cho hai đoạn bất kì không cắt nhau tạo thành các tam giác chia hình vuông thành các phần nhỏ hình tam giác rời nhau. Tìm số k nhỏ nhất sao cho trong các tam giác được chia ra, luôn tồn tại một tam giác có diện tích 1 không quá . 100 Giải. 9
Giả sử với k điểm nằm trong hình vuông đó, có tất cả a tam giác được tạo thành. Tổng tất cả các góc trong của các tam giác đó là a.1800 . Mặt khác, các góc đó cũng chính là các góc quay xung quanh mỗi điểm đã cho cùng với các đỉnh của hình vuông nên tổng trên cũng bằng : 4.900 + k .3600 . Do đó, ta có 4.900 + k .3600 = a.1800 ⇔ a = 2k + 2 . Tức là với mọi cách sắp xếp các điểm và nối các đoạn thẳng ứng với k điểm ta luôn thu được 2k + 2 tam giác. 1 Vì có tất cả 2k + 2 tam giác nên diện tích của tam giác nhỏ nhất không vượt quá . 2k + 2 1 1 Mà ≤ ⇔ k ≥ 49 nên tất cả các giá trị k ≥ 49 đều thỏa mãn đề bài. 2k + 2 100 Ta sẽ chứng minh rằng k = 48 (hoặc nhỏ hơn) không thỏa mãn đề bài bằng cách chỉ ra một cách sắp xếp các điểm này phía trong hình vuông và cách nối chúng lại thành các tam giác mà diện 1 tích của tam giác bất kì đều lớn hơn . 100 Thật vậy, ta đặt 48 điểm này chia đều một đường chéo đi qua hai đỉnh nào đó của hình vuông và nối các điểm này với hai đỉnh còn lại của hình vuông. Rõ ràng hình vuông đã được chia thành 98 1 1 tam giác nhỏ bằng nhau và diện tích mỗi tam giác này cùng bằng > , không thỏa mãn đề 98 100 bài. Vậy giá trị nhỏ nhất của k cần tìm là 49. 10
Bài 9. Trong không gian cho 7 điểm phân biệt sao cho không có bốn điểm nào đồng phẳng. Tất cả các điểm đó được nối với nhau bởi các đoạn thẳng. Mỗi đoạn thẳng được tô bởi hai màu xanh, đỏ hoặc không được tô màu. Tìm số k nhỏ nhất sao cho với mọi cách tô màu k đoạn thẳng bất kì trong các đoạn thẳng đó, luôn tồn tại một tam giác có ba cạnh cùng màu. Giải. Trước hết, ta có kết quả quen thuộc sau : Cho 6 điểm phân biệt sao cho không có ba điểm nào thẳng hàng. Nếu ta tô màu tất cả các đoạn thẳng nối các điểm này bởi hai màu xanh hoặc đỏ thì luôn tồn tại một tam giác có các cạnh cùng màu. Từ giả thiết không có bốn điểm nào đồng phẳng, ta suy ra rằng không có ba điểm nào thẳng hàng và hai đoạn thẳng bất kì chỉ cắt nhau tại đầu mút chung (nếu có) của chúng. Gọi 7 điểm đã cho là A1 , A2 ,..., A7 . Ta thấy với 7 điểm này, có tất cả C72 = 21 đoạn thẳng. Do đó : k ≤ 21 . Nếu tô màu tất cả 21 đoạn thẳng này thì chỉ cần chọn ra 6 điểm trong đó cũng sẽ thỏa mãn điều kiện theo kết quả ở trên. Ta thử tìm giá trị k nhỏ hơn. - Với k = 20, ta tô màu 20 đoạn và không tô màu 1 cạnh, giả sử là A1 A7 , khi đó tất cả các đoạn thẳng trong bộ 6 điểm A1 , A2 , A3 , A4 , A5 , A6 (hoặc A2 , A3 , A4 , A5 , A6 , A7 ) đều được tô màu, lại theo kết quả trên, điều kiện được thỏa mãn, tức là k = 20 vẫn thỏa mãn đề bài. A3 A 2 A 4 A 5 A 1 A A 7 6 - Với k = 19, ta tô màu 19 đoạn và không tô màu 2 cạnh. Ta sẽ chỉ ra một cách tô màu bỏ đi hai đoạn thẳng và không có hai tam giác nào được tô cùng màu như trên hình vẽ. Nếu hai cạnh A1 A7 và A2 A6 không được tô màu thì trong các đoạn xuất phát từ A3, tô xanh bốn đoạn và tô đỏ 2 đoạn ; với các đỉnh còn lại tô xanh 3 đoạn, tô đỏ 3 đoạn (hoặc 2 đoạn đối với hai điểm A6, A7). Do đó, k = 19 không thỏa mãn đề bài. Rõ ràng nếu k = 19 không thỏa thì tất cả số nhỏ hơn nó cũng không thỏa mãn. Vậy giá trị nhỏ nhất của k cần tìm là 20. 11
Bài 10. Một đa giác đều 9 cạnh có các đỉnh được tô bởi một trong hai màu : xanh hoặc đỏ. Chứng minh rằng tồn tại hai tam giác có đỉnh là đỉnh của đa giác đã cho và thỏa mãn hai điều kiện sau: i) Diện tích bằng nhau. ii) Tất cả các đỉnh của hai tam giác đều được tô cùng màu. Lời giải. Ta thấy rằng tô màu 9 đỉnh của đa giác bởi 2 màu thì theo nguyên lí Dirichlet, tồn tại ít nhất 5 đỉnh được tô cùng màu. Ta sẽ chứng minh rằng trong 5 đỉnh đó, tồn tại ít nhất 2 tam giác có cùng diện tích. Số tam giác tạo thành từ 5 đỉnh đó là số cách chọn 3 đỉnh bất kì trong 5 đỉnh và có C53  10 tam giác. Ta xét các phép quay đa giác quanh tâm đường tròn ngoại tiếp O của đa giác với các góc có k 2 số đo là , k  1, 2,3,...,9 . 9 Rõ ràng các phép quay này tuy thay đổi vị trí các đỉnh nhưng các tam giác vẫn có màu như cũ nên sau 9 phép quay, ta thu được 90 tam giác được tô cùng màu. Tuy nhiên, số tam giác tạo thành bởi các đỉnh của đa giác đã cho là C93  84  90 nên theo nguyên lí Dirichlet thì tồn tại hai tam giác được tô cùng màu là ảnh của nhau qua một phép quay trong các phép quay đã xét, tức là chúng có diện tích bằng nhau. Từ đó, ta có đpcm. Bài 11. (VN TST 1999) Cho một đa giác lồi (H). Chứng minh rằng với mỗi số thực a ∈ (0,1) , tồn tại 6 điểm phân biệt nằm trên các cạnh của (H), kí hiệu là A1 , A2 ,..., A6 theo chiều kim đồng hồ thỏa mãn đồng thời hai điều kiện sau:    1. A1 A2= A5 A4= a ⋅ A6 A3 . 2. Các đường thẳng A1 A2 , A5 A4 cách đều đường thẳng A6 A3 . 12
Giải. Trước hết, ta sẽ dựng đoạn A6 A3 có các đỉnh nằm trên các cạnh của (H). Lấy một điểm X bất kì nằm trong đa giác (H) đã cho, gọi (d) là một đường thẳng bất kì qua X, không song song với các cạnh của (H) và A6 , A3 là hai giao điểm của (d) với các cạnh của (H). Đánh dấu một miền mặt phẳng nằm trong (H) được chia ra bởi (d) là P và phần còn lại là Q. Ta sẽ tìm được vô số bộ sáu điểm thỏa mãn (1) và cần chứng minh rằng trong số đó, tồn tại ít nhất một bộ thỏa mãn (2). X A3 I M N A2 A6 A1   Trên đoạn A6 A3 đã dựng, lấy điểm I sao cho A6 I= a ⋅ A6 A3 . Trong miền P, dựng hình bình hành A6 IMN bất kì sao cho một trong hai đỉnh M và N nằm trên cạnh của (H). Tiếp tục tịnh tiến  vector MN về phía cạnh của (H) đến khi cả hai đỉnh đều nằm trên các cạnh của (H). Dễ thấy đoạn MN luôn tồn tại vì: -Nếu (d) không song song với cạnh nào của (H) nên khi a → 0 thì đoạn MN cũng tiến gần về một đỉnh nào đó của (H). - Nếu (d) song song với một cạnh của (H), và độ dài của MN lớn hơn độ dài cạnh đó thì M, N lần lượt thuộc về hai cạnh kề với cạnh của (H) nêu trên; ngược lại thì MN sẽ nằm ngay trên cạnh đó. Tiếp theo, ta sẽ chứng minh rằng trong trường hợp (d) không song song với cạnh nào của (H) thì trong miền (P), chỉ có đúng một đoạn MN thỏa mãn cách dựng trên. Thật vậy, giả sử tồn tại hai đoạn MN , M ' N ' có đỉnh đều nằm trên các cạnh của (H) và các tứ giác A6 IMN , A6 IM ' N ' là hình bình hành. Ta sẽ chứng minh rằng điều này mâu thuẫn với giả thiết (H) là đa giác lồi. Thật vậy, ta xét ba trường hợp: (1) Nếu giao điểm của hai đường thẳng đi qua hai cạnh chứa A6 , A3 cắt nhau tại một điểm nằm trong miền (P). Khi đó, các đoạn thẳng song song với A6 A3 có đỉnh nằm trong miền này đều có độ dài nhỏ hơn A6 A3 . Nếu tồn tại hai đoạn thẳng MN , M ' N ' như trên. 13
Ta lại tiếp tục có ba trường hợp: (1.1) Nếu có một cặp đỉnh nào đó trong chúng thuộc cùng một cạnh, giả sử là M và M’ và hai đỉnh còn lại là N, N’ thì không; khi đó rõ ràng các đỉnh nằm giữa N, N’ sẽ không nằm trong cùng nửa mặt phẳng bờ là đường thẳng đi qua đầu mút của đoạn thẳng chứa hai đỉnh N, N’, điều này mâu thuẫn với giả thiết (H) là đa giác lồi. (1.2) Nếu cả hai cặp đỉnh của hai đoạn MN , M ' N ' cùng nằm trên các cạnh của (H) thì hai cạnh đó phải song song với nhau, ta thấy điều này cũng mâu thuẫn. (1.3) Nếu không có cặp đỉnh nào cùng thuộc một đoạn thì những cũng tương tự trường hợp trên, các đỉnh nằm giữa hai đỉnh M, M’ và N, N’ sẽ không thuộc cùng một nửa mặt phẳng có bờ là đường thẳng đi qua đầu mút của đoạn thẳng chứa hai đỉnh M, M’ và N, N’; mâu thuẫn. (2) Nếu giao điểm của đường thẳng đi qua hai cạnh chứa A6 , A3 song song thì khi tịnh tiến vector   A6 A3 trên đường thẳng đó, ta luôn nhận được các vector có bằng với A6 A3 . Do đa giác đã cho là lồi nên các đỉnh còn lại thuộc miền (P) của (H) sẽ chỉ nằm trong phần giữa hai đường thẳng song song nêu trên. Từ đó, ta cũng đưa về trường hợp đầu tiên và cũng dẫn đến điều mâu thuẫn. A1 A2 A6 I A5 A3 A4 (3) Nếu giao điểm của hai đường thẳng đi qua hai cạnh chứa A6 , A3 cắt nhau tại một điểm không nằm trong miền (P). Khi đó, độ dài của các đoạn thẳng song song với A6 A3 sẽ tăng lên đến một giá trị nào đó rồi giảm xuống đến 0; khi nó giảm đến độ dài đúng bằng A6 A3 thì ta lại quay về trường hợp đầu tiên và cũng có điều vô lí. Tiếp theo, ta cần chứng minh rằng tồn tại một cách dựng đường thẳng (d) mà các cả 6 điểm này đều thỏa mãn đề bài. - Nếu như khoảng cách từ A1 A2 và từ A5 A4 đến A6 A3 bằng nhau thì bài toán kết thúc. 14
-Nếu như khoảng cách từ A1 A2 và từ A5 A4 đến A6 A3 không bằng nhau và giả sử đoạn A1 A2 gần A6 A3 hơn đoạn A5 A4 . Quay (d) quanh X nửa vòng tròn, độ dài của A6 A3 thay đổi liên tục như khi quay (d) quanh X cả một vòng tròn. Độ dài của các đoạn A1 A2 và A5 A4 cũng thay đổi theo nhưng tỉ lệ giữa chúng thì vẫn giữ nguyên. Đến khi quay xong thì các đoạn A1 A2 và A5 A4 đã đổi chỗ cho nhau, tức là khoảng cách từ đoạn đoạn A5 A4 đến A6 A3 gần hơn đoạn A1 A2 . Do phép biến đổi này thực hiện liên tục nên tồn tại một thời điểm mà khoảng cách giữa A1 A2 và A5 A4 đến A6 A3 bằng nhau. Ngay lúc đó, bộ 6 điểm A1 , A2 ,..., A6 này thỏa mãn tất cả các điều kiện của đề bài. Ta có đpcm. Bài 12. (VN TST 2007) Cho đa giác 9 cạnh đều (H). Xét ba tam giác với các đỉnh là các đỉnh của đa giác (H) đã cho sao cho không có hai tam giác nào có chung đỉnh. Chứng minh rằng có thể chọn được từ mỗi tam giác 1 cạnh sao cho 3 cạnh này bằng nhau. Lời giải. Kí hiệu hình (H) đã cho là đa giác A1 A2 A3 ... A8 A9 như hình vẽ. Trước hết, ta thấy rằng độ dài các cạnh và các đường chéo của hình (H) chỉ thuộc 4 giá trị khác nhau (nếu gọi R là bán kính đường tròn ngoại tiếp của (H) thì ta dễ dàng tính được các giá trị đó là π 2π 3π 4π 2 R.sin , 2 R sin , 2 R sin , 2 R sin ) ta đặt chúng là a1 , a2 , a3 , a4 theo thứ tự tăng dần của 9 9 9 9 độ dài. Rõ ràng các tam giác có đỉnh thuộc các đỉnh của (H) sẽ có cạnh có độ dài thuộc 1 trong 6 dạng sau: (a1 , a1 , a2 ), (a2 , a2 , a4 ), (a1 , a3 , a4 ), (a3 , a3 , a3 ), (a2 , a3 , a4 ), (a4 , a4 , a1 ) . A1 a1 A2 a2 A A3 9 a3 a4 A A4 8 A A 7 5 A 6 15
Giả sử 3 tam giác được lấy ra là ∆1 , ∆ 2 , ∆ 3 . Xét các trường hợp sau: - Nếu trong các tam giác đó có một tam giác đều, rõ ràng, tam giác này phải có độ dài các cạnh 3π là 2 R.sin ; không mất tính tổng quát, giả sử đó là tam giác A1 A4 A7 . Do các tam giác 9 ∆1 , ∆ 2 , ∆ 3 không có hai đỉnh nào trùng nhau nên ta sẽ lập một tam giác có các đỉnh là một trong hai đỉnh của các tập hợp { A2 , A3 },{ A4 , A5 },{ A7 , A8 } . Ta sẽ chứng minh rằng tam giác đó phải có ít 3π nhất 1 cạnh có độ dài là 2 R.sin , tức là hai đỉnh có chỉ số có cùng số dư khi chia cho 3. Giả sử 9 3π ngược lại, trong hai tam giác cần lập, không có tam giác nào có cạnh là 2 R.sin , khi đó đỉnh 9 A2 phải nối với A4 và A4 phải nối với A8, nhưng khi đó A8 được nối với A2 là hai đỉnh có chỉ số chia cho 3 cùng dư là 2, mâu thuẫn. Do đó, trong hai tam giác lập được, luôn có một cạnh có độ 3π dài là 2 R.sin . Suy ra trường hợp này luôn có tam giác thỏa mãn đề bài. 9 - Nếu trong các tam giác đó, không có tam giác nào đều . Khi đó các tam giác được xét không có ba đỉnh cùng thuộc một trong ba tập hợp sau: α1 = { A1 , A4 , A7 } , α 2 = { A2 , A5 , A8 } , α 3 = { A3 , A6 , A9 } . Ta thấy một đoạn thẳng nối hai điểm bất kì thuộc hai tập khác nhau sẽ nhận 1 trong 3 giá trị là a1 , a2 , a4 . Hơn nữa, không có tam giác nào có độ dài 3 cạnh là (a1 , a2 , a4 ) nên ta có hai nhận xét: (1) Một tam giác có các đỉnh thuộc cả ba tập α1 , α 2 , α 3 nói trên thì sẽ có hai cạnh nào đó có độ dài bằng nhau (các cạnh của nó có thể là (a1 , a1 , a2 ) , (a2 , a2 , a4 ) , (a4 , a4 , a1 ) ) tức là nó phải cân. (2) Một tam giác có hai trong ba đỉnh thuộc cùng một tập thì tam giác đó các cạnh có độ dài là (a2 , a3 , a4 ) hoặc là (a1 , a3 , a4 ) , tức là tam giác đó không cân. * Ta xét tiếp các trường hợp (các tam giác xét dưới đây là cân nhưng không đều): + Có hai tam giác cân và một tam giác không cân: khi đó theo nhận xét (1), hai tam giác cân đó phải có đỉnh thuộc các tập hợp khác nhau trong ba tập α1 , α 2 , α 3 ; khi đó, rõ ràng tam giác còn lại cũng phải có đỉnh thuộc các tập hợp khác nhau, tức là nó phải cân, mâu thuẫn. Vậy trường hợp này không tồn tại. + Có một tam giác cân và hai tam giác không cân: khi đó theo nhận xét (2), hai tam giác không cân đó phải có hai đỉnh thuộc cùng một tập hợp và đỉnh còn lại thuộc tập hợp khác, giả sử một tam giác có hai đỉnh thuộc α1 và một đỉnh thuộc α 2 ; rõ ràng tam giác không cân còn lại phải có 16
hai đỉnh thuộc α 2 , một đỉnh thuộc α 3 , suy ra tam giác còn lại có hai đỉnh thuộc α 3 , một đỉnh thuộc α1 nên nó là tam giác cân, mâu thuẫn. Vậy tương tự như trên, trường hợp này không tồn tại. + Cả ba tam giác đều không cân: khi đó theo nhận xét (2), tam giác đó thuộc một trong hai dạng (a2 , a3 , a4 ) hoặc là (a1 , a3 , a4 ) , tức là các tam giác này luôn chứa 1 cạnh có độ dài là a3. Trong trường hợp này, bài toán được giải quyết. + Cả ba tam giác đều cân: khi đó, các tam giác có độ dài là (a1 , a1 , a2 ) , (a2 , a2 , a4 ) , (a4 , a4 , a1 ) . Rõ ràng không tồn tại trường hợp có độ dài các cạnh lần lượt nhận cả ba giá trị như ba bộ trên nên phải có hai bộ trùng nhau, tức là có ít nhất hai tam giác cân bằng nhau và một tam giác cân nhận một trong ba giá trị thuộc một trong các bộ trên làm cạnh, khi đó luôn có thể chọn từ tam giác này một cạnh bằng với cạnh đáy hoặc cạnh bên của hai tam giác cân bằng nhau kia. Trong trường hợp này, bài toán cũng được giải quyết. Vậy trong mọi trường hợp, ta luôn có đpcm. Bài 13. (Đề thi Nữ sinh châu Âu 2012) Một hình vuông đơn vị được chia thành các đa giác, sao cho mỗi cạnh của đa giác đều song song với cạnh của hình vuông cho trước. Nếu tổng độ dài các đoạn thẳng nằm bên trong hình vuông (không tính hình vuông) là 2n (với n là một 1 số thực dương), chứng minh rằng tồn tại một đa giác có diện tích lớn hơn . ( n + 1) 2 Giải. Trước hết ta xét bổ đề sau : Một đa giác R được tạo thành như đề bài có diện tích a thì nó có chu vi ít nhất là 4 a . Chứng minh: Xét bao lồi hình chữ nhật nhỏ nhất chứa hình trên. Gọi hai kích thước bao lồi là x và y . Do bao lồi đang xét là hình chữ nhật nhỏ nhất nên biên của R đều nằm trên các cạnh hình chữ nhật. Dễ thấy, do đa giác được tạo thành từ các đường thẳng song song với cạnh hình vuông đơn vị nên chu vi đa giác cũng bằng chu vi hình vuông (vì các khoảng trống giữa R và bao lồi là các hình chữ nhật). Áp dụng bất đẳng thức AM-GM suy ra x + y ≥ 2 = xy 2 S hcn ≥ 2 a Do đó: PR = Phcn = 2 ( x + y ) ≥ 4 a . Bổ đề được chứng minh xong. Đặt diện tích và chu vi tương ứng của các hình là a1 , a2 ,..., ak và p1 , p2 ,..., pk (lưu ý, các hình ta xét không có diện tích chung). 17
1 ai Giả sử ngược lại tất cả các hình đều có diện tich nhỏ hơn , dễ thấy ai ≤ với mọi ( n + 1) 2 ( n + 1) k i = 1, 2,..., k . Mặt khác ta có:= S hv ∑= ai 1 kết hợp với bổ đề vừa chứng minh thì thu được i =1 k k k ai 1 pi n ∑ a < ∑ ( n + 1) ≤ 4 ∑ ( n + 1) = i =i 1 =i 1 =i 1 ( n + 1) (do tổng độ dài các đoạn thẳng là 2n , mỗi đoạn thẳng được tính hai lần vào hai chu vi của hai hình kề nhau). n Do đó 1 < (đây là điều vô lí) , dẫn đến điều chúng ta giả sử là sai, và phải tồn tại một hình n +1 1 có diện tích lớn hơn . ( n + 1) 2 Ta có đpcm. Bài 14. (VN 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ố nguyên dương 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. Lời giải. Do trong các điểm đã cho không có bốn điểm nào đồng phẳng nên ba điểm bất kì trong chung luôn tạo thành một tam giác. Gọi S(n) là giá trị nhỏ nhất của số tốt ứng với n điểm trong không gian (n là số tự nhiên), ta sẽ xác định giá trị của S(2006). Ta chỉ xét các giá trị n ≥ 4 . 1 2 2 1 1 1 - Với n = 4 thì thử trực tiếp, ta thấy S(4) = 2. Bởi vì S(4) = 1 không thỏa mãn nên S (4) ≥ 2 , ta sẽ chỉ ra rằng S(4) = 2 thỏa mãn. Cụ thể ta có thể gán các đoạn thẳng như sau : gán 4 đoạn bất kì bởi số 1 và 2 đoạn còn lại bởi số 2, rõ ràng các tam giác tạo thành đều thỏa mãn đề bài. 18
- Với một giá trị n > 4 bất kì, ta sẽ chứng minh rằng :   n + 1  S ( n) ≥ 1 + S    .  2  Gọi a là số nhỏ nhất được gán cho các đoạn thẳng trong trường hợp có n điểm. Trong trường hợp tối thiểu, không mất tính tổng quát, ta giả sử rằng a = 1, ta gọi hai đầu mút của đoạn thẳng nào đó được gán số 1 là X và Y. Trong n – 2 điểm còn lại, nếu có một điểm được nối với X và Y bởi một đoạn thẳng gán bởi số 1 thì điểm đó cùng với X và Y sẽ tạo thành một tam giác đều không thỏa mãn đề bài. Do đó, nếu gọi A là tập hợp tất cả các điểm nối với X bởi một đoạn thẳng gán số 1 (có tính luôn điểm Y) và B là tập hợp tất cả các điểm nối với Y bởi một đoạn thẳng gán số 1 (có tính luôn điểm X) thì giữa A và B không có phần tử nào chung hay A + B = n. Ta có các nhận xét sau : - Nếu lấy một điểm bất kì trong tập A và một điểm bất kì trong B thì hai điểm đó cũng phải được nối bởi đoạn thẳng gán số 1 vì nếu không thì hai điểm đó sẽ cùng với X sẽ tạo thành một tam giác không thỏa mãn đề bài (tam giác đó hoặc không có hai số được gán trên hai cạnh bằng nhau hoặc có hai cạnh bằng nhau nhưng cạnh còn lại gán số 1 nhỏ hơn). - Hai điểm bất kì trong A được nối với nhau bởi một đoạn thẳng gán số lớn hơn 1 bởi nếu không thì khi chọn thêm một điểm trong B, ta sẽ có một tam giác không thỏa mãn đề bài (tam giác đó đều). Tương tự với tập hợp B. Tức là trong các tập A và B đều có chứa các số lớn hơn 1. Tiếp theo, ta lại thấy trong mỗi tập A, B như vậy đều cần thêm S ( A ), S ( B ) số nữa để gán cho  n − 1  n + 1 các đoạn thẳng. Giả sử A ≥ B thì A ≥   + 1 = .  2   2  Ta hoàn toàn có thể gán các số ở tập A trùng với các số ở tập B nên các số cần có thêm nữa là   n + 1  S   , tính thêm số 1 nhỏ nhất đã được gán cho đoạn XY ban đầu, ta được:  2    n + 1  S ( n) ≥ 1 + S     với mọi n.  2  Từ đó, áp dụng liên tiếp kết quả này, ta có: (chú ý rằng S(4) = 2). S (2006) ≥ 1 + S (1003) ≥ 2 + S (502) ≥ ... ≥ 9 + A(4) =11 . Tiếp theo, ta sẽ chứng minh rằng giá trị 11 này thỏa mãn đề bài. Thật vậy : Ta xây dựng cách gán các điểm từ thấp đến cao bằng cách ghép các bộ điểm ít hơn lại. Cụ thể như sau : 19
- Đầu tiên ta xây dựng cho bộ 4 điểm. Cách gán tương tự như ở trên, nhưng trong trường hợp này gán 4 đoạn bởi số 11 và 2 đoạn bởi số 10. - Ghép 2 bộ này lại và tách ra từ một trong hai bộ đó ra 2 điểm, gán cho đoạn thẳng nối 2 điểm đó bởi số 10, ta đã có tất cả 8 điểm. - Tiếp tục ghép tương tự như vậy theo thứ tự như sau : 4 → 8 → 16 → 32 → 63 → 126 → 251 → 502 → 1003 → 2006 (Các trường hợp từ 32 đến 63 hoặc tương tự ta phải bỏ đi 1 điểm nào đó ở một trong hai bộ ra ngoài). Mỗi lần ghép hai bộ điểm lại thì số gán trên đoạn được tách ra lại giảm đi 1 đơn vị, đến khi ghép được 2006 điểm thì số đó chính là 1. Dễ thấy cách gán số cho các đoạn thẳng này thỏa mãn đề bài. Vậy giá trị nhỏ nhất của số tốt cần tìm là 11. Bài 15. (VN TST 2000) Xét 2000 đường tròn bán kính r = 1 trên mặt phẳng sao cho không có hai đường tròn nào tiếp xúc với nhau và mỗi đường tròn cắt ít nhất với hai đường tròn khác. Hãy tìm giá trị nhỏ nhất của số giao điểm của các đường tròn này. Giải. Gọi G là tập hợp các đường tròn trong mặt phẳng thỏa mãn điều kiện đã cho và S là tập hợp tất cả các giao điểm của chúng. Với mọi C ∈ G, x ∈ S , ta xét hàm số f ( x, C ) , trong đó: • f ( x, C ) = 0 nếu x ∉ C . 1 • f ( x, C ) = nếu x ∈ C và có đúng k đường tròn đi qua x. k Với mỗi x ∈ S , ta thấy rằng ∑ f ( x, C ) = 1 . C∈G 1 Với mỗi C ∈ G , chọn một điểm x ∈ C ∩ S sao cho f ( x, C ) = đạt giá trị nhỏ nhất. k Gọi C1 , C2 , C3 ,..., Ck −1 là các đường tròn khác C cùng đi qua x. Do mỗi đường tròn cắt ít nhất hai đường tròn khác nên = với i 1, 2,3,..., k − 1 thì gọi x1 , x2 , x3 ,..., xk −1 tương ứng là các giao điểm khác x của các đường tròn nói trên với C. Do các đường tròn có bán kính khác nhau nên xi ≠ x j với mọi i ≠ j ,1 ≤ i, j ≤ k − 1 . 1 1 Suy ra: ∑ f ( x, C ) ≥ k + (k − 1) k = x∈S 1. Từ đó, ta thấy rằng N =S =∑ ∑ f ( x, C ) =∑ ∑ f ( x, C ) ≥ G .1 =2000 . x∈S C∈G C∈G x∈S 20