Luận văn Thạc sĩ Khoa học: Về lục giác lồi rỗng

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

Thêm vào BST

Báo xấu

24
lượt xem 4
download

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

Năm 1935, Erdos và Szekeres đã đưa ra giả thuyết sau đây (giả thuyết Erdos-Szekeres): Mọi tập không ít hơn 2 n−2 + 1 điểm trên mặt phẳng ở vị trí tổng quát (không có ba điểm nào thẳng hàng) đều chứa n điểm là đỉnh của một đa giác lồi. Giả thuyết Erdos-Szekeres có ý nghĩa triết học sâu sắc: Từ một tập hợp hỗn độn, không có trật tự, đủ lớn (tập các điểm bất kì trên mặt phẳng), ta có thể tìm được một tập con có cấu trúc đẹp (đa giác lồi). Mời các bạn cùng tìm hiểu.

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ĩ Khoa học: Về lục giác lồi rỗng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ NGUYỄN GIANG THÀNH VỀ LỤC GIÁC LỒI RỖNG LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 01 13 Người hướng dẫn khoa học PGS. TS. TẠ DUY PHƯỢNG HÀ NỘI- 2013
Mục lục Mở đầu 3 1 TỔNG QUAN VỀ BÀI TOÁN ERDOS ¨ VỀ ĐA GIÁC LỒI RỖNG 5 1.1 Bài toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Bài toán 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Bài toán 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Bài toán 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.4 Bài toán 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.5 Bài toán 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Bài toán 3 (Bài toán về tồn tại đa giác chứa k điểm trong ) . . . . . 19 1.4 Bài toán 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ 23 2.1 Định lý E(6) ≤ ES(9) . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Lược đồ chứng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.1 Kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Các định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Các trường hợp đơn giản . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Các trường hợp (3, ≥ 0) và (≥ 6, 3) . . . . . . . . . . . . . . . . . . . . 27 2.4.1 Các trường hợp (3, ≥ 0) và (8,3) . . . . . . . . . . . . . . . . . 27 2.4.2 Các trường hợp (6,3) và (7,3) . . . . . . . . . . . . . . . . . . 29 2.5 Các trường hợp (4, ≥ 0) và (≥ 7, 4) . . . . . . . . . . . . . . . . . . . . 34 2.5.1 Bước 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.2 Bước 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.3 Bước 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.4 Bước 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.5 Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 Các trường hợp (5, 0) và (≥ 7, 5, 0) . . . . . . . . . . . . . . . . . . . . 40 2.6.1 Các trường hợp (5, 0) và (8, 5, 0) . . . . . . . . . . . . . . . . . 40 2.6.2 Trường hợp (7, 5, 0) . . . . . . . . . . . . . . . . . . . . . . . . 40 2.7 Các trường hợp riêng . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.7.1 Trường hợp (5,1) . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.7.2 Trường hợp (6,1) . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.7.3 Các trường hợp (6,2) và (7,1) . . . . . . . . . . . . . . . . . . 43 2.8 Các trường hợp (5, ≥ 2) . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1
2.8.1 Một quan sát cơ bản . . . . . . . . . . . . . . . . . . . . . . . 43 2.8.2 Các trường hợp (5, ≥ 2) . . . . . . . . . . . . . . . . . . . . . . 46 2.9 Các trường hợp (6, ≥ 4) . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.9.1 TW X ∩ TXY 6= ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.9.2 TW X ∩ TXY = ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.10 Các trường hợp (≥ 7, ≥ 5, ≥ 1) . . . . . . . . . . . . . . . . . . . . . . 52 2.10.1 Quy tắc 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.10.2 Quy tắc 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.10.3 Ứng dụng của Quy tắc 1 và 2 . . . . . . . . . . . . . . . . . . 54 2.10.4 Quy tắc 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.10.5 Ứng dụng các Quy tắc 1-3 . . . . . . . . . . . . . . . . . . . 58 2.10.6 Trường hợp (1, 1, 1, 1, 1, 1, 1) . . . . . . . . . . . . . . . . . . 59 2.10.7 Trường hợp (1, 1, 1, 1, 1, 1, 1, 0) . . . . . . . . . . . . . . . . . 59 2.10.8 Trường hợp (1, 1, 1, 1, 1, 1, 1, 1) . . . . . . . . . . . . . . . . . . 61 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2
Mở đầu Năm 1935, Erdo˝s và Szekeres đã đưa ra giả thuyết sau đây (giả thuyết Erdo˝s- Szekeres): Mọi tập không ít hơn 2n−2 + 1 điểm trên mặt phẳng ở vị trí tổng quát (không có ba điểm nào thẳng hàng) đều chứa n điểm là đỉnh của một đa giác lồi. Giả thuyết Erdo˝s-Szekeres có ý nghĩa triết học sâu sắc: Từ một tập hợp hỗn độn, không có trật tự, đủ lớn (tập các điểm bất kì trên mặt phẳng), ta có thể tìm được một tập con có cấu trúc đẹp (đa giác lồi). Kí hiệu ES(n) là số điểm ở vị trí tổng quát nhỏ nhất mà từ đó ta có thể chọn ra n điểm là đỉnh của n-giác lồi. Khi ấy, giả thuyết Erdo ˝s-Szekeres nói rằng ES (n) = 2n−2 + 1. Bất chấp sự cố gắng của hàng trăm nhà toán học đã viết hàng trăm bài báo, giả thuyết Erdo˝s-Szekeres mới chỉ được chứng minh cho các trường hợp n = 3, 4, 5, 6. Trường hợp n = 6 mới được chứng minh gần đây (2006) bởi Szekeres và Peters nhờ máy tính. Trên con đường chứng minh giả thuyết Erdo˝s-Szekeres, nhiều phương pháp và bài toán mới đã xuất hiện. Năm 1978 [xem 5], Erdo˝s đã phát biểu một bài toán mới, đó là Bài toán Erdo˝s về đa giác lồi rỗng: Cho n là một số tự nhiên bất kì. Tồn tại hay không số nguyên dương nhỏ nhất E(n) sao cho từ mọi tập chứa tối thiểu E(n) điểm ở vị trí tổng quát trên mặt phẳng, đều có thể chọn ra được n điểm là đỉnh của một đa giác lồi rỗng (đa giác không chứa điểm nào của tập đã cho bên trong nó). Bài toán này đã thu hút nhiều nhà nghiên cứu hình học tổ hợp trên thế giới. Năm 1978, Harborth đã chứng minh E(5) = 10. Năm 1983, với mọi n, Horton đã xây dựng tập (sau này được gọi là tập Horton), mà từ đó không thể lấy ra được đa giác lồi rỗng bảy đỉnh. Như vậy, chỉ còn phải nghiên cứu với trường hợp n = 6. Năm 2003, Overmars đã chứng minh, nếu E(6) tồn tại thì E(6) ≥ 30. Năm 2008, Gerken đã chứng minh E(6) ≤ ES(9) và từ đó suy ra ES(6) tồn tại và ta có đánh giá 30 ≤ E(6) ≤ 1717. Nhiều người tin rằng, E(6) = 30. Tuy nhiên, giả thuyết này cho đến nay vẫn chưa được chứng minh. Luận văn Về lục giác lồi rỗng có mục đích trình bày tổng quan về bài toán Erdo˝s- 3
Szekeres và bài toán Erdo˝s đồng thời trình bày chứng minh chi tiết bài báo của Gerken về đánh giá E(6) ≤ ES(9). Luận văn gồm hai Chương: Chương 1 trình bày tổng quan về giả thuyết Erdo˝s-Szekeres. Chương 2 trình bày cách chứng minh E(6) ≤ ES(9) của Gerken (năm 2008). Luận văn được hoàn thành tại trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội dưới sự hướng dẫn của PGS. TS. Tạ Duy Phượng- Viện Toán học. Tôi xin bày tỏ lòng biết ơn sâu sắc tới Thầy hướng dẫn. Tôi xin được cảm ơn Khoa sau đại học, các Thày Cô trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội và Viện Toán học đã nhiệt tình truyền thụ kiến thức và tạo điều kiện giúp đỡ tôi hoàn thành khóa Cao học. Và cuối cùng, xin cảm ơn Gia đình đã động viên và khích lệ tôi rất nhiều trong thời gian nghiên cứu và học tập. 4
Chương 1 TỔNG QUAN VỀ BÀI TOÁN ¨ VỀ ĐA GIÁC LỒI RỖNG ERDOS 1.1 Bài toán 1 Với mỗi số tự nhiên n ≥ 3 , hãy xác định số nguyên dương nhỏ nhất ES(n) sao cho mọi tập tạo thành từ tối thiểu ES(n) điểm trên mặt phẳng ở vị trí tổng quát phải chứa n điểm là đỉnh của một đa giác lồi. Bài toán 1 được phát biểu vào năm 1935 và sau này được gọi là Bài toán Erd¨os- Szekeres. Erd¨os đã gọi bài toán này là bài toán có kết hạnh phúc (happy end problem hay happy ending problem), vì không lâu sau khi bài báo được in ra (1935), Gy¨orgy Szekeres và Esther Klein đã tổ chức đám cưới (1937) và sống hạnh phúc bên nhau 60 năm. Bài toán 1 đã được tách ra thành hai bài toán: 1.1.1 Bài toán 1a Tồn tại hay không tồn tại số ES(n)? 1.1.2 Bài toán 1b Nếu số ES(n) tồn tại thì xác định ES(n) như một hàm của n. Sự tồn tại số ES(n) có thể được chứng minh bằng hai cách. Cách thứ nhất do Szekeres chứng minh không lâu sau khi E. Klein phát biểu bài toán, dựa trên định lí Ramsey (mà Ông đã tự tìm lại do không biết định lí này). Từ đó ta có bất đẳng thức ES(n) ≤ R4 (n, 5) , trong đó R4 (n, 5) là số Ramsey. Tuy nhiên, đánh giá này là quá lớn so với thực tế. Thí dụ, với n = 5 thì ES(5) ≤ 210000 quá xa so với ES(5) = 9. Cách thứ hai do Erd¨os chứng minh dựa trên một số quan sát hình học và kết 2n−4 quả ta được một đánh giá tốt hơn ES(n) ≤ Cn−2 + 1. Như vậy, bài toán 1a đã được trả lời khẳng định. 5
Rõ ràng ba điểm không thẳng hàng là đủ để tạo ra một tam giác nên ES(3) = 3. Dưới đây ta xét một số trường hợp cụ thể của bài toán với n = 4, 5, 6. 1.1.3 Bài toán 1.1 (E. Klein) Từ năm điểm bất kỳ trên mặt phẳng ở vị trí tổng quát bao giờ cũng chọn được bốn điểm là đỉnh của một tứ giác lồi. Đây cũng kết quả cho bài toán 1 trong trường hợp n = 4. Bài toán đã được E.Klein chứng minh vào năm 1932. Chứng minh Trước tiên ta nhận thấy, tồn tại bốn điểm không tạo thành một tứ giác lồi (Hình 1.1). Hình 1.1 Vậy số điểm mà từ đó có thể tạo thành tứ giác lồi phải không ít hơn 5. Xét bao lồi của năm điểm (tập lồi nhỏ nhất chứa năm điểm đã cho) ở vị trí tổng quát. Chỉ có ba khả năng khác nhau sau đây. • Khả năng 1 (Hình 1.2): Hình 1.2 Bao lồi của năm điểm là một ngũ giác ABCDE. Khi ấy mọi bộ bốn điểm từ năm điểm ấy đều tạo thành tứ giác lồi (và điểm còn lại nằm ngoài tứ giác lồi đó). Trong 6
trường hợp này ta có tất cả C54 = 5 tứ giác lồi. Đó chính là các tứ giác ABCD, ABCE, ABDE, ACDE, BCDE. Tất cả các tứ giác này đều không chứa điểm còn lại (điểm thứ năm nằm bên ngoài tứ giác). Ta gọi các tứ giác lồi này là tứ giác lồi rỗng. Ngoài ra, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E (ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE). Và tất cả các tam giác này đều là các tam giác rỗng. • Khả năng 2 (Hình 1.3): Hình 1.3 Bao lồi là một tứ giác chứa một điểm còn lại ở bên trong. Trong trường hợp này ta có một tứ giác lồi (kí hiệu là ABCD) chứa một điểm E ở bên trong. Tứ giác ABCD (chỉ chứa đúng một điểm E ở bên trong) được gọi là tứ giác gần rỗng. Vì không có ba điểm nào thẳng hàng nên E phải nằm về cùng phía với B (hoặc với D) của đường thẳng AC. Do đó ta có tứ giác AECD (hoặc ABCE) là tứ giác lồi rỗng, còn tứ giác ABCE (hoặc tương ứng AECD) là tứ giác lõm. Tương tự, điểm E phải nằm cùng phía với A (hoặc với C) của đường chéo BD. Khi ấy tứ giác BEDC (hoặc tứ giác ABED) là tứ giác lồi rỗng và tứ giác ABED (hoặc tứ giác BCDE) là tứ giác lõm. Như vậy, trong Trường hợp 2 ta có hai tứ giác lồi rỗng, một tứ giác lồi gần rỗng và hai tứ giác lõm. Ngoài ra, trong trường hợp này, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E. Đó là các tam giác: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Trong đó tất cả 6 tam giác có đỉnh E đều là tam giác rỗng (không chứa hai điểm còn lại bên trong). Vì khi kẻ đường chéo AC (hoặc BD) của tứ giác lồi ABCD thì do các điểm không thẳng hàng nên E phải nằm trong một trong hai tam giác ABC hoặc ACD (ABD hoặc BCD). Như vậy ta có hai tam giác gần rỗng (chứa điểm E) và thêm hai tam giác rỗng nữa. • Khả năng 3 (Hình 1.4): 7
Hình 1.4 Bao lồi chứa ba điểm tạo thành tam giác, thí dụ, ABC. Hai điểm còn lại E và D nằm bên trong tam giác. Do không có ba điểm nào thẳng hàng (các điểm ở vị trí tổng quát) nên hai điểm E và D xác định một đường thẳng chia mặt phẳng tam giác ABC thành hai phần sao cho có hai đỉnh của tam giác ABC, thí dụ, A và B, nằm trên cùng một nửa mặt phẳng mở. Hai điểm E và D cùng với A và B tạo thành một tứ giác lồi rỗng ABDE. Tứ giác này là tứ giác lồi duy nhất. Bốn tứ giác ABDC, ABEC, BDCE, ADCE còn lại là các tứ giác lõm. Ngoài ra, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E. Đó là các tam giác: ABC (chứa hai điểm bên trong), ACD và BEC chứa một điểm bên trong (tam giác gần rỗng). Bảy tam giác còn lại ABD, ABE, ACE, ADE, BCD, BDE, CDE là các tam giác rỗng. 1.1.4 Bài toán 1.2 Với chín điểm cho trước ở vị trí tổng quát (không có ba điểm nào thẳng hàng) bao giờ ta cũng tìm được năm điểm tạo thành một ngũ giác lồi. Theo Erdo˝s và Szekeres, công thức ES(5) = 9 đã được Endre Makai chứng minh. Hình 1.5 Tuy nhiên không có bài viết nào của E. Makai trình bày chứng minh đó, mà chỉ có phản ví dụ của E. Makai (Hình 1.5, xem [6]) chỉ ra rằng tồn tại tám điểm mà 8
không có năm điểm nào trong số đó tạo thành ngũ giác lồi, tức là ES(5) ≥ 9 (xem [6]). Bài toán 1.2 đã được Hoàng Chúng giới thiệu với bạn đọc Việt Nam trong Toán học và Tuổi trẻ số 4, tháng 2 năm 1967. Ngay sau đó công thức ES(5) = 9 đã được Đoàn Hữu Dũng chứng minh trong Toán học và Tuổi trẻ số 6 tháng 6, 1967. Hoàn toàn độc lập (nhưng cùng phương pháp) với Đoàn Hữu Dũng, công thức này cũng được chứng minh bởi Bonnice năm 1974. Dưới đây chúng tôi trình bày chứng minh chi tiết công thức ES(5) = 9, kết hợp cả phương pháp hình học, (xem [1]) của Đoàn Hữu Dũng (sử dụng các đa giác lồi bao nhau) và ngôn ngữ cấu hình của Bonnice (xem [3]). Chứng minh (Đoàn Hữu Dũng, 1967; Bonnice, 1974) Lấy bao lồi của 9 điểm bất kỳ. Gọi mỗi trường hợp (khả năng) có thể xảy ra là một cấu hình. Để phân loại các cấu hình, ta xét các đa giác lồi bao nhau, tức là đầu tiên lấy bao lồi của 9 điểm, bao lồi chỉ có thể là đa giác 9; 8; 7; 6; 5; 4; 3 đỉnh. Các điểm còn lại bên trong bao lồi tương ứng sẽ là 0; 1; 2; 3; 4; 5; 6. Khi số điểm còn lại bên trong bao lồi lớn hơn 3, ta lại lấy bao lồi của các điểm này để được các đa giác lồi. Chỉ có duy nhất một trường hợp ba tam giác bao nhau. Các trường hợp còn lại chỉ có thể là hai hoặc một đa giác bao nhau (có thể chứa một hoặc hai điểm trong). Ta được tất cả 12 cấu hình khác nhau sau đây: Trường hợp 1 (Hình 1.6a) Cấu hình (9;0): Bao lồi là đa giác lồi 9 đỉnh. Mọi tập năm đỉnh đều tạo thành ngũ giác lồi (thậm chí lồi rỗng). Trường hợp 2 (Hình 1.6b) Cấu hình (8;1): Bao lồi là đa giác lồi 8 đỉnh, một điểm còn lại nằm trong đa giác. Do không có ba điểm nào thẳng hàng nên năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng hoặc chứa một điểm trong). Trường hợp 3 (Hình 1.6c) Cấu hình (7;2): Bao lồi là đa giác lồi 7 đỉnh, hai điểm còn lại nằm trong đa giác. Do không có ba điểm nào thẳng hàng nên năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng, chứa một hoặc hai điểm trong). 9
Hình 1.6 Các cấu hình (9,0), (8,1), (7,2) Trường hợp 4 (Hình 1.7a) Cấu hình (6;3): Bao lồi là đa giác lồi 6 đỉnh, ba điểm còn lại tạo thành tam giác nằm trong bao lồi. Năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng, chứa một, hai điểm hoặc ba điểm trong). Trường hợp 5 (Hình 1.7b) Cấu hình (5;4) hoặc (5;3;1): Bao lồi là ngũ giác lồi, bốn điểm còn lại nằm trong đa giác. Ta có sẵn ngũ giác lồi chứa 4 điểm trong. Trường hợp 6 (Hình 1.7c) Cấu hình (4;5): Bao lồi là tứ giác lồi, năm điểm còn lại tạo thành đa giác lồi. Ta có sẵn ngũ giác lồi rỗng (nằm trong tứ giác). Hình 1.7 Các cấu hình (6,3), (5,4), (4,5) Hình 1.8 Các cấu hình (3,6), (3,5,1) 10
Trường hợp 7 (Hình 1.8a) Cấu hình (3;6): Mọi bộ 5 trong 6 đỉnh của lục giác lồi tạo thành các ngũ giác lồi nằm trong tam giác bao lồi ngoài. Trường hợp 8 (Hình 1.8c) Cấu hình (3;5;1): Ngũ giác lồi (chứa một điểm trong và nằm trong tam giác bao lồi ngoài) đã có sẵn. Nhận xét 1 Như vậy, ta còn lại bốn cấu hình (4, 4, 1), (4, 3, 2), (3, 4, 2) và (3, 3, 3) chưa xét. Hình 1.9 Các cấu hình (4,4,1), (4,3,2) Hình 1.10 Các cấu hình (3,4,2), (3,3,3) Cấu hình (3, 3, 3) trở về cấu hình (3, 3, 2) nếu bỏ đi một đỉnh của tam giác trong cùng. Cấu hình (4, 3, 2) trở về cấu hình (4, 3, 1) nếu bỏ đi một trong hai điểm trong. Cấu hình (4, 4, 1) trở về cấu hình (4, 3, 1) nếu bỏ đi một đỉnh của tứ giác trong sao cho ba đỉnh còn lại vẫn chứa một điểm trong. Vậy ta chỉ còn phải chứng minh các cấu hình (3, 3, 2), (3, 4, 2) và (4, 3, 1) chứa ngũ giác lồi. Bổ đề 1.1 Mọi tập Ω gồm tám điểm trên mặt phẳng ở vị trí tổng quát có cấu hình (4,3,1) chứa ngũ giác lồi. Chứng minh Bao lồi conv(Ω) của Ω (là tứ giác lồi ngoài cùng) chứa tam giác ABC . 11
Tam giác ABC lại chứa điểm P bên trong. Kẻ các nửa đường thẳng P A, P B, P C . Các nửa đường thẳng này chia mặt phẳng thành ba miền lồi đóng: miền (I) giới hạn bởi hai tia PA và PB; miền (II) giới hạn bởi hai tia PB và PC; miền (III) giới hạn bởi hai tia PC và PA (Hình 1.11). Hình 1.11 Cấu hình (4,3,1) Vì đa giác ngoài là tứ giác gồm bốn đỉnh nên theo nguyên lí Dirichlet, tồn tại ít nhất một trong ba miền mở (I), (II) hoặc (III) chứa hai đỉnh, thí dụ miền (I) giới hạn bởi hai tia PA và PB chứa hai điểm R và Q. Khi ấy A, B, P cùng với R và Q tạo thành ngũ giác lồi. Bổ đề 1.2 Mọi tập Ω gồm tám điểm trên mặt phẳng ở vị trí tổng quát có cấu hình (3, 3, 2) đều chứa ngũ giác lồi. Chứng minh Bao lồi convΩ của Ω là tam giác MNP chứa tam giác ABC, E và F là hai điểm nằm trong tam giác ABC. Các nửa đường thẳng FA, FB, EA, EC chia mặt phẳng thành ba miền: miền (I) giới hạn bởi hai tia EA, EC; miền (II) giới hạn bởi hai tia FA, FB; miền (III) giới hạn bởi tia FB, đoạn FE và tia EC. Hình 1.12 Cấu hình (3,3,2) Nếu convΩ (tam giác MNP) có một đỉnh, thí dụ M, nằm trong miền (III) thì nó tạo với các điểm B, F, E, C một ngũ giác lồi. Nếu cả ba đỉnh của tam giác MNP không nằm trong miền (III) thì MNP phải có ít nhất hai đỉnh nằm trong miền (I) 12
hoặc miền (II) (Hình 1.12). Tức là tồn tại ít nhất một miền (I) hoặc (II) chứa hai đỉnh của tam giác bao ngoài MNP. Hai đỉnh này tạo với ba điểm A, F, B (hoặc A, E, C) một ngũ giác lồi. Bổ đề 1.3 Mọi tập Ω gồm chín điểm trên mặt phẳng ở vị trí tổng quát có cấu hình (3,4,2) đều chứa ngũ giác lồi. Chứng minh Bao lồi convΩ của Ω là tam giác MNP bao tứ giác ABCD chứa hai điểm E, F bên trong. Các nửa đường thẳng FA, FB, EC, ED chia mặt phẳng thành bốn miền lồi đóng. Nếu có một đỉnh (thí dụ, N) của MNP nằm trong miền (I) giới hạn bởi đoạn thẳng FE và hai tia FA, EC (hoặc nằm trong miền (II) giới hạn bởi đoạn thẳng FE và hai tia FB, ED) thì N cùng với A, F, E, C (hoặc B, F, B, D) tạo thành một ngũ giác lồi (Hình 1.13). Hình 1.13 Cấu hình (3,4,2) Nếu không có đỉnh nào của tam giác MNP nằm trong miền (I) hoặc miền (II) thì ít nhất một trong hai miền (III) (giới hạn bởi hai tia FA và FB) hoặc (IV) (giới hạn bởi hai tia EC và ED) phải chứa hai đỉnh của tam giác MNP. Thí dụ, Q và R nằm trong miền (III). Khi ấy A, F, B và Q, R tạo thành một ngũ giác lồi (Hình 1.13). Vì các cấu hình (4, 4, 1), (4, 3, 2), (3, 4, 2) và (3, 3, 3) qui được về các trường hợp cấu hình (4, 3, 1), (3, 4, 2) và (3, 3, 2) nên ta đã xét tất cả các trường hợp có thể xảy ra với chín điểm. Do đó ta có kết luận: Từ chín điểm bất kì trên mặt phẳng ở vị trí tổng quát luôn có thể chọn ra năm điểm tạo thành ngũ giác lồi. Nhận xét 1.2 Có thể xảy ra trường hợp tứ giác ABCD chứa hai điểm E, F bên trong không có tam giác nào của tứ giác ABCD chứa cả hai điểm E và F bên trong (khi đoạn EF cắt cả hai đường chéo sao cho hai điểm E và F nằm ở hai phía của mỗi đường chéo, Hình 1.13) nên cấu hình (3, 4, 2) nói chung không đưa được về cấu hình (3, 3, 2). 13
Lời bình Khái niệm đa giác lồi bao nhau lần đầu tiên được Đoàn Hữu Dũng đưa ra và khái niệm cấu hình do Bonnice sử dụng là hai khái niệm cơ bản và được rất nhiều tác giả (T. Gerken, V. Koselev,...) sau này sử dụng, mặc dù bài báo của Đoàn Hữu Dũng trong Toán học và Tuổi trẻ không được các tác giả nước ngoài biết đến. 1.1.5 Bài toán 1.3 Mọi tập ít nhất 17 điểm ở vị trí tổng quát trên mặt phẳng đều chứa sáu điểm là đỉnh của lục giác lồi. Nói cách khác, ta phải chứng minh công thức ES(6) = 26−2 + 1 = 17. Bài toán 1.3 là trường hợp riêng của Bài toán 1 khi n = 6. Tuy nhiên, trường hợp cụ thể này của Bài toán Erd¨os–Szekeres cũng đã thách thức các nhà toán học trong 70 năm. Nó chỉ vừa mới được G. Szekeres và L. Peters chứng minh năm 2006 bằng máy tính (với 300 giờ chạy máy, xem [15]). Nó cũng được ba tác giả Dehnhardt, Harborth, và Lángi chứng minh không sử dụng máy tính năm 2009 (xem [4]), nhưng chỉ trong trường hợp khi đa giác bao ngoài cũng là ngũ giác lồi. Trường hợp khi đa giác bao ngoài là tứ giác lồi hoặc tam giác vẫn chưa được chứng minh. Dựa trên các đẳng thức ES(3) = 3 , ES(4) = 5 và ES(5) = 9, Erdo˝s và Szekeres đưa ra giả thuyết sau đây. Giả thuyết (Erd¨os–Szekeres, 1935) Với mỗi số tự nhiên n ≥ 3 , mọi tập có tối thiểu ES (n) = 2n−2 + 1 điểm trên mặt phẳng ở vị trí tổng quát, đều chứa n điểm là đỉnh của một đa giác lồi n cạnh. Như vậy, theo chứng minh của E. Klein, ES(4) = 5. Makai đã đưa ra ví dụ tám điểm không chứa năm điểm nào tạo thành ngũ giác lồi. Do đó, ES(5) ≥ 9. Lần đầu tiên công thức ES(5) = 9 đã được Đoàn Hữu Dũng chứng minh. Với một vài thay đổi nhỏ trong trình bày, lời giải này đã được Hoàng Đức Tân giới thiệu lại trong Tạp chí Toán học và Tuổi trẻ, số 174, tháng 4 năm 1990. Bài báo của Hoàng Đức Tân đã được in lại trong Tuyển chọn theo chuyên đề Toán học và Tuổi trẻ, Quyển 4, Nhà xuất bản Giáo dục, 2008, trang 183-185. Chứng minh của Đoàn Hữu Dũng cũng đã được đưa vào các cuốn sách: Hoàng Chúng, Lê Đình Phi, Quốc Trinh, Toán chọn lọc cấp III, Tập I (Hình học), Nhà xuất bản Giáo dục, 1970, Bài tập 22, trang 9; Lời giải trang 48-53; Phan Huy Khải, Các bài toán hình học tổ hợp, Nhà xuất bản Giáo dục, 2007, trang 116-120; Phan Huy Khải, Giải tích lồi 14
và các bài toán sơ cấp, Nhà xuất bản Giáo dục, 2007, trang 163-167. Giả thuyết Erd¨os–Szekeres cũng được giới thiệu trong: Nguyễn Bá Đô, Đặng Hùng Thắng, Hoàng Văn Trung, Một số vấn đề toán học chưa giải quyết được, Nhà xuất bản Giáo dục, 2007, trang 190-194. Trên các tài liệu nước ngoài, công thức ES(5) = 9 lần đầu tiên được Kalbfleisch và Stanton chứng minh năm 1970 (xem [10]). Tuy nhiên, cách chứng minh khá cồng kềnh, do đó công thức ES(5) = 9 đã được Bonnice chứng minh năm 1974 và Lovász năm 1979 chứng minh theo cách đơn giản hơn. Cách chứng minh của Bonnice về cơ bản trùng với cách chứng minh của Đoàn Hữu Dũng. Như vậy, với n = 5 ta có công thức ES(5) = 9 đã được chứng minh ngắn gọn bởi Đoàn Hữu Dũng vào năm 1967 và Bonnice vào năm 1974 (như đã chứng minh ở trên). Cùng phương pháp giải cho trường hợp n = 5, nhưng vì phải rà soát rất nhiều khả năng, nên mãi cho tới năm 2006, sau 70 năm khi giả thuyết Erd¨os–Szekeres được phát biểu, sử dụng kĩ thuật đánh dấu theo hướng của bộ ba điểm để loại bớt các trường hợp, trường hợp n = 6 mới được Szekeres và Peters giải quyết trên máy tính và chưa có lời giải trọn vẹn mà không dùng máy tính. Năm 1961, Erd¨os–Szekeres đã chứng minh ES(n) ≥ 2n−2 + 1 là đạt được theo nghĩa cận dưới. Với mọi n tồn tại tập 2n−2 điểm ở vị trí tổng quát trên mặt phẳng mà từ đó không thể lấy ra được n điểm tạo thành n-giác lồi. Vì giả thuyết Erd¨os–Szekeres chưa được chứng minh nên một lối đi là tìm cách đánh giá trên và đánh giá dưới số ES(n). Đánh giá tốt nhất hiện nay là n−2 2n−2 + 1 ≤ ES(n) ≤ C2n−5 + 1. Như vậy, cho tới nay, giả thuyết Erd¨os–Szekeres vẫn còn là thách thức đối với các nhà toán học. Giả thuyết này được Ron Graham, một chuyên gia lớn của lí thuyết đồ thị, đặt giải thưởng 1000 USD. Ngay từ năm 1935, để chứng minh sự tồn tại số N (n), G. Szekeres đã sử dụng định lí Ramsey (1930), một định lí nổi tiếng do có tính bản chất và có nhiều ứng dụng. Điều này chứng tỏ mối quan hệ sâu sắc giữa một bài toán hình học cụ thể với các kiến thức toán học tổng quát. Định lí Ramsey và Định lí Erd¨os–Szekeres (về sự tồn tại hữu hạn của số N (n)) cùng có chung một bản chất triết học sâu sắc: Từ một cấu trúc hỗn độn, không có trật tự (tập các điểm trên mặt phẳng, tập các ngôi sao trên bầu trời, tập các số nguyên tố, một đồ thị bất kì,...), nhưng đủ nhiều phần tử, có thể chọn ra được một tập có cấu trúc đẹp (tập các điểm tạo thành đa giác lồi, tập các ngôi sao hình con gấu (ông Thần Nông, gầu tát nước,...), dãy số nguyên tố tạo thành cấp số cộng, đồ thị đơn sắc,...). Gần đây, giả thuyết Erd¨os–Szekeres đã giúp chứng minh một trường hợp của giả thuyết big-clique line trong lí thuyết đồ thị. Trên con đường tìm cách chứng minh giả thuyết Erd¨os–Szekeres, các nhà toán học cũng đã phải sử dụng 15
nhiều kiến thức liên quan (Định lí Ramsey, giải tích, hình học tổ hợp,...). Bài toán Erd¨os–Szekeres đã được mở rộng theo nhiều hướng khác nhau: thay các điểm trên mặt phẳng bằng các điểm trong không gian hoặc thay các điểm thành các tập lồi hoặc thể lồi; nghiên cứu sâu hơn về cấu trúc hình học của tập các điểm (đa giác lồi rỗng, đa giác lồi gần rỗng, đa giác lồi chứa k điểm,...); quan hệ giữa số các đa giác lồi k đỉnh trong tập hợp n điểm (trên mặt phẳng hoặc trong không gian), từ đó một số bài toán và giả thuyết mới đã được phát biểu. Bài toán Erdo˝s-Szekeres nhận được sự quan tâm rộng rãi của các nhà toán học. Đã có đến vài trăm bài báo viết về giả thuyết này và những bài toán liên quan (xem danh mục tài liệu về giả thuyết Erdo˝s-Szekeres và giả thuyết Erdo˝s về đa giác lồi rỗng trong [2], [12]). 1.2 Bài toán 2 Cho n là một số tự nhiên bất kì, n ≥ 3. Hãy xác định số nguyên dương nhỏ nhất E(n) nếu nó tồn tại, sao cho từ mọi tập X chứa tối thiểu E(n) điểm ở vị trí tổng quát trên mặt phẳng, đều có thể chọn ra được n điểm là đỉnh của một đa giác lồi rỗng (đa giác không chứa bất kì điểm nào của X bên trong nó). Bài toán trên đã được P. Erdo˝s phát biểu vào năm 1978 và còn được gọi là bài toán về đa giác lồi rỗng. Trường hợp n = 3: Dễ thấy E(3)=3. Trường hợp n = 4: Dựa vào bài toán 1.1 ta có E(4)=5. Trường hợp n = 5: Năm 1978, Harborth đã chứng minh rằng E(5) = 10, tức là từ mười điểm ở vị trí tổng quát có thể chọn ra được năm điểm tạo thành ngũ giác lồi rỗng. Bất đẳng thức E(5) ≥ 10 suy ra từ Hình 2.1a và Hình 2.1b, trong đó tập chín điểm ở vị trí tổng quát không chứa năm điểm nào tạo thành ngũ giác lồi rỗng (có hai ngũ giác lồi, nhưng cả hai đều không rỗng). Hình 2.1a Tập 9 điểm của Harborth 16
Hình 2.1b Tập 9 điểm của Avis và Rappaport Goodman và Pollack (1982, 1983) đã đưa vào khái niệm đánh dấu theo hướng của bộ ba điểm. Bằng máy tính, Avis và Rappaport (1986) đã tìm ra ví dụ tập gồm 9 điểm không có ngũ giác lồi rỗng (Hình 2.1b), khác với ví dụ trên của Harborth theo nghĩa: Trong hai ví dụ này, tập các điểm là khác nhau theo cách đánh dấu theo hướng theo Goodman và Pollack. Trường hợp n ≥ 7: Với mọi n ≥ 7, Horton (1983) đã xây dựng ví dụ tập với n điểm ở vị trí tổng quát không chứa đa giác giác lồi rỗng bảy đỉnh nào. Như vậy, E(n) không tồn tại với mọi số tự nhiên n ≥ 7. Horton đã xây dựng một cách giải tích tập Sk trên mặt phẳng gồm 2k (k ≥ 1) điểm ở vị trí tổng quát không chứa đa giác lồi rỗng bảy đỉnh. Trường hợp n = 6: Như vậy, bài toán về đa giác lồi rỗng đã được giải cho n ≤ 5 và n ≥ 7. Với n = 6, Horton nhắc lại câu hỏi của Erdo˝s về đa giác rỗng như sau. Bài toán 2.1 E(6) là hữu hạn hay vô hạn? Có rất nhiều cố gắng để chứng minh sự tồn tại của E(6). Horton biểu lộ sự tin tưởng rằng E(6) tồn tại. Nicolás (2007) và Gerken (2008) độc lập nhau đã chứng minh rằng mọi tập đủ lớn các điểm ở vị trí tổng quát trên mặt phẳng chứa lục giác lồi rỗng. Ta có Định lí 2.1 (Tồn tại lục giác lồi rỗng) Tồn tại một số nguyên E(6) sao cho mọi tập với tối thiểu E(6) điểm ở vị trí tổng quát trên mặt phẳng có lục giác lồi rỗng. Cả hai cách chứng minh của Nicolás và Gerken đều đưa đến việc xét quan hệ giữa lục giác lồi rỗng và k –giác (đa giác k đỉnh) lồi lớn hơn cùng với việc xét các 17
lớp đa giác lồi bao nhau nằm bên trong k –giác lồi. Trong khi Nicolás đã cho một chứng minh đơn giản E(6) ≤ ES(25) thì Gerken phân tích thấu đáo hơn (xét 57 trường hợp) để chỉ ra rằng E(6) ≤ ES(9). Trên thực tế Gerken đã chứng minh rằng mọi 9-giác lồi (đa giác lồi 9 đỉnh) đều chứa lục giác lồi rỗng. Đây là một đánh giá tốt nhất theo nghĩa tồn tại một tập có bao lồi là 8–giác không chứa lục giác rỗng (Overmas, 2003). Valtr (2006) đã đơn giản hóa chứng minh của Gerken nhưng cho đánh giá kém hơn: E(6) ≤ ES(15) thay vì E(6) ≤ ES(9). Hệ quả Mọi tập điểm trên mặt phẳng ở vị trí tổng quát chứa không ít hơn 1717 điểm đều chứa lục giác lồi rỗng. Chứng minh Khi n = 6, từ đánh giá 7 +1= 13! 8.9.10.11.12.13 E(6) ≤ ES(9) ≤ C13 7!6! +1= 2.3.4.5.6 + 1 = 1717. Suy ra, mọi tập chứa không ít hơn 1717 điểm đều chứa lục giác lồi rỗng. Hơn nữa, nếu giả thuyết Erdo˝s–Szekeres đúng, thì E(6) ≤ ES(9) = 129. Bằng cách phân tích kĩ các trường hợp đa giác lồi bao nhau, Koselev (2007) đã chứng minh E(6) ≤ max {ES(8), 400} ≤ 463 (tương ứng, E(6) ≤ 65 nếu giả thuyết Erdo ˝s–Szekeres đúng). Như vậy, ta có Định lí 2.2 (Đánh giá trên cho lục giác lồi rỗng, Koselev, 2007) Mọi tập có tối thiểu 463 điểm ở vị trí tổng quát trên mặt phẳng đều chứa sáu điểm tạo thành lục giác lồi rỗng. Cố gắng tìm đánh giá dưới của E(6), Chvátal và Klincsek (1980) đã xây dựng một thuật toán có độ phức tạp O(n3 ) để xác định tập con lồi lớn nhất của tập n điểm trên mặt phẳng. Cải tiến phương pháp của Chvátal và Klincsek, Rappaport (1985), Avis và Rappaport (1986) đã xây dựng một thuật toán có độ phức tạp O(n3 ) về thời gian và O(n2 ) về không gian để tìm tập con (của một tập n điểm trên mặt phẳng ở vị trí tổng quát) xác định đa giác lồi rỗng lớn nhất. Bằng cách sử dụng thuật toán này, Avis và Rappaport đã tìm ra tập 15 điểm không có ngũ giác lồi rỗng. Thêm một điểm vào tập 15 điểm trên và chạy lại chương trình để tìm lục giác lồi rỗng. Tiếp tục như vậy, Avis và Rappaport đã tìm ra tập 20 điểm ở vị trí tổng quát không chứa lục giác lồi rỗng. Bằng cách cải tiến kết quả của Dobkin, Edelsbrunner và Overmars (1990), Over- mars, Scholen và Vincent (1989) đã xây dựng một thuật toán có độ phức tạp O(n2 ) về thời gian để giải bài toán sau đây: Cho trước tập hữu hạn điểm V trên mặt phẳng không chứa lục giác lồi rỗng và cho 18
điểm z ∈ / V , hãy xác định khi nào tập {z} ∪ V chứa lục giác lồi rỗng. Sử dụng thuật toán này, Overmars, Scholen và Vincent đã tìm ra tập gồm 26 điểm không chứa lục giác lồi rỗng. Do đó, E(6) ≥ 27. Năm 2003, bằng máy tính, Overmars đã tìm ra 29 điểm ở vị trí tổng quát không chứa lục giác lồi rỗng. Như vậy, E(6) ≥ 30. Như trên đã trình bày, một số thuật toán tìm đa giác lồi rỗng với số đỉnh lớn nhất xác định bởi tập các điểm cho trước đã được xây dựng. Nhờ các thuật toán này và sử dụng máy tính, ta có đánh giá dưới của đại lượng E(6). Tuy nhiên, giả thuyết sau đây vẫn chưa được chứng minh hay bác bỏ. Giả thuyết 2.1 (về lục giác lồi rỗng) E(6) = 30. Như trên ta thấy, đánh giá tốt nhất hiện nay là 30 ≤ E(6) ≤ 463. 1.3 Bài toán 3 (Bài toán về tồn tại đa giác chứa k điểm trong ) Ta có thể mở rộng Bài toán 1 và Bài toán 2 như sau. Cho số nguyên dương n ≥ 3 bất kỳ và một số dương k ≥ 0, hãy tìm số nguyên dương nhỏ nhất H(n, k) sao cho từ tập điểm X bất kỳ trên mặt phẳng ở vị trí tổng quát và chứa ít nhất H(n, k) điểm, có thể chọn được một tập con gồm n điểm là đỉnh của một đa giác lồi n cạnh chứa tối đa k điểm của X bên trong. Hiển nhiên khi k = 0 thì Bài toán 3 chính là Bài toán 2, tức là H(n, 0) = E(n) với mọi n ≥ 3. Với các giá trị nhỏ của n ta có: H(3, k) = 3; H(4, k) = 5; H(5, 0) = E(5) = 10; H(5, k) = 9 với mọi k ≥ 1. Đẳng thức H(5, k) = 9 suy ra từ nhận xét rằng, mọi ngũ giác lồi chứa hai điểm (hoặc nhiều hơn) bên trong luôn chứa ngũ giác lồi nhỏ hơn. Thật vậy, giả sử ngũ giác lồi chứa hai điểm ( hay nhiều hơn, xem hình 1.7b) bên trong. Khi đó kẻ đường thẳng đi qua hai điểm này thì đưởng thẳng đó sẽ chia mặt phẳng làm hai phần. Có ít nhất ba đỉnh của ngũ giác lồi nằm trên một nửa mặt phẳng đóng. Ba điểm này cùng với hai điểm đã cho tạo thành một ngũ giác lồi nhỏ hơn. Sử dụng tập Horton, Sendov (1995) đã chứng minh H(n, k) không tồn tại với một số giá trị đặc biệt của k và n > 7. Cụ thể, Sendov đã chỉ ra: H(9, 2), H(8, 1), H(7, 0) = E(7) không tồn tại và sự tồn tại các đại lượng H(7, 1); H(8, 2); H(9, 3) còn chưa được chứng minh. Tổng quát hơn, Sendov đã chứng minh rằng, nếu n = 4m + r − 2, hay n = 4m+s với s = r−2, m là số nguyên, r ∈ {0, 1, 2, 3} thì H(n, (s + 2) 2m−1 −4m−s−3) 19