Tài liệu Về bài toán cực trị trong hình học tổ hợp

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỖ PHƯƠNG THẢO VỀ BÀI TOÁN CỰC TRỊ TRONG HÌNH HỌC TỔ HỢP LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN-2019 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỖ PHƯƠNG THẢO VỀ BÀI TOÁN CỰC TRỊ TRONG HÌNH HỌC TỔ HỢP CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP MÃ SỐ: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. TRỊNH THANH HẢI THÁI NGUYÊN-2019 Mục lục Trang Mở đầu 1 Chương 1 Kiến thức chuẩn bị 1.1 Tổng quan về bài toán hình học tổ hợp . . . . . . . . . . . . . . 1.2 Một số nguyên lý, phương pháp giải toán thường gặp trong lời giải các bài toán hình học tổ hợp . . . . . . . . . . . . . . . . . . 1.2.1 Một số nguyên lý . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Phương pháp đếm hai lần (Double Counting) . . . . . . . 1.3 Một số ví dụ về bài toán hình học tổ hợp . . . . . . . . . . . . . 1.3.1 Các bài toán đếm trong hình học tổ hợp . . . . . . . . . 1.3.2 Các bài toán chứng minh trong hình học tổ hợp . . . . . 3 3 Chương 2 2.1 Bài 2.2 Bài 2.3 Bài 4 4 6 8 8 8 Một số bài toán về cực trị trong hình học tổ hợp 22 toán về tìm giá trị lớn nhất . . . . . . . . . . . . . . . . . . . 22 toán về tìm giá trị nhỏ nhất . . . . . . . . . . . . . . . . . . . 36 toán liên quan đến cực trị hình học tổ hợp . . . . . . . . . . 43 Kết luận 46 ii Mở đầu Từ thời xa xưa vấn đề toán học được ra đời từ rất sớm từ các hoạt động thực tiễn của con người, trong đó có tư duy về hình học tổ hợp, ví dụ: Ở những nước châu Á, trong số đó có Ấn Độ, các nhà toán học Jaina đã nghiên cứu ra dãy số, các dãy cấp số, hoán vị và tổ hợp; Thời Trung Quốc cổ đại, người ta đã biết đến biểu đồ tổ hợp phức còn gọi là “hình vuông thần kì”; Thời kì cổ đại ở Hy Lạp đã có những nhà triết học thông thái đặc biệt là nhà triết học Kxenorat đã biết từ những chữ cái cho trước lập thành bảng chữ số. . . Nhưng phải đến khoảng thế kỉ XVII – XVIII với những công trình nghiên của như Pascal, Fermat, Euler. . . thì toán học tổ hợp mới thực sự hình thành như một nhánh của toán học. Toán tổ hợp có tính hấp dẫn, lý thú của toán học nói chung và toán sơ cấp nói riêng. Nội dung của toán tổ hợp phong phú và được ứng dụng nhiều trong thực tế đời sống. . . Hình học tổ hợp là một nhánh không thể thiếu toán tổ hợp, là những bài toán hay, thú vị và thường xuyên xuất hiện trong các cuộc thi học sinh giỏi Quốc gia, Olympic toán quốc tế, thi Olympic sinh viên giữa các trường đại học, cao đẳng trong cả nước. Ở Trường Đại học Khoa học- Đại học Thái Nguyên đã có học viên Lê Thị Bình đã làm luận văn Thạc sĩ với đề tài “Các bài toán về hình học tổ hợp” nhưng chưa luận văn đề cập một cách hệ thống đến dạng toán “Cực trị trong hình học tổ hợp”. Chính vì với mong muốn tìn hiểu sâu về các toán cực trị trong hình học tổ hợp, em đã chọn đề tài “Các bài toán cực trị hình học tổ hợp” làm đề tài luận văn thạc sĩ của mình. Mục đích nghiên cứu của luận văn được xác định là: Sưu tầm, nghiên cứu và trình bày một cách có chọn lọc về bài toán cực trị trong hình học tổ hợp để hình thành một tài liệu giảng dạy chuyên đề bồi dưỡng học sinh khá, giỏi. Nội dung chính của luận văn được trình bày thành hai chương: Chương 1: Trong chương này, luận văn trình bày một số nguyên lý và phương pháp thường gặp trong các lời giải của bài toán hình học tổ hợp, kèm theo các ví dụ, các bài tập minh họa. Chương 2: Nội dung chương 2 được dành riêng để trình bày lời giải của một số bài toán cực trị hình học tổ hợp dành cho học sinh khá, giỏi và được sắp 1 xếp theo hai dạng chính là: Bài toán liên quan đến tìm giá trị lớn nhất, tìm giá trị nhỏ nhất trong hình học tổ hợp. Luận văn này được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên dưới sự hướng dẫn tận tình của PGS. TS Trịnh Thanh Hải. Em chân thành cảm ơn thầy Trịnh Thanh Hải đã tận tình hướng dẫn em triển khai đề tài của luận văn này. Em xin chân thành cảm ơn gia đình, bạn bè cùng các anh chị đã tạo điều kiện để em hoàn thành đề tài này. Tuy nhiên điều kiện về năng lực bản thân còn hạn chế, luận văn chắc chắn không tránh khỏi những thiếu sót. Kính mong nhận được sự đóng góp ý kiến của các thầy cô giáo, bạn bè và đồng nghiệp để bài luận văn của em được hoàn thiện hơn. Em xin trân trọng cảm ơn! Thái Nguyên, tháng 05 năm 2019 Học viên Đỗ Phương Thảo 2 Chương 1 Kiến thức chuẩn bị 1.1 Tổng quan về bài toán hình học tổ hợp Trước tiên, luận văn xin nhắc lại một vài dạng toán tổ hợp được trình bày trong luận văn: (i) Bài toán cực trị tổ hợp: Dạng 1: Tìm số nguyên dương k nhỏ nhất (lớn nhất) sao cho mọi tập A mà | A |= k là hữu hạn đều có tính chất T nào đó. Ví dụ 1.1.1. Gọi A là tập tất cả các số tự nhiên lẻ không chia hết cho 5 và nhỏ hơn 30. Tìm số k nhỏ nhất sao cho mỗi tập con của A gồm k phần tử đều tồn tại hai số chia hết cho nhau? Ví dụ 1.1.2. Cho tập A gồm 16 số nguyên dương đầu tiên. Hãy tìm số nguyên dương k nhỏ nhất có tính chất: Trong mỗi tập con có k phần tử của A đều tồn tại hai số phân biệt a, b sao cho a2 + b2 là số nguyên tố (VMO 2004). Với bài toán dạng này, chúng ta thường xét một tập A có tính chất đặc biệt nào đó sao cho | A |= m và A không thỏa mãn tính chất T , từ đó suy ra được kmin > m + 1. Tiếp theo ta chứng minh mọi tập A mà | A |= m + 1 đều có tính chất T , từ đó ta tìm được kmin = m + 1. Để chứng minh mọi tập A mà | A |= m + 1 đều có tính chất T thì ta có thể sử dụng nguyên lí Dirichlet hoặc dựa vào tính chất tập A. Dạng 2: Tìm số phần tử lớn nhất (nhỏ nhất) của tập A gồm các phần tử có tính chất T . Ví dụ 1.1.3. Cho A là tập hợp gồm 8 phần tử. Tìm số lớn nhất các tập con gồm 3 phần tử của A sao cho giao của hai tập bất kì trong các tập con này không phải là tập gồm hai phần tử. Ví dụ 1.1.4. Trong một cuộc thi có 11 thí sinh tham gia giải 9 bài toán. Hai thí sinh bất kì giải chung với nhau không quá một bài. Tìm k lớn nhất để mọi bài toán có ít nhất k thí sinh giải được. 3 Để giải bài toán này, chúng ta thường thực hiện theo cách sau: Đặt | A |= k , bằng các lập luận ta chứng minh k < m (k > m). Sau đó ta xây 0 0 dựng một tập A thỏa tính chất T và | A |= m. (ii) Bài toán cực trị hình học tổ hợp Các bài toán cực trị tổ hợp (i), mà tập A gồm các đối tượng hình học thì thường được xếp vào dạng Bài toán cực trị hình học tổ hợp. Ví dụ 1.1.5. Cho một đa giác đều 2007 đỉnh. Tìm số nguyên dương k nhỏ nhất thoả mãn tính chất: Trong mỗi cách chọn k đỉnh của đa giác, luôn tồn tại 4 đỉnh tạo thành một tứ giác lồi mà 3 trong số 4 cạnh của tứ giác là cạnh của đa giác đã cho (VMO 2007). Ví dụ 1.1.6. Cho 2006 điểm phân biệt trong không gian, không có bốn điểm nào thẳng hàng. Số k gọi là số tốt nếu ta có thể điền lên mỗi đoạn thẳng nối hai điểm trong 2006 điểm đã cho một số tự nhiên không vượt quá k sao cho với mọi tam giác có ba đỉnh trong 2006 điểm đã cho thì có hai cạnh được điền hai số bằng nhau và cạnh còn lại thì được điền số lớn hơn. Tìm số tốt có giá trị nhỏ nhất (TST Việt Nam 2006). Phương pháp giải các bài toán cực trị hình học tổ hợp này sẽ được luận văn trình bày chi tiết trong nội dung của Chương 2. 1.2 1.2.1 Một số nguyên lý, phương pháp giải toán thường gặp trong lời giải các bài toán hình học tổ hợp Một số nguyên lý Nguyên lý cộng Quy tắc cộng: Nếu Ei (i = 1, . . . , k ) với k sự kiện thỏa mãn: (i) Không có hai sự kiện nào trong số chúng xảy ra đồng thời; (ii) Ei có thể xảy ra theo ni cách thì một trong k sự kiện có thể xảy ra theo (n1 + n2 + · · · + nk ) cách. Nguyên lý nhân Quy tắc nhân: Nếu Ei (i = 1, . . . , k ) với k sự kiện thỏa mãn. Và E1 có thể xảy ra theo n1 cách, E2 có thể xảy ra theo n2 cách (không phụ thuộc đến việc E1 xảy ra như thế nào); E3 có thể xảy ra theo n3 cách (không phụ thuộc đến việc E2 , E1 xảy ra như thế nào), . . . , Ek có thể xảy ra theo nk cách (không phụ thuộc đến (k − 1) sự kiện trước xảy ra như thế nào), thì k sự kiện có thể xảy ra đồng thời theo n1 · n2 · n3 . . . nk cách. 4 Nguyên lý bù trừ Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này, ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1 , A2 là hai tập hữu hạn, khi đó: [ | A1 A2 |=| A1 | + | A2 | − | A1 ∩ A2 | Từ đó, với ba tập hữu hạn A1 , A2 , A3 ta có: | A1 ∪ A2 ∪ A3 |=| A1 | + | A2 | + | A3 | − | A1 ∩ A2 | − | A1 ∩ A3 | − | A3 ∩ A2 | + | A1 ∩ A2 ∩ A3 | . Và bằng quy nạp, với k tập hữu hạn A1 , A2 , . . . , Ak ta có: | A1 ∩ A2 ∩ · · · ∩ Ak |= N1 − N2 + N3 − · · · + (−1)k−1 Nk . Trong đó Nm (1 ≤ m ≤ k ) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là: X | Ai1 ∩ Ai2 ∩ · · · ∩ Aim | Nm = 1 km (n, k, m) là các số tự nhiên) thì khi nhốt n con thỏ vào m lồng sẽ tồn tại một lồng chứa ít nhất k + 1 thỏ. Thật vậy, giả sử lồng nào cũng có không quá k thỏ thì m lồng có không quá mk thỏ, ít hơn n thỏ, vô lý. 1.2.2 Phương pháp đếm hai lần (Double Counting) Ý tưởng của phương pháp đếm hai lần: Với bài toán đếm, nếu ta sử dụng hai phương pháp đếm khác nhau thì kết quả phải trùng nhau. Ví dụ 1.2.1. [3] Người ta kẻ n đường thẳng, trong đó không có hai đường thẳng nào song song với ba đường thẳng nào đồng quy. Hỏi n đường thẳng đó chia mặt phẳng thành bao nhiêu miền. Chứng minh. Với n = 1 chia mặt phẳng thành 2 miền, Với n = 2 chia mặt phẳng thành 4 miền, Với n = 3 chia mặt phẳng thành 7 miền. Gọi Sn là số miền con chia bởi n đường thẳng. Suy ra: S1 = 2, S2 = 4 = 1 + 2(2 + 1) 3(3 + 1) , S3 = 1 + = 7, . . . 2 2 6 Từ đó ta đi tới chứng minh bằng quy nạp: Sn = 1 + n(n + 1) . 2 k(k + 1) . Khi đó k + 1 đường thẳng. Vậy 2 đường thẳng k + 1 cắt k đường thẳng trước tại thành k + 1 miền mới. Suy ra: Giả sử đúng với n = k . Suy ra Sk = 1 + Sk+1 = Sk + (k + 1) = 1 + k(k + 1) (k + 1)(k + 2) + (k + 1) = 1 + . 2 2 Vậy đẳng thức đúng. Ví dụ 1.2.2. Cho n điểm A1 , A2 , . . . , An trên cùng mặt phẳng sao cho không có 3 điểm nào thẳng hàng, không có 4 điểm nào tạo thành hình bình hành. Gọi I1 , I2 , . . . , Im là tất cả các trung điểm của các đoạn tạo thành từ các đoạn Ai Aj (1 ≤ i < j ≤ n). Gọi N là tổng độ dài của mọi đoạn thẳng với hai đầu mút là Ai Aj . M là tổng độ dài của mọi đoạn thẳng với d là hai đầu mút. Gọi các đỉnh của đa giác đều đã cho là: Ii , Ij . Chứng minh rằng: n2 − 3n + 2 M≤ · N. 4 Chứng minh. Ta có M, N, P lần lượt là trung điểm của AB, BC, CA thì ta có: 1 M N + N P + P M = (AB + BC + CA). 2 (1) Với M, N, P, Q, R, S lần lượt là trung điểm của AB, CD, BC, DA, AC, BD thì ta có: 1 M N + P Q + RS ≤ (AB + BC + CD + DA + AC + BD). 2 (2) Dễ thấy (1) là hiển nhiên vì theo tính chất đường trung bình của tam giác còn (2.3.1) ta dựa vào nhận xét sau: 1 P Q ≤ P K + KQ = (AB + CD). 2 (3) Do đó dựa vào (1) và (2.3.1) là đúng. Khi đó, với n điểm A1 , A2 , . . . , An ta thiết lập các tam giác và tứ giác, rồi lập ra mọi đẳng thức (1) và mọi bất đẳng thức (2.3.1) và tương ứng cộng vế với vế ta thu được bất đẳng thức (3). Bây giờ với bất đẳng thức (3) ta xét các giá trị của hai vế theo cách khác nhau là M . 2 Mỗi đoạn Ii Ij thuộc vào n − 2 tam giác và Cn−2 tứ giác nên vế phải (3) bằng: 1 n2 − 3n + 2 2 (n − 2 + Cn−2 )·N = · N. 2 4 n2 − 3n + 2 Như vậy ta sẽ thu được: M ≤ · N . Vậy các đa giác đều được lát 4 mặt phẳng chỉ có tam giác đều, hình vuông và lục giác đều. 7 1.3 1.3.1 Một số ví dụ về bài toán hình học tổ hợp Các bài toán đếm trong hình học tổ hợp Trong các bài toán về đếm số đoạn thẳng, số góc, số đa giác, đôi khi ta cần dùng đến công thức tính số tổ hợp chập k của n phần tử (tức là số tập hợp con gồm k phần tử trong n phần tử): n(n − 1)(n − 2) . . . [n − (k − 1)] k! n(n − 1) 7·6·5 , C73 = = 35. Ta cũng nhắc lại ở đây công Chẳng hạn: Cn2 = 2 3! n(n − 3) thức tính số đường chéo của đa giác lồi n cạnh: . 2 Bài toán 1.3.1. [1] Một n- giác lồi (n > 3) có nhiều nhất bao nhiêu đường Cnk = chéo có độ dài lớn nhất? Lời giải. Ta có một đa giác lồi có AC là đường chéo lớn nhất và có hai cạnh bằng AC , đó là AB và AD. Ta sẽ chứng minh với mọi đa giác lồi có đường chéo lớn nhất bằng số cạnh a > 2. Trong số các cạnh đó (các cạnh này không là ba cạnh của một tam giác), ta chọn được hai cạnh không có đỉnh chung, chẳng hạn là AB và C D. Ta sẽ chứng minh tồn tại một đường chéo có độ dài lớn hơn a. Thật vậy, vì AC + BD > AB + CD = a + a = 2a, nên tồn tại một trong hai đường chéo AC, BD lớn hơn a, trái với giả thiết đường chéo lớn nhất bằng a. Vậy trong đa giác lồi, có nhiều nhất là hai cạnh có độ dài bằng đường chéo lớn nhất. Bài toán 1.3.2. [1] Kẻ tất cả các đường chéo của một đa giác lồi 7 cạnh. Biết rằng không có ba đường chéo nào đồng quy. Có bao nhiêu giao điểm của các đường chéo nằm trong đa giác? Lời giải. Mỗi giao điểm của hai đường chéo tương ứng duy nhất với một tứ giác lồi có các đỉnh là các đỉnh của đa giác. Do đó, có bao nhiêu tứ giác lồi thì có bấy nhiêu giao điểm của các đường chéo nằm trong đa giác. Gọi đa giác lồi là ABCDEF G, ta có M, N lần lượt là giao điểm của AC với BD và AC . P là giao điểm của BE và AD. Nên điểm M ứng với tứ giác ABCD, điểm N ứng với tứ giác ABCE , điểm P ứng với tứ giác ABDE . Số giao điểm phải tìm bằng: C74 = 1.3.2 7·6·5·4 = 35 4! Các bài toán chứng minh trong hình học tổ hợp Bài toán 1.3.3. [3] Cho 17 đường thẳng có tính chất: Mỗi đường thẳng cắt m hình chữ nhật cho trước thành hai tứ giác có tỉ số diện tích bằng , (m, n > 0). n 8 Chứng minh rằng ít nhất 5 trong các đường thẳng trên cùng đi qua một điểm. Lời giải. Nhận xét: Các đường thẳng đã cho không thể cắt hai cạnh kề nhau của hình chữ nhật, vì cắt hai cạnh kề nhau tạo thành tam giác và ngũ giác sẽ mâu thuẫn với giả thiết. Suy ra các đường thẳng này phải đi qua hai cạnh đối diện của hình chữ nhật (không đi qua đỉnh). Giả sử đường thẳng M N cắt hình chữ nhật tạo thành hai tứ giác là AM N D và M N CN . Suy ra: dt(AM N D) m = . dt(M BCN ) n Gọi P và Q là trung điểm của AD và BC , cắt M N tại E . Suy ra: (AM + DN )AD m PE m = ⇒ = (M B + CN )BC n EQ n Suy ra: PE m PE m = ⇒ = EQ + P E n+m PQ m+n Suy ra E cố định do tính chất đối xứng của hình chữ nhật. Do đó trên P Q tồn tại điểm F , đường thẳng nào đi qua F cũng cho kết quả tỉ số diện tích hai tứ m giác bằng . n Tương tự tồn tại hai điểm G và J trên trục đối xứng HK thỏa mãn bất cứ đường thẳng nào đi qua G và J đều thỏa mãn giả thiết chia hình chữ nhật m thành hai tứ giác có tỉ số diện tích bằng . Từ đó tồn tại bốn điểm E, F, G, J n trên P Q và HK thỏa mãn bất cứ đường thẳng nào đi qua cắt hai cạnh đối m diện hình chữ nhật thành hai tứ giác thỏa mãn tỉ số diện tích bằng . Như n vậy ta đã chỉ ra có “ 17 chú thỏ và 4 cái lồng”, đó là 17 đường thẳng và 4 điểm 17 − 1 E, F, G, J . Theo nguyên lý Dirichlet thì luôn có ít nhất 1 + [ ] = 5 đường 4 thẳng luôn đi qua 1 điểm. Bài toán 1.3.4. [3] Cho 19 điểm trong đó không có ba điểm nào thẳng hàng, nằm trong một lục giác đều có cạnh bằng 1. Chứng minh rằng luôn tồn tại một tam giác (đỉnh là ba trong 19 điểm trên) có ít nhất một góc không lớn 3 5 hơn 45◦ và nằm trong đường tròn có bán kính nhỏ hơn . Lời giải. Lục giác đều được chia thành 6 tam giác đều có cạnh bằng 1. Vậy ta 19 − 1 có “ 6 lồng và 19 thỏ”. Suy ra luôn có ít nhất 1 + [ ] = 4 điểm nằm trong 6 6 tam giác đó. Gọi 4 điểm nằm trong tam giác đều có cạnh bằng 1 là A, B, C, D. Vị trí của A, B, C, D được sắp xếp như sau: 9 • A, B, C, D là tứ giác lồi, suy ra ∠A + ∠B + ∠C + ∠D = 360◦ . Suy ra có ít nhất một góc ≤ 90◦ , giả sử ∠A ≤ 90◦ ⇒ ∠DAC + ∠CAB ≤ 90◦ . Vậy trong hai góc ∠DAC, ∠CAB luôn có một góc không lớn hơn 45◦ . • Có một điểm nằm trong tam giác tạo bởi ba điểm còn lại. Giả sử điểm D nằm trong tam giác ABC . - Nếu ∠CDB ≥ 90◦ ⇒ ∠DBC + ∠DCB ≥ 90◦ . Suy ra một trong hai góc ∠DBC, ∠DCB có một góc nhỏ hơn 45◦ ⇒ tam giác thỏa mãn là tam giác DBC . - Nếu ∠CDB < 90◦ ⇒ CAB < 90◦ . Suy ra ∠CAD hoặc ∠DAB luôn có một góc nhỏ hơn 45◦ ⇒ tam giác thỏa mãn là ACD hoặc ADB . Tam giác đều có cạnh bằng 1 ⇒ bán kính đường tròn ngoại tiếp tam giác là √ √ 3 1 1 1 9 3 3 · 25 < 27 ⇒ < ⇒ < ⇒ < . 3 27 25 3 25 3 5 Bài này đã sử dụng hai lần nguyên lý Dirichlet. Bài toán 1.3.5. [3] Cho tam giác đều có cạnh bằng 1, lấy 17 điểm tùy ý trong tam giác đều. Chứng minh rằng luôn tồn tại hai điểm trong số 17 điểm có 1 khoảng cách không vượt quá . 4 1 4 Lời giải. Chia tam giác đều thành 16 tam giác đều có cạnh bằng , từ 17 điểm đã cho luôn có một tam giác chứa ít nhất 2 điểm (kể cả điểm nằm trên cạnh). 1 , 4 đường thẳng M N cắt hai cạnh tam giác tại P và Q (giả sử hai cạnh AB, AC ). Gọi hai điểm bất kì M, N nằm trong tam giác đều ABC có cạnh bằng \ - Nếu M QA > 90◦ ⇒ tam giác AP Q là tam giác tù. Suy ra 1 M N < AQ < AB ≤ . 4 \ \ - Nếu M QA < 90◦ ⇒ P[ CQ = 180◦ − M QA ≤ 90◦ . Suy ra P QC là tam giác tù ⇒ M N ≤ P Q < P C ≤ BC . Vậy cả hai trường hợp ta luôn có BC > M N. Bài toán 1.3.6. [3] Cho điểm P nằm trong đa giác 2n cạnh, kẻ các đường thẳng qua P và mỗi đỉnh đa giác. Chứng minh rằng bao giờ cũng tìm được một cạnh của đa giác sao cho không có một đường thẳng nào nói trên cắt cạnh này. 10 Lời giải. Theo giả thiết cho đa giác có 2n cạnh. Suy ra đa giác có 2n đỉnh gọi đa giác đó là A1 A2 . . . Ak . . . A2n−1 A2n . Giả sử P nằm trên đường chéo nào đó chẳng hạn đường chéo A1 Ak . Suy ra đường thẳng P A1 và P Ak trùng nhau. Như vậy, 2n − 2 đường thẳng còn lại chỉ cắt phần trong tối đa của đa giác là 2n − 2 cạnh. Suy ra có ít nhất một cạnh của đa giác thỏa mãn bài toán. Điểm P không nằm trên bất cứ đường chéo nào của đa giác A1 A2 . . . Ak . . . A2n−1 A2n . Nối An với An+1 suy ra đường thẳng An An+1 chia đa giác A1 A2 . . . Ak A2n−1 A2n thành hai đa giác, mỗi đa giác có n cạnh, điểm P nằm ở một trong hai đa giác đó. Giả sử P nằm trong đa giác A1 A2 . . . An+1 . Từ P nối với các đỉnh A1 , A2 , . . . , Ak , . . . , A2n−1 , A2n . Vậy suy ra có n + 1 đường thẳng đó là P An+1 , P An+2 , . . . , P A1 không thể cắt các cạnh An+1 An+2 , An+2 An+3 , . . . , A2n A1 thỏa mãn bài toán. Bài toán 1.3.7. [3] Cho tứ giác ABCD. Chứng minh rằng bốn đường tròn có đường kính là bốn cạnh của tứ giác phủ kín miền tứ giác ABCD. Lời giải. Giả sử M là điểm trong tứ giác ABCD. Suy ra \ \ \ \ A MB + B MC + C MD + D M A = 360◦ . \ Không mất tính tổng quát, giả sử A M B là góc lớn nhất trong bốn góc \ \ \ \ \ A M B, B M C, C M D, D M A. Theo định lý Dirichlet suy ra A M B ≥ 90◦ ⇒ M nằm trong đường tròn đường kính AB . Vậy bốn đường tròn có đường kính AB, BC, CD, DA phủ kín miền tứ giác ABCD. Bài toán 1.3.8. [3] Trong mặt phẳng có năm điểm không có ba điểm nào thẳng hàng. Chứng minh rằng tồn tại ít nhất một tứ giác lồi có đỉnh là trong các điểm đã cho. Lời giải. Trước hết ta dựng bao lồi của năm điểm đã cho: (1) Nếu bao lồi là tứ giác, bài toán đã được chứng minh; (2) Nếu bao lồi là tam giác. Giả sử tam giác đó là ABC , khi đó điểm D và E nằm trong tam giác (D và E không nằm trên các cạnh của tam giác ABC vì không có ba điểm nào thẳng hàng). Suy ra điểm D nằm trong ba tam giác EAB, EBC, ECA. Giả sử D nằm trong tam giác EBC suy ra B hoặc C và D cùng thuộc nửa mặt phẳng bờ AE . Nếu là B thì tứ giác AEDB là lồi. Nếu là C thì tứ giác AEDC là tứ lồi cần chỉ ra. 11 Bài toán 1.3.9. [3] Có thể dùng ba hình vuông có cạnh bằng 4, phủ kín một hình vuông có cạnh bằng 5 hay không (với các hình vuông cạnh 4 không có phần chung nhau)? Lời giải. Gọi hình vuông có cạnh bằng 5 là ABCD. Giả sử có ba hình vuông cạnh bằng 4 phủ kín hình vuông ABCD (ba hình vuông có cạnh bằng 4 không √ có phần chung nhau). Độ dài đường chéo hình vuông cạnh 4 bằng 4 2 > 5. Theo Định lý Dirichlet suy ra bốn đỉnh A, B, C, D nằm trong ba hình vuông cạnh 4. Vậy suy ra có một hình vuông cạnh 4 chứa hai đỉnh vuông ABCD. Do đó đỉnh giao của ba hình vuông cạnh bằng 4 nằm trong hình vuông ABCD. Hạ AH⊥M N ⇒ AH ≤ 4. Gọi M và N là giao điểm hình vuông ABCD với hai cạnh hình vuông cạnh 4, AM, AN là cạnh huyền của tam giác ABM và tam giác ADN . Suy ra AM, AN ≥ 5. Áp dụng Định lý Pythagoras suy ra AM 2 = AH 2 + HM 2 ⇒ HM ≥ 3. Tương tự đối với tam giác vuông AHN ⇒ HN ≥ 3 ⇒ HM + HN ≥ 6. Mâu thuẫn. Vậy ABCD không thể nằm trọn trong ba hình vuông. Bài toán 1.3.10. [3] Cho tam giác đều ABC , các điểm D, E, I lấn lượt nằm d = 120◦ . Chứng minh [ + CBE [ + ACI trên các cạnh BC, CA, AB thỏa mãn BAD rằng các tam giác: BAD, CBE, ACI phủ kín tam giác đều ABC . Lời giải. Giả sử P là điểm nằm trong tam giác ABC mà các tam giác BAD, CBE, ACI không phủ điểm P . Từ đó suy ra d < ACP d = BAP [ < BAP [ , CBE [ < ACI [ ⇒ BAD+ [ CBE [ + ACI [ + CBP [ + ACP [. BAD d = 120◦ ⇒ BAP [ + CBE [ + ACI [ + CBP [ + ACP [ > 120◦ . Theo giả thiết BAD Nếu P trùng với tâm đường tròn ngoại tiếp tam giác ABC thì suy ra d = 30◦ + 30◦ + 30◦ = 90◦ . [ + CBE [ + ACI BAD d = 120◦ . Suy ra P khác O. Từ đó [ + CBE [ + ACI Mâu thuẫn với giả thiết BAD suy ra P A, P B, P C không bằng nhau. Kéo dài P A, P B, P C cắt đường tròn ngoại tiếp tam giác ABC tại K, M, N . Suy ra [ + CBP [ + ACP [ =K \ \ [ - Xem thêm -