Luận văn Thạc sĩ Toán học: Về bài toán cực trị trong hình học tổng hợp

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

Thêm vào BST

Báo xấu

29
lượt xem 4
download

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

Mục đích nghiên cứu của đề tài luận văn 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ổng hợp để hình thành một tài liệu giảng dạy chuyên đề mồi dưỡng học sinh khá, giỏi. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Về bài toán cực trị trong hình học tổng 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ị 3 1.1 Tổng quan về bài toán hình học tổ hợp . . . . . . . . . . . . . . 3 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 . . . . . . . . . . . . . . . . . . 4 1.2.1 Một số nguyên lý . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Phương pháp đếm hai lần (Double Counting) . . . . . . . 6 1.3 Một số ví dụ về bài toán hình học tổ hợp . . . . . . . . . . . . . 8 1.3.1 Các bài toán đếm trong hình học tổ hợp . . . . . . . . . 8 1.3.2 Các bài toán chứng minh trong hình học tổ hợp . . . . . 8 Chương 2 Một số bài toán về cực trị trong hình học tổ hợp 22 2.1 Bài toán về tìm giá trị lớn nhất . . . . . . . . . . . . . . . . . . . 22 2.2 Bài toán về tìm giá trị nhỏ nhất . . . . . . . . . . . . . . . . . . . 36 2.3 Bài 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 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ý 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 Nm = | Ai1 ∩ Ai2 ∩ · · · ∩ Aim | 1
• Xét đoạn thẳng có độ dài lớn nhất (nhỏ nhất) trong một số hữu hạn các đoạn thẳng. • Xét góc lớn nhất (nhỏ nhất) trong một số hữu hạn góc. • Xét đa giác có diện tích hoặc chu vi lớn nhất (nhỏ nhất) trong một số hữu hạn các đa giác. • Xét khoảng cách lớn nhất (nhỏ nhất) trong một số hữu hạn khoảng cách giữa hai điểm hoặc khoảng cách từ một điểm đến một đường thẳng. • Xét các điểm là đầu mút của một đoạn thẳng, xét các điểm ở phía trái nhất hoặc ở phía phải nhất của một đoạn thẳng (giả thiết là đoạn thẳng đó nằm ngang). Nguyên lý Dirichlet Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet đề xuất từ thế kỷ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ một mệnh đề rất đơn giản gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý “chuồng chim bồ câu”: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim. Dạng đơn giản nhất của nguyên lý Dirichlet, hay còn gọi là nguyên lý nhốt thỏ vào lồng, như sau: Nếu nhốt n + 1 thỏ vào n lồng thì tồn tại một lồng có ít nhất 2 con thỏ. Tổng quát: Nếu n > 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: 2(2 + 1) 3(3 + 1) S1 = 2, S2 = 4 = 1 + , S3 = 1 + = 7, . . . 2 2 6
n(n + 1) Từ đó ta đi tới chứng minh bằng quy nạp: Sn = 1 + . 2 k(k + 1) Giả sử đúng với n = k . Suy ra Sk = 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: k(k + 1) (k + 1)(k + 2) Sk+1 = Sk + (k + 1) = 1 + + (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). (1) 2 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). (3) 2 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 2 n2 − 3n + 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 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 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)] Cnk = k! n(n − 1) 7·6·5 Chẳng hạn: Cn2 = , C73 = = 35. Ta cũng nhắc lại ở đây công 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 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: 7·6·5·4 C74 = = 35 4! 1.3.2 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 hơn 45◦ và nằm trong đường tròn có bán kính nhỏ hơn . 5 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 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 4 đã 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 Gọi hai điểm bất kì M, N nằm trong tam giác đều ABC có cạnh bằng , 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 ). - 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 trên các cạnh BC, CA, AB thỏa mãn BAD [ + CBE[ + ACI d = 120◦ . Chứng minh 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 BAD [ < BAP [ , CBE [ < ACI [ ⇒ BAD+ d < ACP [ CBE[ + ACI d = BAP [ + CBP [ + ACP [. Theo giả thiết BAD [ + CBE [ + ACId = 120◦ ⇒ BAP [ + CBP [ > 120◦ . [ + ACP Nếu P trùng với tâm đường tròn ngoại tiếp tam giác ABC thì suy ra BAD [ + CBE d = 30◦ + 30◦ + 30◦ = 90◦ . [ + ACI Mâu thuẫn với giả thiết BAD [ + CBE[ + ACId = 120◦ . Suy ra P khác O. Từ đó 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 BAP [ + CBP [ + ACP [ =K\MP + C \ KM + AKN [
Lời giải. Ta tưởng tượng rằng các ô vuông được kẻ sao cho cạnh của nó nằm theo phương nằm ngang và thẳng đứng. Để trở về đỉnh ban đầu, ta đi lên trên bao nhiêu bước thì đi xuống dưới bấy nhiêu bước, đi sang trái bao nhiêu bước thì phải đi về bên phải bấy nhiêu bước. Do đó tổng số bước đi phải là số chẵn. Bài toán 1.3.12. [3] Cho một đa giác lồi. Chứng minh rằng tồn tại một hình bình hành có diện tích không quá hai lần diện tích đa giác sao cho các đỉnh đa giác nằm trong hoặc trên cạnh của hình bình hành. Lời giải. Gọi d là đường thẳng chứa cạnh CD của đa giác, A là điểm nằm trên đa giác và có khoảng cách đến đường thẳng d là lớn nhất, qua A kẻ đường thẳng song song với CD. Gọi B và E là hai đỉnh có khoảng cách đến AD là lớn nhất về hai phía AD. Qua B và E kẻ đường thẳng song song với AD, các đường thẳng này tạo thành hình bình hành P QM N . Suy ra các đỉnh của đa giác nằm trong hoặc trên cạnh của hình bình hành P QM N . Suy ra SAED + SABD ≤ SABCDEF (dấu bằng xảy ra khi đa giác là tứ giác). Mà 1 1 SAED + SABD = SP QM N ⇒ SP QM N ≤ SABCDEF ⇒ SP QM N ≤ 2SABCDEF . 2 2 Bài toán 1.3.13. [3] Mỗi một điểm trong mặt phẳng được tô màu bởi hai màu xanh hoặc đỏ. Chứng minh rằng luôn tồn tại một tam giác đều có ba đỉnh cùng màu. Lời giải. Gọi tam giác đều đó là ABC . Ba điểm A, B, C không cùng màu. Giả sử A, B cùng màu đỏ và C màu xanh. Kéo dài AB, AC sao cho BE = AB, CI = AC . Suy ra tam giác AEI đều. Gọi D là trung điểm EI kéo dài DB, DC sao cho BM = BD, CN = CD. Suy ra tam giác DM N là tam giác đều và M, N, A thẳng hàng. Do đó các tam giác CM E, ABM, BED, CDI là tam giác đều. • Tam giác ABM có A, B đỏ suy ra M xanh. • Tam giác CM E có C, M xanh suy ra E đỏ. • Tam giác BED có B, E đỏ suy ra D xanh. Xét tam giác CDI : • Nếu I màu xanh suy ra tam giác CDI có ba đỉnh cùng màu. • Nếu I đỏ suy ra tam giác AEI có ba đỉnh màu đỏ. Vậy ta luôn tồn tại tam giác CDI hoặc AEI cùng có ba đỉnh cùng màu. 13
Bài toán 1.3.14. [3] Mỗi điểm trên mặt phẳng được tô bằng mày đen hoặc đỏ. Chứng minh rằng ta có thể tìm được ba điểm cùng màu mà mỗi cặp điểm có khoảng cách bằng một hoặc có thể tìm được ba điểm cùng màu có khoảng √ cách bằng 3 bởi hai màu xanh hoặc đỏ. Chứng minh rằng luôn tồn tại một tam giác đều có ba đỉnh cùng màu. Lời giải. Giả sử không tồn tại 3 điểm cùng màu mà mỗi cặp điểm cách nhau bằng 1. Ta sẽ chứng minh rằng ta có thể tìm được ba điểm cùng màu và cách √ nhau bằng 3. Theo giả thiết, suy ra tồn tại hai điểm khác nhau mà khoảng cách bằng 1, ta lấy hai điểm A, B khác có khoảng cách bằng 2. Gọi I là trung điểm AB , IA = IB = 1 và điểm I cùng màu với A hoặc B . Giả sử I và B cùng màu đỏ, suy ra A màu đen, dựng hai tam giác đều IBC và IBD. Do đó C và D đối xứng nhau qua AB , hai tam giác đều này có cạnh bằng 1. Theo giả thiết trên không tồn tại 3 điểm cùng màu, mỗi cặp điểm cách nhau bằng • D và C màu đen, • A, D, C màu đen. DC cắt AB tại H suy ra DH vuông góc AB và HI = HB . Suy ra √ 3 √ DH = ⇒ DH = 3. 2 Tam giác DAB có IA = IB = ID = 1. [ = 90◦ , DAB Vậy suy ra ADB [ = 30◦ , DAC [ = 60◦ . Do đó tam giác ADC là tam √ giác đều có cạnh bằng 3. Ba điểm A, D, C cùng màu đen và cách nhau một √ khoảng bằng 3. Bài toán 1.3.15. [3] Bàn cờ vua 8 × 8, các ô được tô trắng đen xen kẽ nhau. Ở mỗi bước xét một hàng hoặc cột, sau đó trong hàng (hoặc cột) chọn ra tay thay đổi tất các các ô trong hàng (hoặc cột) theo quy tắc: ô đen tô thành ô trắng và ngược lại. Hỏi bằng cách ấy có thể đến một lúc nào đó trên bàn cờ chỉ có duy nhất một ô đen được không? Chứng minh. Lời giải. Giả sử trước khi tô lại một hàng (hoặc một cột) chọn ra, có k ô đen và 8 − k ô trắng. Sau khi tô lại hàng (hoặc cột) sẽ có k ô trắng và 8 − k ô đen. Sau một lần đổi số ô đen là: (8 − k) − k = 8 − 2k = 2(4 − k). Thay đổi một số chẵn ô đen. Như vậy tính chẵn, lẻ của ô đen thay đổi suốt quá trình ta tô màu, bàn cờ lúc đầu có 32 ô đen. Không lúc nào nhận được trên bàn cờ chỉ có một ô đen. 14
Bài toán 1.3.16. [3] Trong mặt phẳng tọa độ xOy , có tồn tại đa giác đều 45 cạnh mà các đỉnh của nó là các số hữu tỉ không? Lời giải. Đa giác đều A1 A2 A3 . . . A45 , giả sử tam giác A1 A16 A31 là tam giác đều có các đỉnh là các số hữu tỉ bao gồm tam giác A1 A16 A31 bằng hình vuông ABCD. Tọa độ của A1 A16 A31 là các số hữu tỉ. Suy ra tọa độ A, B, C, D cũng là các số hữu tỉ. Do đó diện tích hình vuông ABCD và các tam giác AA1 A16 , BA16 A31 , DA1 A31 là các số hữu tỉ. Suy ra SA1 A16 A31 = SABCD − SAA1 A16 − SBA16 A31 − SDA1 A31 là các số hữu tỉ. 3 Mặt khác SA1 A16 A31 = A1 A16 là số vô tỉ. Vậy điều đó không xảy ra tọa độ các 4 đỉnh là số hữu tỉ. Bài toán 1.3.17. [3] Cho đa giác ABCDEGHK có các góc ở đỉnh bằng nhau, độ dài các cạnh là số nguyên. Chứng minh cặp cạnh đối song song và bằng nhau. Lời giải. Theo giả thiết các góc có đỉnh bằng nhau, theo công thức tính tổng các đa giác lồi. Suy ra mỗi góc ở đỉnh đa giác lồi có giá trị là: (n − 2)180◦ 6 · 180◦ = = 135◦ . n 8 Kéo dài cạnh của đa giác ABCDEGHK cắt nhau thành tứ giác P QM N và IJSR. Suy ra AK = 180◦ − KAB P[ [ = 180◦ − 135◦ = 45◦ . Tương tự các góc P[KA = 45◦ ⇒ tam giác P AK là tam giác vuông cân. Suy ra tứ giác P QM N là hình chữ nhật. Do đó AB song song EG và CD song song với HK . Chứng minh tương tự IJRS cũng là hình chữ nhật. Suy ra BC song song GH, DE song song với AK . Tam giác P AK là tam giác vuông cân. Suy ra AK BC ED GH AP = √ , BQ = √ , M E = √ , N G = √ , 2 2 2 2 AK BC P Q = P A + AB + BQ = √ + AB + √ , 2 2 DE GH M N = M E + EG + GN = √ + EG + √ . 2 2 15
Có P QM N là hình chữ nhật suy ra P Q = M N . Suy ra AK BC DE GH √ + AB + √ = √ + EG + √ 2 2 2 2 1 √ (AK + BC − DE − GH) = EG − AB. 2 Giả thiết độ dài các cạnh là số nguyên. Suy ra AK +BC +DE −GH và EG−AB là các số nguyên. Do đó vế trái là số vô tỉ, vế phải là số nguyên. Suy ra EG − AB = 0 ⇒ EG = AB. Chứng minh tương tự CD = HK và AK = DE, BC = GH . Bài toán 1.3.18. [3] Cho hai hình vuông ABCD, P QM N có cạnh bằng nhau, mỗi cạnh hình vuông được tô màu giống nhau xanh hoặc đỏ, hai hình này xếp trồng lên nhau tạo thành bát giác. Chứng minh rằng bát giác có tổng độ dài bốn cạnh màu đỏ bằng tổng độ dài bốn cạnh màu xanh. Lời giải. Xét bát giác AP N QCM DN nhận thấy: SABCD +SP AB +SQBC +SM CD +SN DA = SP QM N +SAP N +SBP Q +SCQM +SDM N . Gọi khoảng cách từ A, B, C, D đến các cạnh N P, P Q, QM, M N theo thứ tự h1, h2, h4 và khoảng cách từ P, Q, M, N đếm các cạnh AB, BC, CD, DA theo thứ tự là h5, h6, h7, h8. Hai hình vuông có cạnh bằng nhau suy ra SABCD = SP QM N . Các tam giác AA1 A8 , P A1 A2 , BA2 A3 , QA3 A4 , CA4 A5 , M A5 A6 , DA6 A7 , N A7 A8 là các tam giác vuông có AA \ 1 A8 = P\ A1 A2 = QA \ 3 A4 = M \ A5 A6 = N\ A7 A8 . Suy ra các tam giác đồng dạng h1 h2 h3 h4 h5 h6 h7 h8 = = = = = = = = k. A1 A8 A2 A3 A4 A5 A6 A7 A1 A2 A3 A4 A5 A6 A7 A8 Suy ra A1 A8 + A2 A3 + A4 A5 + A6 A7 = A1 A2 = A3 A4 = A5 A6 + A7 A8 . Bài toán 1.3.19. [3] Chứng minh rằng nếu ba đỉnh của một hình bình hành là các điểm nguyên. Chứng minh rằng đỉnh thứ tư cũng là điểm nguyên. 16
Lời giải. Giả sử hình bình hành ABCD có ba đỉnh A, B, C là các điểm nguyên. Giả sử tọa độ của A(x1 , y1 ); B(x2 , y2 ); C(x3 , y3 ) với x1 , x2 , x3 , y1 , y2 , y3 là các số nguyên, gọi giao điểm hai đường chéo là I, ABCD là hình bình hành. Gọi M, Q, J, N, P lần lượt là chân đường vuông góc hạ từ các điểm A, D, I, B, C xuống trục tung, ta có: AM + CP = 2IJ = BN + DQ. Suy ra: x + 1 + x3 = x2 + x4 x 4 = x1 + x3 − x2 Suy ra vế phải là số nguyên. Vậy x4 là số nguyên. Chứng minh tương tự được y4 là số nguyên. Bài toán 1.3.20. [3] Cho tam giác ABC mà các đỉnh của nó là các điểm nguyên. Chứng minh rằng 2SABC là số nguyên. Lời giải. Ba điểm A, B, C là các điểm nguyên, dựng hình bình hành ABCD. Theo bài 1.3.19, đỉnh D là điểm nguyên. Suy ra SABCD = 2SABC . Qua D và B dựng hình chữ nhật BEDI sao cho các cạnh song song với trục tung và trục hoành. Do đó các đỉnh I và E là các điểm nguyên. Suy ra: SABCD = SBEDI − SIQAP − SAQD − SAP B − SCN EM − SBCN − SCM D . Mặt khác, tam giác AQD = CN B ; tam giác AP B = CM D. Suy ra SAQD = SBCN , SAP B = SCM D , SIQAP − SAQD − SAP B − SCN EM − SBCN − SCM D = SIQAP − 2SAQD − 2SAP B − SCN EM = IQ · QA + AQ · QD + AP · P B + N C · CM là số nguyên. Suy ra SABCD = 2SABC là số nguyên. Bài toán 1.3.21. [3] Cho ngũ giác có tất cả các cạnh bằng a. Chứng minh rằng có thể đặt trong đó một tam giác đều cạnh a. Lời giải. Giả sử đường chéo AC lớn nhất của ngũ giác ABCDE có các cạnh bằng a. Ta sẽ chứng minh có tam giác đều cạnh a nằm trong tứ giác ACDE . Trước hết ta chứng minh hai mệnh đề 17