Hình học trong bài toán lát gạch đa hoa

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN NGUYỄN THỊ QUỲNH BÀI TOÁN PHỦ VÀ BAO HÌNH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Hình học Người hướng dẫn khoa học: ThS. PHẠM THANH TÂM Hà Nội - 2014 LỜI CẢM ƠN Lời đầu tiên của khóa luận em xin gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn ThS.Phạm Thanh Tâm. Thầy đã giao đề tài và tận tình hướng dẫn em trong suốt quá trình hoàn thành khóa luận này. Em xin gửi lời cảm ơn của mình tới các thầy, cô giáo trong khoa Toán đã giảng dạy tận tình và giúp đỡ chúng em trong suốt quá trình học tập tại Khoa. Nhân dịp này em cũng xin bày tỏ lòng biết ơn chân thành của mình tới gia đình, bạn bè đã ở bên cổ vũ động viên giúp đỡ em trong suốt quá trình học tập vừa qua. Hà Nội, ngày 16 tháng 05 năm 2014 Sinh viên Nguyễn Thị Quỳnh 1 LỜI CAM ĐOAN Sau một thời gian nghiên cứu, tìm hiểu tài liệu cùng với sự hướng dẫn của thầy giáo ThS. Phạm Thanh Tâm em đã hoàn thành bài khoá luận của mình. Em xin cam đoan khoá luận này là kết quả của quá trình làm việc nghiêm túc với sự cố gắng nỗ lực của bản thân dưới sự hướng dẫn chỉ bảo tận tình của ThS. Phạm Thanh Tâm. Trong khi nghiên cứu khóa luận này, em đã tham khảo một số tài liệu ghi trong tài liệu tham khảo. Hà Nội, ngày 16 tháng 05 năm 2014 Sinh viên Nguyễn Thị Quỳnh 2 Mục lục Chương 1. Kiến thức cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Một số khái niệm mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Các tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4. Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Chương 2. Bài toán phủ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1. Lát mặt phẳng bằng những đa giác bằng nhau . . . . . . . . . . . . . . . . . . . . . . 10 2.2. Bài toán phủ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1. Bài toán phủ đa giác lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.2. Bài toán phủ một đoạn thẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.3. Bài toán phủ một hình vuông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3. Định lí Bloosphelt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4. Phủ bàn với những khăn hình chữ nhật . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5. Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.6. Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Chương 3. Bài toán bao hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1. Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2. Bài toán bao hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.1. Bài toán bao hình vuông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.2. Bao hình tam giác và đường tròn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3. Bài toán Malfatti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4. Bài tập đề nghị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3 MỞ ĐẦU 1. Lý do chọn đề tài Hình học tổ hợp là một nhánh không thể thiếu được của các bài toán tổ hợp nói chung, nó thường xuyên xuất hiện trong các đề thi học sinh giỏi ở mọi cấp. Khác với các bài toán trong lĩnh vực Giải tích, Đại số, Lượng giác, các bài toán của hình học tổ hợp thường liên quan nhiều đến các đối tượng là các tập hợp hữu hạn. Vì lẽ đó các bài toán này mang đặc trưng rõ nét của toán học rời rạc. Bài toán phủ và bao hình là một phần của hình học tổ hợp. Những bài toán này rất đa dạng về nội dung và phương pháp giải. Nhiều bài toán phát biểu rất đơn giản, với những kiến thức phổ thông ta cũng có thể hiểu được nhưng để giải được chúng thì cần đến một sự hiểu biết sâu sắc những kiến thức về hình học tổ hợp. Vì vậy, em đã chọn đề tài "Bài toán phủ và bao hình" nhằm mục đích tìm hiểu sâu hơn về những vấn đề trong hình học tổ hợp cũng như tìm ra được lời giải tối ưu cho những bài toán này. 2. Mục đích nghiên cứu Bước đầu làm quen với nghiên cứu khoa học và tìm hiểu sâu hơn về các bài toán phủ và bao hình và các vấn đề liên quan đến hình học tổ hợp. 3. Nhiệm vụ nghiên cứu Nghiên cứu một số chuyên đề về hình học tổ hợp, các bài toán về phủ hình và bao hình. Tìm ra lời giải và xây dựng hệ thống bài tập liên quan. 4. Đối tượng nghiên cứu Nghiên cứu các dạng bài toán phủ và bao hình trong hình học tổ hợp, các tính chất, định lí và ứng dụng có liên quan. 5. Phương pháp nghiên cứu Đọc tài liệu, phân tích, so sánh tổng hợp. 6. Cấu trúc khóa luận Ngoài phần mở đầu, danh mục tài liệu tham khảo, khóa luận bao gồm ba chương: Chương 1: Kiến thức mở đầu. Chương 2: Bài toán phủ hình. Chương 3: Bài toán bao hình. 4 Chương 1 Kiến thức cơ bản Trong phần này, ta chỉ giới hạn đi nghiên cứu đối tượng là các đa giác lồi, còn các trường hợp đa giác khác sẽ được tìm hiểu sau. 1.1. Một số khái niệm mở đầu Định nghĩa 1.1.1 [Tập lồi]. Tập X ⊂ Rn , X 6= 0/ gọi là tập lồi nếu với mọi x, y ∈ X và λ ∈ [0, 1] thì λ x + [1 − λ ]y ∈ X. [1.1] Ví dụ 1.1.1. Rn , {x} là các tập lồi. Định nghĩa 1.1.2 [Bao lồi]. Bao lồi của một tập X là giao của các tập lồi chứa X. KH: Conv X Định nghĩa 1.1.3 [Đa giác]. Là đường gấp khúc n cạnh trong mặt phẳng [n ≥ 3] A1 A2 . . . An sao cho đỉnh đầu và đỉnh cuối trùng nhau. Cạnh đầu A1 A2 và cạnh cuối An−1 An [cũng coi là hai cạnh liên tiếp] không nằm trên một đường thẳng.Đa giác như thế kí hiệu là A1 A2 . . . An . Đa giác n cạnh còn gọi là n - giác. Các điểm Ai gọi là các đỉnh của đa giác. Các đoạn thẳng Ai Ai+1 gọi là các cạnh của đa giác. Góc Ai−1 Ai Ai+1 gọi là góc đa giác ở đỉnh Ai . Định nghĩa 1.1.4 [Đa giác đơn]. Là đa giác mà bất kì hai cạnh không liên tiếp nào cũng không có điểm chung. Định nghĩa 1.1.5 [Đa giác lồi]. Là đa giác mà toàn bộ đa giác này nằm về một phía của đường thẳng chứa cạnh bất kỳ nào của đa giác đó. 5 Định nghĩa 1.1.6 [Đa giác đều]. Đa giác được gọi là đa giác đều nếu tất cả các cạnh của chúng bằng nhau và tất cả các góc của chúng bằng nhau. Khác với đa diện đều, đa giác đều có thể có số cạnh [góc] lớn vô cùng. Khi đó hình dáng đa giác đều tiến gần tới hình tròn. Định nghĩa 1.1.7 [Đường chéo của đa giác]. Một đoạn thẳng nối hai đỉnh không kề nhau của một đa giác gọi là đường chéo của đa giác đó. 1.2. Các tính chất Tính chất 1.2.1. Tổng các góc trong của một đa giác lồi n cạnh bằng [n − 2]180o . [1.2] Tính chất 1.2.2. Tổng số đo góc trong và góc ngoài tại một đỉnh của hình n - giác bằng 180o . Tính chất 1.2.3. Mọi góc trong một đa giác lồi không vượt quá 180o . Tính chất 1.2.4. Trong đa giác lồi, đoạn thẳng nối hai điểm bất kỳ nằm hoàn toàn trong đa giác. Tính chất 1.2.5. Số đo góc của đa giác n cạnh là [n − 2]180o . n [1.3] Định lý 1.1. Số đường chéo của đa giác n cạnh là n[n − 3] . 2 1.3. [1.4] Một số ví dụ Ví dụ 1.3.1. Tính số cạnh của một đa giác lồi, biết đa giác đó thỏa mãn các điều kiện sau: a] Tổng các góc trong bằng tổng các góc ngoài [tại mỗi đỉnh của đa giác chỉ kề một góc ngoài]; b] Số đường chéo gấp đôi số cạnh; c] Tổng các góc trong trừ đi một góc của đa giác bằng 2570o . 6 Giải Gọi số cạnh của đa giác là n [n ≥ 3, n ∈ N]. a] Khi đó, tổng số đo các góc trong của đa giác là [n − 2]180o ; Mà tổng số đo các góc ngoài của một đa giác là 360o nên theo giả thiết, ta được [n − 2]180o = 360o . Suy ra n = 4. Vậy số cạnh của đa giác đó là 4. b] Theo giả thiết số đường chéo gấp hai lần số cạnh nên ta có n[n − 3] = 2n ⇔ n2 − 7n = 0. 2 Suy ra n = 7. Vậy số cạnh của đa giác là 7. c] Tổng các góc trong của một đa giác bằng [n − 2]180o nên theo giả thiết ta có: b = 2570o [n − 2]180o − A Suy ra b = [n − 2]180o − 2570o . A [1.5] Vì mọi góc trong một đa giác lồi không vượt quá 180o nên 0o < [n − 2]180o − 2570o < 180o [1.6] ⇔ 16, 2 < n < 17, 2. Do n ∈ N, n > 3 nên suy ra n = 17. Vậy đa giác đó có 17 cạnh. Ví dụ 1.3.2. Chứng minh rằng trong một đa giác lồi bất kỳ không thể có quá 3 góc nhọn. 7 Giải Giả sử đa giác lồi có K góc nhọn [K ≥ 4]. Khi đó, nếu góc trong một đỉnh của đa giác lồi là góc nhọn thì góc ngoài tương ứng tại đỉnh đó là góc tù. Do vậy, nếu đa giác có K ≥ 4 góc nhọn thì sẽ có K ≥ 4 góc tù tương ứng và tổng các góc ngoài của chúng sẽ lớn hơn 360o . Điều này không xảy ra vì trong một đa giác bất kì tổng các góc ngoài chỉ bằng 360o . Vậy: Trong một đa giác lồi bất kì không thể có quá 3 góc nhọn. Ví dụ 1.3.3. Có tồn tại hay không đa giác có số cạnh bằng số đường chéo? Giải Gọi n là số cạnh của đa giác [n ≥ 3, n ∈ Z + ]. Đa giác có số cạnh bằng số đường chéo khi và chỉ khi n[n − 3] = n ⇔ n2 − 5n = 0. 2 Suy ra n = 5. Vậy đa giác duy nhất có số cạnh bằng số đường chéo là ngũ giác. Ví dụ 1.3.4. Tìm tất cả các hình chữ nhật sao cho có thể cắt hình chữ nhật đó thành 13 hình vuông bằng nhau. Giải Giả sử một cạnh của hình chữ nhật được chia thành m hình bằng nhau, cạnh kia được chia thành n hình bằng nhau [m, n ∈ N]. Ta có m.n = 13. Vì 13 là số nguyên tố nên một trong hai số m, n bằng 1, số còn lại bằng 13. Do đó, hình chữ nhật có cạnh 1 và 13 thoả mãn đề bài. 1.4. Bài tập đề nghị Bài tập 1.1. Chứng minh rằng bằng một đường chéo thích hợp, mọi n - giác đơn có thể phân hoạch thành hai đa giác có số cạnh nhỏ hơn n. 8 Bài tập 1.2. Chứng minh rằng ngũ giác có 5 cạnh bằng nhau và 3 góc liên tiếp bằng nhau là ngũ giác đều. Bài tập 1.3. Tổng tất cả các góc trong và một trong các góc ngoài của đa giác là 2225o . Hỏi đa giác có bao nhiêu cạnh? Bài tập 1.4. Tìm số cạnh của một đa giác biết các đường chéo của nó có độ dài bằng nhau. Bài tập 1.5. Cho ngũ giác lồi ABCDE có các cạnh bằng nhau và các góc trong đều nhỏ hơn 120o . Chứng minh rằng các góc trong của ngũ giác lồi đó đều là góc tù. Bài tập 1.6. Cho hình vuông ABCD, độ dài cạnh bằng 1 đơn vị. Gọi P, Q lần lượt nằm d bằng 45o . trên cạnh AB, AD. CMR chu vi tam giác APQ bằng 2 khi và chỉ khi góc CPQ Bài tập 1.7. Chứng minh rằng trong một tứ giác lồi có các góc không bằng nhau thì có ít nhất một góc là góc tù. Bài tập 1.8. a] Tìm số n sao cho trong mặt phẳng có thể phủ kín bởi đa giác đều có n cạnh. b] Có tồn tại các ngũ giác bằng nhau để phủ kín mặt phẳng hay không. Bài tập 1.9. Người ta đánh dấu mỗi đỉnh của đa giác đều 1995 cạnh bởi màu xanh hoặc đỏ. Chứng minh rằng luôn tìm được 3 đỉnh của đa giác là 3 đỉnh của một tam giác cân được đánh dấu cùng màu. Bài tập 1.10. Chứng minh rằng có vô số hình bình hành MNPQ nội tiếp một hình bình hành ABCD cho trước [mỗi đỉnh của hình bình hành MNPQ nằm trên mỗi cạnh của hình bình hành ABCD] và các hình bình hành này có chung tâm đối xứng. Bài tập 1.11. Cho lục giác đều có tất cả các góc trong bằng nhau. Chứng minh rằng hiệu giữa các cạnh đối diện thì bằng nhau. Bài tập 1.12. Một đa giác có hiệu giữa đường chéo lớn nhất và nhỏ nhất bằng cạnh của nó. Hỏi đa giác đó là đa giác gì ? 9 Chương 2 Bài toán phủ hình 2.1. Lát mặt phẳng bằng những đa giác bằng nhau Trong thực tế, ở bất cứ đâu, ta cũng gặp bài toán này như lát vỉa hè, sàn nhà, sân trường,... bằng những viên gạch đa giác giống nhau [hình chữ nhật, hình vuông, hình lục giác,...]. Mặt phẳng được lát bởi những đa giác giống nhau này sao cho hai đa giác tuỳ ý không có điểm chung, nhưng chúng có thể chung đỉnh và chung cạnh. Khi đó ta được "một phủ mặt phẳng" nếu mọi điểm trong mặt phẳng đều nằm trong một hình đa giác mà ta dùng để lát. Ví dụ 2.1.1. Xét những hình tam giác, tứ giác, ngũ giác,...giống nhau mà ta dùng để lát mặt phẳng. Để dễ thấy trực quan, ta coi các đa giác là những viên gạch và lát mặt phẳng bằng những viên gạch giống nhau. a] Ta có thể lát mặt phẳng bằng những viên gạch hình tam giác. Bằng cách ghép hai viên gạch hình tam giác này ta được viên gạch có dạng hình bình hành. Hiển nhiên ta cũng có thể phủ được mặt phẳng bằng những viên gạch này [xem hình H.2.1 và hình H.2.2]. b] Tương tự, mặt phẳng cũng có thể lát bằng những viên gạch hình tứ giác có dạng bất kỳ , ghép hai viên tứ giác lại tạo ra viên lục giác, trong đó những góc đối diện bằng nhau và các cạnh đối diện song song và bằng nhau. Ta cũng thấy mặt phẳng có thể lát bằng viên gạch hình này [xem hình H.2.3 và hình H.2.4] . c] Ta cũng có thể ghép mặt phẳng bằng những viên gạch lục giác sao cho mọi đỉnh của viên gạch sẽ là đỉnh của ba góc trong của viên gạch lục giác, mà tổng của chúng là 360o [xem hình H.2.5] . 10 H2.2 H.2.1 H.2.3 H.2.4 d] Giả sử ta dùng những viên gạch ngũ giác giống nhau để lát mặt phẳng +] Nếu những viên gạch ngũ giác là ngũ giác đều thì không thể phủ được mặt phẳng [vì n.180o > 360o với n = 3, 4, 5] . +] Nếu viên gạch ngũ giác là không đều thì có thể phủ được mặt phẳng bởi một loại ngũ giác như sau. Ta chia một lục giác đều thành ba ngũ giác bằng nhau bằng cách dựng ba đường trung trực của ba cạnh không kề nhau. Mặt phẳng có thể lát bằng những viên gạch lục giác và những viên gạch ngũ giác này thực sự lát được mặt phẳng [xem hình H.2.6]. Từ đó, ta thấy với n ≤ 6, mặt phẳng có thể phủ được bởi những viên gạch hình n - giác giống nhau. H.2.6 H.2.5 11 Ta xét định lí sau: Định lý 2.1. Với n ≥ 7 không tồn tại những viên gạch có dạng n - giác lồi giống nhau mà có thể lát được mặt phẳng. Chứng minh Giả sử tồn tại một phủ mặt phẳng bởi những viên gạch n - giác giống nhau với n ≥ 7. Kí hiệu S là diện tích của n - giác, d là đường kính của đường tròn chứa n - giác với giả thiết d và n - giác cố định. Xét ba đường tròn đồng tâm lần lượt có bán kính R, R − d và R + d sao cho R đủ lớn [R > d]. Kí hiệu NR là số lượng những n - giác nằm trong đường tròn bán kính R. Khi đó NR > [R − d]2 π. S [2.1] [R − d]2 π thì NR .S ≤ [R − d]2 π không xảy ra]. S Mặt khác, mọi điểm thuộc hình tròn có bán kính R − d sẽ nằm trong một đa giác nào đó ở trong đường tròn bán kính R, nên [Vì giả sử ngược lại nếu NR ≤ π[R − d]2 < NR .S . Tổng các góc trong của những đa giác là [n − 2]NR π. [2.2] Từ [2.1] và [2.2] ta có bất đẳng thức [n − 2][R − d]2 π 2 . [2.3] S Bây giờ, ta xét những n - giác giao với hình tròn bán kính R. Vì mọi đa giác có điểm chung với hình tròn bán kính R sẽ nằm trong hình tròn bán kính R + d nên số π[R + d]2 lượng của chúng MR sẽ nhỏ hơn . S Suy ra số lượng của những điểm mà chúng nằm trong hình tròn bán kính R sẽ nhỏ hơn nMR . 3 Lại thấy, tổng của những góc mà chúng có đỉnh chung là 2π nên sau khi lấy tổng ta được [n − 2]NR π > QR = 2nMR 2n[R + d]2 ≤ . 3 3S 12 [2.4] Từ [2.3] và [2.4] ta được bất đẳng thức 2n[R + d]2 π 2 [n − 2][R − d]2 π 2 ≥ . 3S S Hay là ⇔ 2n[R + d]2 ≥ 3[n − 2][R − d]2 . [2.5] Chia cả hai vế bất đẳng thức trên cho R2 , ta được d d d d 2n + 4n + 2n[ ]2 ≥ 3[n − 2] − 6[n − 2] + 3[n − 2][ ]2 . R R R R Khi cho R tăng vô hạn, ta có thể thay d bằng 0, và suy ra được R 2n ≥ 3[n − 2]. Bất đẳng thức này chỉ đúng với n ≤ 6. Vậy không thể có phủ mặt phẳng với n - giác giống nhau mà n ≥ 7. 2.2. Bài toán phủ hình 2.2.1. Bài toán phủ đa giác lồi a] Phủ đa giác lồi bằng những đa giác vị tự với chính nó Ta xét bài toán phủ một đa giác lồi bằng một số những đa giác khác mà chúng nhận được từ đa giác đã cho qua một phép vị tự với hệ số k < 1. Định nghĩa 2.2.1. Cho đa giác D và một họ đa giác Di [Di là các đa giác vị tự với đa giác D với tỉ số vị tự k ∈ [0, 1]]. Ta nói rằng một số đa giác Di tạo thành một phủ vị tự của đa giác D, nếu mọi điểm của đa giác đã cho thuộc ít nhất một trong những đa giác phủ. Để đơn giản, trong mục này ta nói một phủ thay cho một phủ vị tự nói trên. Ví dụ 2.2.1. Với tam giác ABC bất kì có tồn tại một phủ theo định nghĩa trên không? 13 C C1 A1 A A 2 D C2 C B1 H.2.7 B2 B B A H.2.8 Giải Trên mỗi cạnh của tam giác ABC ta dựng những đoạn thẳng A1 B1 //AB, A2C2 //AC, C1 B2 //CB [ A1 B1 , A2C2 , C1 B2 đủ gần các cạnh tương ứng AB, AC và BC] [xem hình H.2.7]. Khi đó các tam giác 4A1 B1C, 4A2 BC2 và 4AB2C1 là các tam giác vị tự với tam giác ABC và ba tam giác này phủ được tam giác ABC. Ta đi chứng minh rằng không thể phủ một tam giác bất kỳ bằng hai tam giác vị tự có hệ số vị tự nhỏ hơn 1. Thật vậy, giả sử có một tam giác MNP vị tự với tam giác ABC mà phủ được hai đỉnh A, B. Khi đó, mọi đoạn thẳng trong tam giác phủ MNP và song song với AB sẽ có độ dài nhỏ hơn thực sự độ dài AB [ vì hệ số vị tự k < 1]. Điều này vô lí và không thể có một phủ như vậy. Do đó, để có một phủ theo điều kiện đã cho cần phải có ít nhất ba tam giác vị tự. Bằng cách chứng minh tương tự, cần phải có ít nhất bốn hình bình hành vị tự với hình bình hành ABCD đã cho mới phủ được nó [xem hình H.2.8] . Ta có bổ đề sau: Bổ đề 2.1. Mọi đa giác lồi D có n cạnh khác hình bình hành đều tồn tại ba cạnh, mà kéo dài ba cạnh này tạo ra một tam giác chứa đa giác đã cho. Chứng minh Ta chứng minh bằng phương pháp quy nạp. +] Nếu n = 3, 4 thì đa giác lồi M đã cho là tam giác hoặc tứ giác thì khẳng định trên luôn đúng [xem hình H.2.9]. +] Giả sử bổ đề đúng với mọi đa giác lồi M khác hình bình hành có số cạnh nhỏ hơn n. Ta xét đa giác M có n cạnh [n ≥ 5] thì từ điều kiện M là đa giác lồi không phải là hình bình hành nên tồn tại ít nhất ba cạnh kề mà có hai cạnh kéo dài cắt nhau tạo thành một đa giác có số cạnh nhỏ hơn, kí hiệu Mn−1 . Khi đó theo giả thiết quy nạp : +] Nếu Mn−1 là một tam giác thì bổ đề được chứng minh. 14 J D F C E H.2.9 I A H.2.10 B +] Nếu Mn−1 là một hình bình hành ABCD, nhưng đa giác ban đầu M không phải hình bình hành, do đó tồn tại điểm nào đó trong các điểm A, B, C, D không phải là đỉnh của M. [ vì nếu A, B, C, D là các đỉnh của M thì đa giác M sẽ chứa ABCD. Nhưng theo cách dựng trên ABCD chứa M, do đó M là hình bình hành ABCD , mâu thuẫn với giả thiết]. Tiếp đó, ta giả sử D không thuộc M. Kí hiệu F là đỉnh thuộc M gần nhất với D. Xét đường thẳng đi qua F và một cạnh của M cắt hai cạnh AD, CD lần lượt ở E, F. Từ đa giác M là lồi nên M sẽ nằm hoàn toàn về một phía của EF và cả về một phía của cạnh AD [xem hình H.2.10] . Suy ra ba đường thẳng AB, BC và EF là ba đường đi qua ba cạnh của M mà tạo thành tam giác BIJ phải tìm. Định lý 2.2. [Gohberg - Markus] Cho M là đa giác lồi không phải là hình bình hành. Khi đó, số lượng nhỏ nhất những đa giác vị tự với M đủ để phủ M là 3. Chứng minh Áp dụng kết quả của bổ đề 2.1, ta sẽ chứng minh rằng mọi đa giác lồi khác hình bình hành có thể phủ được bởi ba đa giác vị tự. Thật vậy, cho ABC là tam giác chứa đa giác A1 A2 . . . An . Giả sử A1 A2 , Ak Ak+1 và A` A`+1 lần lượt nằm trên các cạnh AB, AB và BC. Lấy một điểm O bất kỳ nằm trong đa giác và nối O với ba điểm P, Q, R [P ∈ A1 A2 , Q ∈ Ak Ak+1 , R ∈ A` A`+1 ]. Các đoạn thẳng OP, OQ, OR chia đa giác M đã cho thành ba phần m1 , m2 , m3 . Xét phép vị tự tâm A hệ số k = 1 − δ [với δ > 0, δ đủ nhỏ]. 0 0 Khi đó, qua phép vị tự này, ảnh của A1 và Ak+1 tương ứng là A1 và Ak+1 sẽ nằm trong đoạn A1 P và Ak+1 Q. Hơn nữa, qua phép vị tự này ảnh của đường gấp khúc Ak+1 . . . A` A`+1 . . . A1 không có điểm chung với đường gấp khúc QOP. Do đó, ta nhận được một đa giác vị tự phủ m1 . Lập luận tương tự cho các phép vị tự có tâm tại B,C ta cũng nhận được các đa giác vị tự phủ m2 và m3 . 15 C A1 P A2 A`+1 R m3 m1 A` O m2 B A Ak Q Ak+1 H.2.11 Gọi các đa giác M1 , M2 là ảnh của M qua phép vị tự có tâm tương ứng O1 và O2 . Giả sử M phủ được bởi hai đa giác nói trên. Khi đó, ta dựng đường thẳng ` đi qua O1 và O2 và gọi F ∈ M là điểm sao cho khoảng cách từ F tới đường thẳng ` là lớn nhất . Khi đó, F không thể phủ bởi một trong hai đa giác M1 , M2 [mâu thuẫn với giả thiết hai đa giác phủ đa giác đã cho] [xem hình H.2.11]. Do vậy, M không thể phủ bằng hai đa giác vị tự với nó. Định lí được chứng minh. b] Phủ đa giác lồi bằng những đa giác đồng dạng với nó [với hệ số đồng dạng k 6= 1] Định nghĩa 2.2.2. [Phủ đa giác bằng những đa giác đồng dạng với nó] : Tương tự như định nghĩa phủ đa giác lồi bằng những đa giác vị tự với nó. Bổ đề 2.2. Mọi hình bình hành có thể phủ được bằng ba hình bình hành đồng dạng với nó. Chứng minh Xét hình bình hành ABCD. Gọi O, O1 lần lượt là trung điểm của AC và BC. Giả sử 0 đường chéo AC lớn hơn cạnh BC . Khi đó, trên cạnh BC ta dựng các đoạn thẳng O1 A 0 và O1C thoả mãn 0 0 AC [2.6] O1 A = O1C = k , k < 1 2 0 0 và dựng các đoạn thẳng O1 B và O1 D thoả mãn 0 0 O1 B = O1 D = k 0 0 0 BD \ 0 0 d , A O1 B = AOB. 2 0 [2.7] Ta thấy hình bình hành A B C D sẽ phủ cạnh BC và một hình bình hành nhỏ như 00 00 A BCD [H.2.12]. 00 00 Mặt khác, hình bình hành AA EF và GHD D vị tự với ABCD qua phép vị tự có tâm tương ứng tại A, D và hai hình bình hành này có thể phủ phần còn lại là hình bình 00 00 hành AA D D. 16 B0 C D F E O G A D 0 O1 H 0 C C C0 0 B A B00 B 0 H.2.12 C00 A B A0 H.2.13 Từ đó suy ra mọi hình bình hành có thể phủ được bằng ba hình bình hành đồng dạng với nó. Kết hợp kết quả của định lí 2.2 trên và bổ đề 2.3, ta có định lí sau Định lý 2.3. Mọi đa giác lồi có thể phủ được bằng ba đa giác đồng dạng với nó. Xét bài toán đơn giản nhất khi đa giác là tam giác ABC. +] Nếu ABC là tam giác đều thì không tồn tại một tam giác đều khác mà có thể phủ đồng thời hai đỉnh của tam giác ABC đồng thời thoả mãn cạnh của nó nhỏ hơn cạnh của tam giác ABC đã cho [ vì khoảng cách giữa hai điểm bất kỳ trong tam giác luôn nhỏ hơn một cạnh của tam giác]. Do đó, để phủ được tam giác ABC thì phải cần đến ba tam giác. +] Nếu ABC là tam giác không đều. Giả sử cạnh AB > BC [xem hình H.2.13]. 0 0 0 0 0 Ta dựng tam giác A B C đồng dạng với tam giác ABC thoả mãn BC nằm trên cạnh A B 0 0 0 0 0 và A B = kAB > BC, [k < 1]. Khi đó, tam giác A B C sẽ phủ một tứ giác nhỏ nào đó, 00 0 ví dụ như B BCC . 00 00 Mặt khác, tam giác AB C vị tự với tam giác ABC qua phép vị tự tâm A và tam giác này có thể phủ được phần còn lại của tam giác ABC. Do đó, có thể phủ tam giác ABC bằng hai tam giác đồng dạng. 2.2.2. Bài toán phủ một đoạn thẳng Cho ε là một số. Ta xét một đoạn thẳng A có độ dài bằng 1 được phủ bởi một số đoạn thẳng khác. Bài toán đặt ra : Từ một phủ bất kỳ của đoạn thẳng đơn vị, có tồn tại hay không một số đoạn thẳng [trong những đoạn thẳng phủ] mà mọi cặp đoạn thẳng của chúng đều không có điểm chung nhưng tổng độ dài của chúng nhỏ hơn ε > 0 hoặc lớn hơn ε > 0. 1 Để ý rằng εo = giữ vai trò quan trọng như một số kết quả trong định lí sau : 2 17 Định lý 2.4. Cho tập hợp M những đoạn thẳng phủ đoạn thẳng AB với độ dài bằng 1. a] Tồn tại một tập hợp con σ ⊂ M gồm những đoạn thẳng không giao nhau mà tổng 1 của chúng không nhỏ hơn . 2 1 b] Nếu ε > thì luôn tồn tại tập hợp M chứa những đoạn thẳng có tính chất sau: Tổng 2 những độ dài của những đoạn thẳng không giao nhau thuộc M nhỏ hơn ε. Chứng minh Ta có nhận xét sau: Cho tập M những đoạn thẳng phủ đoạn thẳng AB. Nếu một đoạn thẳng bị phủ toàn bộ bởi một hoặc vài đoạn thẳng, thì ta bỏ đoạn thẳng này đi và những đoạn thẳng còn lại vẫn phủ AB. a] Xét tất cả những đoạn thẳng phủ điểm A. Trong những đoạn thẳng vừa chọn, ta chọn đoạn thẳng có điểm đầu bên phải nằm về phía bên phải nhất trên đoạn thẳng AB. +] Nếu ta bỏ đi tất cả những đoạn khác phủ A ngoài đoạn thẳng ta vừa chọn ở trên, thì ta vẫn còn một phủ đoạn AB, gọi là đoạn thẳng thứ nhất. Tiếp đó, ta xét tất cả những đoạn thẳng phủ điểm cuối bên phải B1 của đoạn thẳng thứ nhất A1 B1 . Xét hai đoạn thẳng CD và EF . +] Nếu điểm F nằm ở bên phải của D, thì đoạn thẳng A1 B1 và EF sẽ phủ đoạn CD và ta có thể bỏ đi CD [xem hình H.2.14]. +] Nếu điểm F nằm ở bên trái điểm D thì lập luận tương tự, ta có thể bỏ đoạn EF [xem hình H.2.15]. Tiếp tục quá trình này, ta tách được một đoạn thẳng A2 B2 phủ B1 gọi là đoạn thẳng thứ hai. Xét tất cả các đoạn thẳng phủ B2 và cũng tách được một đoạn thẳng và gọi đó là đoạn thẳng thứ ba,.... Sau khi đánh số như trên thì ta nhận được mọi cặp đoạn thẳng có số thứ tự đồng thời chẵn hoặc lẻ sẽ không có điểm chung [vì giả sử đoạn thứ nhất và đoạn thứ ba có điểm chung, thì đoạn thứ hai và đoạn thứ ba phủ B1 mà theo cách dựng, tổng các độ dài của những đoạn thẳng phủ AB không nhỏ hơn 1. Do đó, điều giả sử sai]. Vậy tổng 1 các độ dài của các đoạn thẳng có số thứ tự chẵn hoặc lẻ không nhỏ hơn . 2 1 b] Cho ε là một số, ε > . 2 Xét hai đoạn thẳng A1 B1 và A2 B2 giao nhau và phủ AB . 1 1 Nếu chúng có độ dài bằng nhau A1 B1 = A2 B2 = + δ > < ε thì chúng sẽ tạo ra tập 2 2 M cần tìm. 18 A A1 C E B1 D F B A1 H.2.14 2.2.3. A C E B1 F D B H.2.15 Bài toán phủ một hình vuông Rado [1906 − 1989] là nhà toán học người Hungari. Ông là người đầu tiên nghiên cứu về bài toán liên quan đến phủ một hình vuông. Bài toán này cũng được lấy tên ông là bài toán Rado. Bài toán Rado liên quan đến việc tìm số εo thoả mãn tính chất sau: a] Cho hình vuông có cạnh bằng 1 được phủ bởi tập hợp những hình vuông con. Từ mỗi tập hợp hình vuông con này, có thể chọn ra được những hình vuông không giao nhau thoả mãn tổng diện tích của chúng lớn hơn ε [ với mọi 0 < ε < εo ]. b] Cho hình vuông có cạnh bằng 1, tồn tại một tập hợp hình vuông phủ hình vuông đã cho thoả mãn tổng diện tích của những hình vuông tuỳ ý không giao nhau nhỏ hơn ε [ với mọi ε > εo ]. Để dễ tưởng tượng, ta coi hình vuông là cái mặt bàn hình vuông có cạnh bằng 1 đơn vị, ta muốn phủ mặt bàn hình vuông này bằng những khăn trải bàn hình vuông. Cụ thể ta xét định lí sau: Định lý 2.5. Cho một mặt bàn hình vuông có cạnh bằng 1, được phủ bởi những khăn trải bàn hình vuông. Khi đó, tồn tại một tập hợp con những khăn trải bàn không giao 1 nhau sao cho tổng diện tích của chúng không nhỏ hơn . 9 Chứng minh a] Theo giả thiết, từ tập hợp những khăn trải bàn phủ mặt bàn hình vuông có cạnh bằng 1 là hữu hạn nên ta chọn ra được một chiếc khăn có cạnh lớn nhất, chẳng hạn a1 và ta kí hiệu là K1 . Sau đó xét tất cả những khăn trải bàn còn lại có giao với K1 và những khăn này đều phải nằm trong hình vuông có cạnh 3a1 mà nó chứa K1 [xem hình H.2.16]. Phần mặt bàn chưa được phủ bởi K1 , nhưng được phủ bởi những khăn giao với K1 có diện tích không vượt quá diện tích của 8 hình vuông có cạnh a1 , tức là diện tích phần phủ này không lớn hơn 8a21 . Ta bỏ đi những khăn có giao với K1 và xét những khăn còn lại trừ K1 . Từ trong tập này, ta lại chọn ra một khăn có cạnh lớn nhất a2 và kí hiệu nó là K2 . Ta bỏ đi những khăn có giao với K2 và diện tích của phần bỏ đi này không nhỏ hơn 8a22 . Bằng cách lập luận tương tự, ta sẽ nhận được một tập hợp những khăn không giao nhau K1 , K2 , . . . , K p và tổng diện tích của những khăn này bằng a21 + a22 + . . . + a2p . Mà theo lập luận ở trên ta có: 1 1 − [a21 + a22 + . . . + a2p ] ≤ 8[a21 + a22 + . . . + a2p ] ⇔ a21 + a22 + . . . + a2p ≥ . 9 19