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 ERD ¨OS VỀ ĐA GIÁC LỒI RỖNG 5 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Bài toán 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Bài toán 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.1.5 Bài toán 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 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 ) . . . . . 21 1.4 Bài toán 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ

2.1 Định lý E(6) ≤ ES(9) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Lược đồ chứng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Các định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Các trường hợp đơn giản . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Các trường hợp (3, ≥ 0) và (≥ 6, 3) . . . . . . . . . . . . . . . . . . . . 2.4.1 Các trường hợp (3, ≥ 0) và (8,3) . . . . . . . . . . . . . . . . . 2.4.2 Các trường hợp (6,3) và (7,3) . . . . . . . . . . . . . . . . . . 2.5 Các trường hợp (4, ≥ 0) và (≥ 7, 4) . . . . . . . . . . . . . . . . . . . . 2.5.1 Bước 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Bước 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.3 Bước 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.4 Bước 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.5 Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Các trường hợp (5, 0) và (≥ 7, 5, 0) . . . . . . . . . . . . . . . . . . . . 2.6.1 Các trường hợp (5, 0) và (8, 5, 0) . . . . . . . . . . . . . . . . . 2.6.2 Trường hợp (7, 5, 0) . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Các trường hợp riêng . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7.1 Trường hợp (5,1) . . . . . . . . . . . . . . . . . . . . . . . . . 2.7.2 Trường hợp (6,1) . . . . . . . . . . . . . . . . . . . . . . . . . 2.7.3 Các trường hợp (6,2) và (7,1) . . . . . . . . . . . . . . . . . . 2.8 Các trường hợp (5, ≥ 2) . . . . . . . . . . . . . . . . . . . . . . . . . . 23 23 23 25 25 27 27 27 29 34 34 35 38 38 38 40 40 40 41 41 42 43 43

2.9.1 2.9.2

2.8.1 Một quan sát cơ bản . . . . . . . . . . . . . . . . . . . . . . . 2.8.2 Các trường hợp (5, ≥ 2) . . . . . . . . . . . . . . . . . . . . . . 2.9 Các trường hợp (6, ≥ 4) . . . . . . . . . . . . . . . . . . . . . . . . . . TW X ∩ TXY (cid:54)= ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . TW X ∩ TXY = ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Các trường hợp (≥ 7, ≥ 5, ≥ 1) . . . . . . . . . . . . . . . . . . . . . . 2.10.1 Quy tắc 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10.2 Quy tắc 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10.3 Ứng dụng của Quy tắc 1 và 2 . . . . . . . . . . . . . . . . . . 2.10.4 Quy tắc 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10.5 Ứng dụng các Quy tắc 1-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10.6 Trường hợp (1, 1, 1, 1, 1, 1, 1) 2.10.7 Trường hợp (1, 1, 1, 1, 1, 1, 1, 0) . . . . . . . . . . . . . . . . . 2.10.8 Trường hợp (1, 1, 1, 1, 1, 1, 1, 1) . . . . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 46 48 49 51 52 53 54 54 56 58 59 59 61 65 66

Mở đầu

Năm 1935, Erd˝os và Szekeres đã đưa ra giả thuyết sau đây (giả thuyết Erd˝os- 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 Erd˝os-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 Erd˝os-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 Erd˝os-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 Erd˝os-Szekeres, nhiều phương pháp và bài toán mới đã xuất hiện. Năm 1978 [xem 5], Erd˝os đã phát biểu một bài toán mới, đó là Bài toán Erd˝os 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 Erd˝os-

Szekeres và bài toán Erd˝os đồ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 Erd˝os-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.

Chương 1

TỔNG QUAN VỀ BÀI TOÁN ERD ¨OS VỀ ĐA GIÁC LỒI RỖNG

1.1 Bài toán 1

1.1.1 Bài toán 1a

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.2 Bài toán 1b

Tồn tại hay không tồn tại số ES(n)?

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 n−2 + 1. Như vậy, bài toán 1a đã

quả ta được một đánh giá tốt hơn ES(n) ≤ C2n−4 được trả lời khẳng định.

1.1.3 Bài toán 1.1

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.

(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

• Khả năng 2 (Hình 1.3):

trường hợp này ta có tất cả C4 5 = 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.

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):

Hình 1.4

1.1.4 Bài toán 1.2

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.

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 Erd˝os 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à

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).

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)

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.

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)

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).

1.1.5 Bài toán 1.3

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.

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, Erd˝os 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

2n−2 + 1 ≤ ES(n) ≤ Cn−2

2n−5 + 1.

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à

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

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 Erd˝os-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 Erd˝os-Szekeres và giả thuyết Erd˝os 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. Erd˝os 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

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 Erd˝os 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

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.

E(6) ≤ ES(9) ≤ C7

13 + 1 = 13!

7!6! + 1 = 8.9.10.11.12.13

2.3.4.5.6 + 1 = 1717.

Chứng minh Khi n = 6, từ đánh giá

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 Erd˝os–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 Erd˝os–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

đ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)

không tồn tại. Sendov cũng nêu

H(n, (r + 4) 2m−1 − 4m − r) tồn tại với mọi n ≥ 6.

Giả thuyết 2.2 (Sendov, 1995)

Kết quả tương tự cũng đã được Helena Nyklová (2003) chứng minh. Hơn nữa, Nyklová đã chứng minh H(6, 5) = 19 và H(6, k) = ES(6) với k ≥ 6. Koselev đã cho một đánh giá trên cho H(6, 1) như sau.

H(6, 1) ≤ ES(7) ≤ 127.

Định lí 2.3 (Koselev, 2008)

Như vậy, ta có 17 = E(6) ≤ H(6, 1) ≤ 127. Nếu giả thuyết Erd˝os-Szekeres đúng

H(6, 1) = ES(6) = 17.

thì 17 ≤ H(6, 1) ≤ ES(7) = 33. Hơn nữa, ta có Giả thuyết 2.3 (Koselev, 2008)

Nếu giả thuyết này đúng thì H(6, 1) = H(6, 2) = H(6, 3) = H(6, 4) = H(6, 5) = 17. Đẳng thức H(6, 5) = 17 không trùng với H(6, 5) = 19 của Nyklová. Tuy nhiên, Koselev đã chỉ ra, các tính toán của Nyklová là thiếu chính xác. Kết quả sau đây của Koselev là tốt hơn kết quả của Sendov khi n bất kì.

n−7 2

n, C

n−7 − 1

(cid:16) (cid:17) Định lí 2.4 (Koselev, 2008) Với mọi n ≥ 7 thì H khi n chẵn và

n−8 2

n, 2C

n−8 − 1

2 + o(1)(cid:1)n

(cid:17) (cid:16) khi n lẻ không tồn tại.

√ (2 + o(1))n, tốt hơn đánh giá (cid:0) 4 ES(n) ≤ H(n, k) ≤ E(n) , nếu các số tương ứng tồn tại. Ta còn có

E(n) = H(n, 0) ≥ H(n, 1) ≥ H(n, 2) ≥ ...

Theo định lí trên của Koselev, về mặt tiệm cận, số lượng các điểm trong bằng của Sendov và Nyklová. Ta luôn có

và tồn tại số k(cid:48) = k(cid:48) (n) sao cho H(n, k) = ES(n) với mọi k ≥ k(cid:48). Nói cách khác, nếu tập S chứa các điểm tạo thành n –giác lồi thì đa giác ấy chứa không nhiều điểm trong. Hiển nhiên ta có, k(cid:48) (n) ≤ ES(n) − n , tuy nhiên, ta chưa biết giá trị chính xác của k(cid:48) (n) và ES(n). Câu hỏi sau đây là thú vị:

Bài toán 2.4 (Koselev, 2008) Với giá trị nào của k thì H(n, k) = ES(n) hoặc H(n, k) > ES(n)?

Vì ta chỉ biết ES(n) ≥ 2n−2 + 1 nên ta có thể đặt câu hỏi: Tìm giá trị lớn nhất của k để H(n, k) > 2n−2 + 1. Ta có

n, C

> 2n−2 + 1.

(cid:100) n−3 2 (cid:101) n−3 − (cid:6) n

(cid:18) (cid:19) (cid:7) Định lí 2.5 (Koselev, 2010) Nếu n ≥ 6 thì H

1.4 Bài toán 4

A. Bialostocki, P. Dierker , B. Voxman (1991) đã phát biểu bài toán sau đây về

sự tồn tại đa giác lồi chứa modq điểm trong Cho hai số tự nhiên bất kì, n ≥ 3 và q ≥ 2. Hãy xác định số nguyên dương nhỏ nhất H(n, modq), nếu nó tồn tại, sao cho từ mọi tập X có tối thiểu H(n, modq) điểm ở vị trí tổng quát trên mặt phẳng, có thể tìm được n điểm là đỉnh của một đa giác lồi chứa số điểm của S trong phần trong chia hết cho q.

H(3, modq) = 3; H(4, modq) = 5; H(5, modq) = H(5) = 10.

Với các giá trị nhỏ của n, các khẳng định sau đây là hiển nhiên:

Với n = 6 thì H(6, modq) = E(6) với mọi q, ngoại trừ một số hữu hạn giá trị. Có thể H(6, mod2) = ES(6) = 17, nhưng với q ≥ 3 có thể xây dựng tập điểm mà H(n, modq) > 17. Bialostocki, Dierker, Voxman đã đưa ra

Giả thuyết 2.4 Số H(n, modq) tồn tại với mọi n ≥ 3 và q ≥ 2.

Giả thuyết này cho đến nay vẫn chưa được chứng minh hoặc bác bỏ. Ta chỉ có một công thức đánh giá trên như sau.

H (n, modq) ≤ N

Định lí 2.8 (Bialostocki, Dierker, Voxman, 1991) Với n ≥ q + 2 ta có đánh giá  

R3  , trong đó n(cid:48) là số tự nhiên nhỏ nhất thỏa (cid:124)  n(cid:48), n(cid:48), ..., n(cid:48)  (cid:125) (cid:123)(cid:122) q

mãn điều kiện n(cid:48) ≥ n và n(cid:48) ≡ 2 (modq). Ở đây R (l1, l2, ..., ls; 3) là số Ramsey. Năm 1996, Caro đã nhận được kết quả tổng quát hơn cho các điểm trên mặt phẳng với các giá trị được gán cho chúng từ nhóm Abel hữu hạn và các đa giác lồi với tổng trong bằng không. Ứng dụng vào bài toán xét ở đây, ta được đánh giá

H(n, modq) ≤ 2c(q)n, trong đó c(q) là một hàm không phụ thuộc vào n, nhưng tăng theo cấp lớn hơn cấp mũ theo q. Như vậy, đánh giá này cũng cho chúng ta đánh giá cấp mũ của mũ cho H(n, modq). Tất nhiên, đánh giá trong định lí trên cần được làm chính xác hơn. Chúng ta muốn, một mặt, giảm đánh giá cấp mũ của mũ, ít ra là cho một số hệ thức giữa n và q. Mặt khác, có vẻ như điều kiện n ≥ q + 2 là không cần thiết trong chứng minh sự tồn tại của H(n, modq). Chỉ có duy nhất một kết quả theo hướng thứ nhất: Károlyi, Pach, Toth (2001) đã chứng minh tồn tại H(n, modq) khi n ≥ 5q 6 + O(1). Thực ra kết quả này tồi hơn kết quả của Bialostocki, Dierker, Voxman (1991). P. Valtr thông báo đã chứng minh tồn tại H(n, modq) khi n ≥ 3q 4 + O(1). Gần như không có kết quả mới nào theo hướng thứ hai, Caro đã đưa ra

Giả thuyết 2.5 (Caro, 1996) Với c(q) nào đó ta có H(n, modq) ≤ ES (c(q) + n).

Koselev đã chứng minh định lí sau.

Định lí 2.9 (Koselev, 2009) Nếu n ≥ 2q − 1 thì H(n, modq) ≤ ES (q (n − 4) + 4).

Đánh giá theo định lí này chính xác hơn nhiều so với đánh giá của Caro, bởi vì N (q (n − 4) + 4) ≤ 22qn+O(1). Và do đó giải phóng được đánh giá cấp mũ của mũ. Điều kiện n ≥ 2q − 1 mạnh hơn điều kiện n ≥ q + 2 một chút và giả thuyết Caro vẫn chưa được chứng minh hay bác bỏ. Tuy nhiên, định lí trên là một bước quan trong tiến tới lời giải của bài toán. Định lí sau đây là một cải tiến của định lí của Bialostocki, Dierker, Voxman và yếu hơn kết quả của Caro và Định lí 2.9, nhưng cũng đáng được nhắc đến. 

Định lí 2.10 (Koselev, 2009) Nếu n ≥ q+2 và q chẵn thì H(n, mod q) ≤ R3  . n, ..., n (cid:124) (cid:123)(cid:122) (cid:125) q  

Nếu n ≥ q + 2 và q lẻ thì H(n, modq) ≤ R3  . g(n), n, ..., n (cid:124) (cid:123)(cid:122) (cid:125) q−1

Chương 2

CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ

Năm 1978, Erdos đặt ra bài toán xác định số nguyên dương nhỏ nhất E(n), nếu tồn tại, sao cho bất kỳ tập X nào gồm ít nhất E(n) điểm ở vị trí tổng quát trên mặt phẳng chứa n điểm là đỉnh của đa giác lồi n cạnh không chứa điểm nào của X bên trong. Hiển nhiên E(n) = n với n ≤ 3. Dễ dàng chỉ ra E(4) = 5. Năm 1978, Harborth [4] chứng minh rằng E(5) = 10. Năm 1983, Horton [9] chỉ ra rằng với mọi n ≥ 7, E(n) không tồn tại. Đến nay, bài toán xác định E(6) vẫn là bài toán mở. Năm 2003, dựa vào các thuật toán thực hiện trên máy tính, Overmars đã chỉ ra rằng E(6) ≥ 30.

Chương này trình bày chứng minh của T. Gerken ([7], năm 2008) nói rằng mọi đa giác lồi chín đỉnh (9-giác lồi, convex 9-gon) đều chứa lục giác lồi rỗng(xem, [7].

2.1 Định lý E(6) ≤ ES(9)

ES(n) ≤ Cn−2 lồi là đa giác lồi tám cạnh nhưng không chứa một lục giác lồi rỗng.

Định lý này đã được Gerken chứng minh trong [3], 2008. Đánh giá 2n−2 + 1 ≤ 2n−5 + 1 cho ta 129 ≤ ES(9) ≤ 1717. Lưu ý rằng tồn tại tập điểm có bao

2.2 Lược đồ chứng minh

Gọi X là tập hợp các điểm trên mặt phẳng ở vị trí tổng quát và |X| là số phần tử (số điểm) của tập X. Theo công thức đánh giá trên của số Erd¨os–Szekeres, nếu |X| ≥ ES(9) thì X chứa tập đỉnh của một 9-giác lồi (có thể không rỗng).

Gọi H ⊆ X là tập các đỉnh của một 9-giác lồi trong X. Không giảm tính tổng

quát, ta có thể coi X ∩ conv(H) là tập nhỏ nhất theo nghĩa không tồn tại tập chín điểm nào của X nằm trong conv(H) mà chúng tạo thành 9-giác lồi khác, ở đây conv(H) là kí hiệu bao lồi của tập H. Gọi I := conv(H) ∩ (X \ H) là tập hợp các điểm của X nằm trong phần trong bao lồi của H. Lưu ý rằng I có thể không tạo thành đỉnh của một đa giác lồi nhưng tập tất cả các điểm của conv(I) là một đa giác lồi (có thể là một đoạn thẳng nếu |I| = 2 hoặc một điểm nếu |I| = 1) nằm trong conv(H) và tập đỉnh của nó được kí hiệu là ∂I (∂I có thể khác I). Đặt i := |∂I|. Nếu |I| > 2, gọi J := conv(I) ∩ (X \ ∂I) là tập các điểm nằm bên trong conv(I). Lưu ý rằng conv(J) cũng là một đa giác lồi và tập đỉnh của nó được kí hiệu là ∂J. Đặt j := |∂J| (Hình 1).

Lưu ý rằng 0 ≤ i, j ≤ 8 vì nếu ngược lại thì sẽ lại có một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho, trái với giả thiết về tập H. Điều này dẫn tới 57 trường hợp ta cần xét đó là ba trường hợp i = 0, 1, 2 và năm mươi tư (54) trường hợp (i, j) ∈ {3, ..., 8} × {0, ...8}. Ta sẽ khẳng định rằng trong mỗi trường hợp này thì hoặc là tìm thấy một đa giác lồi rỗng u (u ≥ 6) cạnh (có ngay điều phải chứng minh), hoặc là xuất hiện một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho dẫn đến mâu thuẫn với giả thiết tập H là "nhỏ nhất" theo nghĩa trên.

Hình 2.1 Các kí hiệu cơ bản

2.2.1 Kí hiệu

Bảng 1 Tóm tắt lược đồ chứng minh: ví dụ, phần chứng minh trường hợp (8,5) được trình bày ở mục 6 (trường hợp riêng) và mục 10 (trường hợp chung).

2.2.2 Các định nghĩa

Ta sử dụng kí hiệu (i, j) để biểu diễn một trường hợp cụ thể, trong đó i := |∂I| và j := |∂J| với I và J là các tập như đã trình bày ở trên. Kí hiệu (i, j, k), trong đó k là số điểm của X nằm bên trong bao lồi của J, tức là số phần tử của tập hợp K := conv(J) ∩ (X \ ∂J). Kí hiệu "≥ x" có nghĩa x là cận dưới của i, j hoặc k. Xem Bảng 1 để theo dõi vị trí phần chứng minh của trường hợp cụ thể.

(ABC) := [HAB (C) ∩ HBC(A)] \conv ({A, B, C}).

Nhận xét

Cho ba điểm P, Q, R ở vị trí tổng quát, nửa mặt phẳng HP Q(R) được xác định là nửa mặt phẳng mở có bờ là P Q và chứa R. Một xích lồi (convex chain) A1A2...Ak là một tập các đỉnh liên tiếp của một đa giác lồi A1A2...An (n ≥ k). Cho trước một xích lồi ba điểm ABC, miền tam giác (3-sector) (ABC) cho bởi xích lồi được xác định như sau

Ba điểm S, T, U nằm trong (ABC) có thể được sử dụng để dựng một lục giác

lồi nếu A, B, C ∈ (ST U ) (xem Hình 2a).

Cho trước môt xích lồi bốn điểm ABCD. Miền tứ giác (4-sector) (ABCD) được xác định như sau

(ABCD) := [(ABC) ∩ (BCD)] \conv ({A, B, C, D}).

Nhận xét

(ABCDE) := [(ABCD) ∩ (BCDE)] \conv ({A, B, C, D, E}).

Nhận xét

Hai điểm S, T nằm trong miền (ABCD) có thể được sử dụng để dựng một lục giác lồi nếu đường thẳng ST không cắt conv ({A, B, C, D}) (Hình 2b). Điều này cũng có nghĩa, bằng cách dựng, cho trước bờ P Q của conv(I) (hoặc conv(J)) thì nhiều nhất ba đỉnh của H (hoặc ∂I) có thể nằm trong nửa mặt phẳng bờ P Q và không chứa bất kỳ điểm nào khác của I (hoặc J) mà không tạo ra một lục giác lồi rỗng. Ở các hình bên dưới, ta sử dụng kí hiệu (P Q) để biểu thị điều này (Hình 2c). Cuối cùng, cho trước một xích lồi năm điểm ABCDE, khi đó miền ngũ giác (5- sector) (ABCDE) được xác định như sau

Một điểm (đơn) nằm trong miền (ABCDE) có thể được sử dụng để dựng một

lục giác lồi (Hình 2d).

Hình 2.2 Biểu diễn các miền

2.3 Các trường hợp đơn giản

(≥ 6, 0) và (≥ 3, ≥ 6, 0) là hiển nhiên vì một lục giác lồi rỗng đã có sẵn. Trường hợp (1,0): Giả sử điểm duy nhất nằm trong conv(H) là A. Kẻ một đường thẳng qua A và một đỉnh B bất kì của conv(H). Khi ấy, vì số đỉnh còn lại của conv(H) là 8 nên theo nguyên lý Dirichlet sẽ có ít nhất 4 đỉnh nằm trong một nửa mặt phẳng có bờ là AB. Bốn điểm này tạo với A và B một lục giác lồi rỗng. Lập luận tương tự với trường hợp (8,1). Trường hợp (7,2): Đường thẳng đi qua hai điểm A, B bên trong đa giác lồi 7 đỉnh chia mặt phẳng thành hai phần, có một phần chứa ít nhất 4 điểm và cùng với A, B tạo thành lục giác lồi rỗng. Tương tự cho các trường hợp (8,2), (2,0).

Giả sử H là tập đỉnh của 9-giác lồi đã cho. Lưu ý rằng các trường hợp (0,0),

2.4 Các trường hợp (3, ≥ 0) và (≥ 6, 3)

Ta chia các trường hợp (3, ≥ 0) và (≥ 6, 3) theo hai nhóm: nhóm 1 gồm các

2.4.1 Các trường hợp (3, ≥ 0) và (8,3)

trường hợp (3, ≥ 0) và (8,3), nhóm 2 gồm các trường hợp (6,3) và (7,3).

Các kí hiệu ai, bi là số đỉnh của 9-giác lồi conv(H) (trong trường hợp (3, ≥ 0))

hoặc 8-giác lồi conv(I) (trong trường hợp (8,3)) trong mỗi miền.

Hình 2.3 Kí hiệụ sử dụng cho các trường hợp (3, ≥ 0) và (≥ 6, 3)

Giả sử không có lục giác lồi rỗng nào tạo được từ chín điểm của H (hoặc 8 điểm của ∂I) và ba điểm P, Q, R. Khi đó, qua cách dựng các miền như trong Hình 3, ta có

1 ≤ a1 + b1 + a2 ≤ 3.

(4.1)

1 ≤ a2 + b2 + a3 ≤ 3.

(4.2)

1 ≤ a3 + b3 + a1 ≤ 3.

(4.3)

(1 ≤ i ≤ 3)

vì nếu ngược lại thì sẽ xuất hiện một xích lồi gồm bốn đỉnh và cùng với hai trong ba đỉnh của tam giác để tạo thành một lục giác lồi rỗng. Thật vậy, nếu a1 + b1 + a2 = 0 thì tất cả các đỉnh của 9-giác lồi H trong trường hợp (3, ≥ 0) (hoặc 8-giác lồi conv(I) trong trường hợp (8,3)) đều nằm trên nửa mặt phẳng bờ P Q và chứa R, điều này vô lý với giả thiết các đa giác bao nhau. Nếu a1 + b1 + a2 ≥ 3, kí hiệu ba điểm của I trong trường hợp (3, ≥ 0) (hoặc J trong trường hợp (8,3)) là P, Q, R. Xét nửa mặt phẳng αP Q có bờ là P Q không chứa R. Khi ấy nếu αP Q chứa ít nhất bốn điểm A, B, C, D của H (hoặc ∂I trong trường hợp (8,3)) thì xích lồi ABCD cùng với P, Q tạo thành một lục giác lồi rỗng. Như vậy αP Q chỉ có thể chứa tối đa ba điểm để không tạo ra một lục giác lồi rỗng. Hơn nữa, ta có

0 ≤ bi ≤ 2;

(cid:48) nằm trong P QR (nếu có) sẽ tạo thành một lục giác lồi rỗng.

(4.4)

3 (cid:88)

vì nếu ngược lại, tức là tồn tại i0 (i0 ∈ {1, 2, 3}), thí dụ i0 = 1, sao cho b1 = 3 thì một xích lồi ba điểm trong miền (QRP ) sẽ cùng với hai đỉnh của tam giác và hoặc là đỉnh thứ ba R của tam giác (nếu P QR là tam giác rỗng) hoặc là một trong những điểm R Kết hợp các đánh giá (4.1-4.4) suy ra

(ai + bi) ≤ 15.

i=1

(4.5)

(ai + bi) ≤ 7, 5.

3 (cid:80) i=1

Tức là

Do đó, đa giác bao quanh tam giác RP Q chỉ có thể có nhiều nhất bảy đỉnh. Vô lí vì H có 9 đỉnh (trong trường hợp (3, ≥ 0)) và ∂I có 8 đỉnh (trong trường hợp (8,3)). Vậy, trong cả hai trường hợp thì đều tồn tại một lục giác lồi rỗng. Nhận xét Nếu tam giác P QR không rỗng thì tồn tại điểm R(cid:48) (như trong chứng minh) nằm trong conv(P, Q, R)sao cho P QR(cid:48) là tam giác rỗng.

2.4.2 Các trường hợp (6,3) và (7,3)

Các trường hợp (6,3) và (7,3) có thể giải quyết bằng cách nghiên cứu cẩn thận các khả năng có thể xảy ra của dãy hữu hạn (a1,b1,a2,b2,a3,b3) dựa vào hệ các ràng buộc (4.1-4.4). Lưu ý rằng bộ ba (ai,bi,ai+1) với ai = ai+1 = 0 là không thể, vì khi đó có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho (Hình 4). Thật vậy, ở Hình 4a (a2 = a3 = 0, b2 = 1), thay các đỉnh của 9-giác lồi H nằm trong hợp của các miền (AQB) và (BRC) (theo cách dựng thì ít nhất một và nhiều nhất là bốn đỉnh nếu không tồn tại một lục giác lồi rỗng, tức là còn ít nhất năm đỉnh của H nằm trong miền (AQRC)) bởi các điểm từ xích lồi AQRC (độ dài là bốn). Ở Hình 4b (a2 = a3 = 0, b2 = 2), ta thay nhiều nhất bốn đỉnh thích hợp của 9-giác lồi H nằm trong hợp của các miền (AQB1),(B1QP RB2) và (B2RC) bởi các điểm từ xích lồi AQRC.

Hình 2.4 Các trường hợp (x, 3) suy biến: (ai, bi, ai+1) = (0, 1, 0) (hình 4a) và (ai, bi, ai+1) = (0, 2, 0) (hình 4b). Các chữ số biểu thị cho số đỉnh của 9-giác lồi H có thể nằm trong mỗi miền mà không tạo ra một lục giác lồi rỗng.

Bảng 2 Các trường hợp (6, 3, 0) và (7, 3, 0): Tổng hợp các trường hợp con với giả thiết (i) a1 ≥ a2 ≥ a3 và (ii) b2 ≥ b3 khi cố định (a1, b1, a2). Dấu "*" có thể là một số tùy ý. Lưu ý rằng từ đánh giá (4.1) ta có a1 + a2 ≤ 3. Bây giờ, không giảm tính tổng quát, ta giả sử rằng (i) a1 ≥ a2 ≥ a3 và (ii) b2 ≥ b3 khi cố định (a1, b1, a2) (Hình 3). Khi đó, từ hệ các ràng buộc ở trên ta thấy các khả năng phân bố đỉnh (đúng đến phép quay và đối xứng) có thể xảy ra là (2, 0, 1, 2, 0, 1), (1, 1, 1, 1, 1, 1),(1, 1, 1, 2, 0, 2), (1, 1, 1, 2, 0, 1) và (1, 0, 1, 2, 0, 2) (Bảng 2). Các trường hợp này được giải quyết riêng biệt như sau:

• Trường hợp (2, 0, 1, 2, 0, 1) được giải quyết như minh họa trong hình 5. Từ nay về sau, các "chữ số" ta dùng để mô tả số đỉnh của đa giác lồi bên ngoài có thể nằm trong mỗi miền mà không tạo ra một lục giác lồi rỗng. Vì hợp của các miền bao quanh lục giác lồi ABCDEF (conv(I)) chỉ cho phép tối đa tám điểm của 9-giác lồi H (9 đỉnh) nên sẽ có một lục giác lồi rỗng xuất hiện. • Hình 6 minh họa cách giải trường hợp (1, 1, 1, 1, 1, 1), với điểm Q của tam giác P QR nằm bên trong tam giác BDF . Khi đó tồn tại tứ giác lồi rỗng BQDC nên miền (BQDC) không chứa quá một điểm của 9-giác lồi H vì nếu không sẽ có ngay một lục giác lồi rỗng. Vì hợp của các miền bao quanh lục giác lồi ABCDEF (conv(I)) chỉ cho phép tối đa tám điểm của 9-giác lồi H (9 đỉnh) nên sẽ có một lục giác lồi rỗng xuất hiện. Tương tự, ta có thể giải quyết trường hợp khi các điểm khác như P, Q nằm bên trong tam giác BDF . Nếu cả ba điểm P, Q, R đều không nằm trong tam giác BDF thì ta có ngay lục giác lồi rỗng P BQDRF .

Hình 2.5 Trường hợp (6, 3, 0) với sự phân bố (2, 0, 1, 2, 0, 1)

• Hình 7 minh họa lời giải cho trường hợp (1, 1, 1, 2, 0, 2), với điểm Q nằm bên ngoài tam giác BCD. Khi đó, tứ giác CBQD tồn tại và miền (CBQD) không chứa quá một điểm của 9-giác lồi H vì nếu không sẽ có ngay một lục giác lồi rỗng. Vì hợp của các miền bao quanh lục giác lồi ABCDEF (conv(I)) chỉ cho phép tối đa tám điểm của 9-giác lồi H (9 đỉnh) nên sẽ có một lục giác lồi rỗng xuất hiện. Nếu Q nằm trong tam giác BCD thì ta có ngay lục giác lồi rỗng BQDERP .

Hình 2.6 Trường hợp (6, 3, 0) với sự phân bố (1, 1, 1, 1, 1, 1). Giả sử Q ∈ (cid:52)BDF

• Trường hợp (1, 1, 1, 2, 0, 1) được giải quyết như minh họa ở hình 8.

Hình 2.7 Trường hợp (7, 3, 0) với sự phân bố (1, 1, 1, 2, 0, 2). Giả sử Q /∈ (cid:52)BCD

• Hình 9 minh họa lời giải cho trường hợp (1, 0, 1, 2, 0, 2).

Hình 2.8 Trường hợp (6, 3, 0) với sự phân bố (1, 1, 1, 2, 0, 1).

Hình 2.9 Trường hợp (6, 3, 0) với sự phân bố (1, 0, 1, 2, 0, 2).

Phần chứng minh cho các trường hợp (6, 3, ≥ 1) và (7, 3, ≥ 1) được trình bày ở

mục 5 bên dưới.

2.5 Các trường hợp (4, ≥ 0) và (≥ 7, 4)

2.5.1 Bước 1a

Các trường hợp (4, ≥ 0) và (≥ 7, 4) có thể giải quyết theo ba bước đồng thời:

Đầu tiên, xét các trường hợp (4, 0) và (8, 4, 0). Ta sử dụng cách tiếp cận tương tự như Mục 4. Các kí hiệu được mô tả như ở Hình 10, trong đó ai, bi (1 ≤ i ≤ 4) biểu thị cho số đỉnh của 9-giác lồi H (trường hợp (4,0)) hoặc 8-giác lồi conv(I) (trường hơp (8,4,0)) nằm trong mỗi miền.Giả sử không tồn tai một lục giác lồi rỗng thì ta đi đến hệ bất đẳng thức sau:

1 ≤ a1 + b1 + a2 ≤ 3.

(5.1)

1 ≤ a3 + b3 + a4 ≤ 3.

(5.2)

Hình 2.10 Kí hiệu cho các trường hợp (4, ≥ 0) và (≥ 7, 4)

Vì nếu ngược lại, tức là a1 + b1 + a2 ≥ 3, sẽ có ít nhất bốn đỉnh A, B, C, D của 9-giác lồi H (trường hợp (4,0)) hoặc 8-giác lồi conv(I) (trường hơp (8,4,0)) sẽ nằm trong nửa mặt phẳng có bờ là P Q và không chứa R. Khi ấy ta có lục giác lồi rỗng ABCDQP .

(Ở đây, các đỉnh nằm trong hơn một miền thì có thể gán tùy ý vào một miền

mà nó nằm trong và do đó, nó chỉ được tính một lần). Nếu không tồn tại một lục giác lồi rỗng, ta có

0 ≤ b2 + b4 ≤ 1.

(5.3)

2.5.2 Bước 1b

Vì nếu ngược lại, tức là b2 + b4 ≥ 1, sẽ có ít nhất hai đỉnh của 9-giác lồi H (trường hợp (4,0)) hoặc 8-giác lồi conv(I) (trường hơp (8,4,0)) nằm trong hợp các miền (P QRS) và (QP SR). Hai đỉnh này tạo với bốn điểm P, Q, R, S một lục giác lồi rỗng. Kết hợp các ràng buộc (5.1-5.3), ta được a1 + b1 + a2 + a3 + b3 + a4 + b2 + b4 ≤ 7. Ta thấy tối đa bảy đỉnh của 9-giác lồi H (trường hợp (4,0)) và 8-giác lồi conv(I) (trường hợp (8,4,0)) có thể nằm xung quanh tứ giác, dẫn đến mâu thuẫn ở hai trường hợp này.

Tiếp theo, ta xét trường hợp (7, 4, 0) và đánh giá các khả năng có thể xảy ra

dựa trên hệ các ràng buộc (5.1-5.3). Tương tự như trên, ta có:

1 ≤ a1 + b4 + a4 ≤ 3.

(5.4)

1 ≤ a2 + b2 + a3 ≤ 3.

(5.5)

0 ≤ b1 + b3 ≤ 1.

(5.6)

bi ≤ 2. Hơn nữa, từ (5.1) và (5.2) (hoặc

4 (cid:80) i=1 (5.4) và (5.5)), nếu b2 = b4 = 0 (hoặc b1 = b3 = 0) thì nhiều nhất sáu đỉnh của 7-giác lồi conv(I) có thể nằm xung quanh tứ giác, vô lý. Do vậy, chỉ có thể xảy ra bốn trường hợp với (b1, b2, b3, b4) là (0,0,1,1),(0,1,1,0),(1,0,0,1)và (1,1,0,0). Không giảm tính tổng quát, giả sử (b1, b2, b3, b4) = (1, 1, 0, 0). Bằng cách chọn a1 ∈ 0, 1, 2, thì các khả năng có thể xảy ra với dãy hữu hạn (a1,b1,a2,b2,a3,b3,a4,b4) là (2,1,0,1,2,0,1,0), (1,1,1,1,1,0,2,0) và (0,1,2,1,0,0,3,0) (đúng với cả phép quay và đối xứng). Những trường hợp này có thể giải riêng biệt như sau: • Trường hợp (2,1,0,1,2,0,1,0) có thể được giải quyết như minh họa trong Hình 11. Lưu ý rằng có tối đa hai trong ba điểm D, E, F có thể nằm ở một trong miền (QP R) và (RP S) mà không tạo ra một lục giác lồi rỗng, vì ngược lại ta có ngay một lục giác lồi rỗng là DEF P QR. Chứng minh tương tự cho A, B, C và các miền (QRP ) và (P RS). Điều này được mô tả bởi các mũi tên. Lưu ý rằng một miền tứ giác và một miền ngũ giác được tạo ra, thí dụ là miền (BP RQC) và (ERSF ).

Từ (5.3) và (5.6) ta suy ngay ra rằng

• Hình 12 mô tả lời giải cho trường hợp (1,1,1,1,1,0,2,0), với đỉnh Q của tứ giác P QRS nằm bên ngoài tam giác BCD. Khi đó tồn tại tứ giác BQDC. Lưu ý rằng nếu Q nằm bên trong tam giác BCD thì ta có ngay lục giác lồi rỗng BQDRSP .

Hình 2.11 Trường hợp (7,4,0) với cách phân bố điểm (2,1,0,1,2,0,1,0)

Q /∈ (cid:52)BCD

Hình 2.12 Trường hợp (7,4,0) với cách phân bố (1,1,1,1,1,0,2,0). Giả sử

• Trường hợp (0,1,2,1,0,0,3,0) có thể giải quyết như mô tả trong Hình 13. Lưu ý rằng nếu cả B và C cùng nằm trong miền (P SQ) hoặc (QSR) thì ta có ngay một

Hình 2.13 Trường hợp (7,4,0) với cách phân bố (0,1,2,1,0,0,3,0)

2.5.3 Bước 2

lục giác lồi rỗng là ABCQSP hoặc BCDRSQ. Điều này được mô tả bởi các mũi tên.

Bây giờ ta nghiên cứu các trường hợp (4,1) và (8,4,1). Xét các miền được tạo ra bởi các tia xuất phát từ điểm đơn nằm trong J (hoặc K) qua các đỉnh của tứ giác conv(I) (hoặc conv(J)). Mỗi miền trong bốn miền này có thể chứa tối đa hai đỉnh của 9-giác lồi H(hoặc 8-giác lồi conv(I)) vì nếu không thì một lục giác lồi rỗng có thể dựng được. Vì 4.2<9 nên trong trường hợp 9-giác lồi ta có ngay một lục giác lồi rỗng. Với trường hợp 8-giác lồi, ta giải quyết bằng lập luận như mô tả trong Hình 14.

2.5.4 Bước 3

Hình 2.14 Trường hợp (8,4,1)

2.5.5 Tổng kết

Để giải quyết các trường hợp (4, ≥ 2), cố định một điểm P ∈ J rồi dựng các miền như ở bước 2. Sau đó thay điểm P bởi một diểm thích hợp của J trong mỗi miền (nếu cần). Ta lập luận như bước 2. Tiến hành tương tự với các trường hợp (8, 4, ≥ 2) bằng cách chọn một điểm P ∈ K tùy ý.

Những khảo sát ở các Mục 5.3 và Mục 5.4 cũng có thể áp dụng một cách dễ dàng vào trường hợp (6, 3, ≥ 1) (như minh họa trong Hình 15), (7, 3, ≥ 1) và (7, 4, ≥ 1) (như minh họa trong Hình 16).

Hình 2.15 Trường hợp (6,3,1)

Hình 2.16 Trường hợp (7,4,1)

Nhắc lại lần nữa, ý tưởng chính ở đây là ta cố định một điểm P ∈ K và tạo nên các miền bởi các tia xuất phát từ P và đi qua các đỉnh của đa giác lồi conv(J). Ta thấy rằng mỗi miền này chỉ chứa tối đa hai đỉnh của conv(I) mà không tạo ra một lục giác lồi rỗng. Điều này vẫn đúng nếu những điểm khác của K nằm trong các miền này. Bây giờ ta tạo ra một tập hợp các miền khác mà hợp của chúng phủ hoàn toàn phần diện tích bên ngoài của conv(I) như minh họa trong

các hình. Hướng tiếp cận này sẽ được nghiên cứu kĩ hơn ở mục 10 với các trường hợp (≥ 7, ≥ 5, ≥ 1).

2.6 Các trường hợp (5, 0) và (≥ 7, 5, 0)

2.6.1 Các trường hợp (5, 0) và (8, 5, 0)

(1 ≤ i ≤ 5).

Ta sử dụng cách tiếp cận tương tự như ở các Mục 4 và Mục 5, mở rộng khái niệm và kí hiệu của Hình 3 và Hình 10. Giả sử không có lục giác lồi rỗng nào tồn tại, khi đó ta suy ra hệ bất đẳng thức sau

bi = 0

(6.1)

(1 ≤ i ≤ 5; a6 := a1)

1 ≤ ai + ai+1 ≤ 3

(6.2)

5 (cid:88)

(những đỉnh nằm ở trong hơn một miền chỉ tính một lần). Từ hệ bất đẳng thức suy ra

(ai + bi) ≤ 15.

i=1

(6.3)

2.6.2 Trường hợp (7, 5, 0)

Điều này dẫn đến mâu thuẫn vì các đa giác lồi bao ngoài đều có chín hoặc tám đỉnh.

Từ hệ (6.1-6.3) ta thấy rằng ở trường hợp này dãy hữu hạn (a1,b1,a2,b2,a3,b3,a4,b4,a5,b5)

chỉ có thể xảy ra khả năng là (2,0,1,0,2,0,1,0,1,0) (đúng với cả phép quay). trường hợp này được giải như mô tả trong Hình 17.

Hình 2.17 Trường hợp (7,5,0)

2.7 Các trường hợp riêng

2.7.1 Trường hợp (5,1)

Trường hợp này có thể giải quyết như minh họa trong Hình 18. Nhận thấy rằng P phải nằm trong một trong các tam giác (cid:52)ABD, (cid:52)BCE, (cid:52)CDA, (cid:52)DEB và (cid:52)EAC (vì các tam giác này phủ ngũ giác lồi). Không giảm tính tổng quát, giả sử P nằm trong tam giác ABD (như trong Hình vẽ). Đường thẳng P D cắt ngũ giác lồi tạo thành hai tứ giác AEDP và P DCB (và một tam giác). Giả sử không tồn tại một lục giác lồi rỗng, khi đó ta có m1 + m2 ≤ 1 và n1 + n2 ≤ 1 (như đã thống nhất ở các mục trước, các biến biểu thị cho số đỉnh của 9-giác lồi nằm trong các miền tương ứng). Điều này dẫn tới có tối đa tám điểm ở vị trí xích lồi có thể nằm xung quanh ngũ giác mà không tạo ra một lục giác lồi rỗng.

2.7.2 Trường hợp (6,1)

Hình 2.18 Trường hợp (5,1)

Hình 2.19 Trường hợp (6,1)

Trường hợp này có thể giải quyết được như mô tả trong Hình 19. Lưu ý rằng điểm P phải nằm trong một trong hai tứ giác ADEF hoặc ABCD (như trên hình vẽ). Thêm nữa, nếu P nằm trên tứ giác ABCD thì hoặc P ∈ (cid:52)ABC hoặc P ∈ (cid:52)BCD, khi đó ta có ngay lục giác lồi rỗng AP CDEF hoặc BP DEF A. Do vậy, ta có thể giả

2.7.3 Các trường hợp (6,2) và (7,1)

sử tồn tại các tứ giác lồi AP CB và CBP D và lập luận như minh họa trong Hình 19.

Trường hợp (6,2) được giải quyết như minh họa trong Hình 20. Lưu ý rằng nếu bốn đỉnh A, B, C, D của lục giác cùng nằm trên một nửa mặt phẳng bờ P Q thì ta có ngay một lục giác lồi rỗng ABCDP Q. Trường hợp (7,1) ta xử lý tương tự, với một trong bảy đỉnh của 7-giác sẽ đóng vai trò của P .

Hình 2.20 Trường hợp (6,2)

2.8 Các trường hợp (5, ≥ 2)

2.8.1 Một quan sát cơ bản

Các quan sát sau đây sẽ được sử dụng cho các mục tiếp theo.

Tn nhỏ hơn t thì có thể dựng được một

khác của J. Nếu số điểm của tập hợp Quan sát 1 Giả sử j > 2 và đăt 2 ≤ t ≤ min{i − 1, j}. Xét một dãy gồm t đỉnh liên tiếp V1, V2, ..., Vt của conv(J). Kí hiệu Tn là tập hợp các đỉnh Ul của đa giác lồi conv(I) nằm trong nửa mặt phẳng mở có bờ là VnVn+1 và không chứa điểm nào t−1 (cid:83) n=1

9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Chứng minh Ta chứng minh quy nạp theo t. Ta dùng kí hiệu Ul (l ∈ N0) để biểu

thị các đỉnh của conv(I). Lưu ý rằng do I bao J nên |Tn| > 0 với mọi n theo cách xác định J.

Tn| = |T1| < 2 nên |T1| = 1. Giả sử T1=: {U1} (Hình 21). Ta

t−1 (cid:83) n=1

1 ∈ J ∩ (cid:52)U0V1U1 (hoặc V (cid:48)

1 (hoặc V (cid:48)

2) để tạo ra các miền tam giác mới là (U0V (cid:48) 1U1 và (cid:52)U1V (cid:48)

2U2) mà các tam giác tương ứng là (cid:52)U0V (cid:48)

Với t = 2. Ta có |

thấy rằng tối đa bốn đỉnh của 9-giác lồi H có thể nằm trong hợp của các miền tam giác (U0V1U1) và (U1V2U2), trong đó U0 và U2 là các đỉnh của conv(I) đứng liền trước và liền sau U1. (Lưu ý rằng U0 (cid:54)= U2 vì ta giả sử t < i). Từ đánh giá trên suy ra không có điểm nào của J nằm bên trong tam giác (cid:52)U0V1U1 (hoặc (cid:52)U1V2U2). Thật vậy, giả sử ngược lại, nếu V (cid:48) 2 ∈ J ∩ (cid:52)U1V2U2) thì thay V1 (hoặc V2) bởi V (cid:48) 1U1) và (U1V (cid:48) 2U2 không chứa bất kỳ điểm nào của J. Lưu ý rằng các miền tam giác mới này cũng phủ phần diện tích bên ngoài conv(I) bị các miền tam giác ban đầu phủ (thậm chí lớn hơn). Theo giải thích trên, mỗi miền này cho phép chứa tối đa hai đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng. Thay thế những đỉnh này bởi các điểm từ xích lồi U0V1V2U1 (có độ dài là bốn) thì sẽ tạo ra một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. (Lập luận tương tự như trong Mục 4.2).

Hình 2.21 Quan sát 1: t = 2

Tn nhỏ

t−1 (cid:83) n=1

n=1 Tn| < t − 1 thì | ∪t−2

n=1 Tn| ≤ | ∪t−1

Bây giờ với t > 2. Ta phải chứng minh rằng nếu số điểm của tập hợp

hơn t thì có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Nếu | ∪t−1 n=1 Tn| < t, do đó khẳng định đã được chứng minh bởi giả thiết quy nạp. Vì vậy ta giả sử rằng | ∪t−1 n=1 Tn| = t − 1. Kí hiệu các đỉnh liên tiếp của conv(I) là Ul(l ∈ N0) với U1 ∈ T1 và U0 /∈ T1 (vì I bao J nên ∃U0 /∈ T1). Từ giả thiết quy nạp kéo theo U2 ∈ T1 vì nếu không thì |T1| = 1.

(cid:48)

Bây giờ ta xây dựng các miền như sau, bắt đầu với miền tam giác (U0V1U1), miền này có thể chứa tối đa hai đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng. (Như trên, nếu cần có thể thay V1 bởi V 1). Tiếp theo ta dựng miền tứ giác (U1V1V2U2), (U2V2V3U3),...,(Ut−2Vt−2Vt−1Ut−1), mỗi miền này có thể chứa tối đa một đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng, xem Hình 22.

Hình 2.22 Quan sát 1: t > 2

m=pTm (cid:12) (cid:12) ≤ p.

(cid:12) (cid:12) ≤ (t − 1) − p.

(cid:48)

(cid:12)U t−1 m=1Tm

t ).

Lưu ý rằng mỗi bước xây dựng được xác định dựa trên giả thiết quy nạp. Ta có thể dựng miền (U1V1V2U2) với U1, U2 ∈ T1. Giả sử tồn tại số nhỏ nhất p ∈ N sao cho (UpVpVp+1Up+1) không là tứ giác lồi. Điều này có nghĩa là Up ∈ (∪p−1 m=1Tm)\Tp hoặc Up+1 ∈ (∪t−1 m=p+1Tm)\Tp. Ở trường hợp thứ nhất, điều này dẫn đến (cid:12) Ở trường hợp thứ hai, điều này dẫn tới (cid:12) (cid:12)U p Trong cả hai trường hợp, giả thiết quy nạp kéo theo có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Do đó, các miền này có thể dựng được như mô tả ở trên. Cuối cùng, ta dựng miền (Ut−1VtUt), mỗi miền này có thể chứa tối đa hai đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng. (Như trên, nếu cần có thể thay Vt bởi V

n=1 Tn| = t − 1. Điều đó kéo theo việc có nhiều nhất 2.2 + (t − 2).1 = t + 2 đỉnh của 9-giác lồi có thể nằm trong hợp của các

Lưu ý rằng Ut /∈ Tt−1 vì ta đã giả sử | ∪t−1

(UlVlVl+1Ul+1)∪(Ut−1VtUt).

t−2 (cid:83) l=1

miền (U0V1U1) ∪

2.8.2 Các trường hợp (5, ≥ 2)

Thay các đỉnh này bởi các điểm nằm trên xích lồi U0V1V2...VtUt (độ dài là t + 2) sẽ tạo ra một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho.

Xét đường thẳng đi qua hai đỉnh liên tiếp của conv(J), giả sử là P và Q. Khi ấy conv(J) nằm trọn trong một nửa mặt phẳng có bờ là P Q. Gọi TP Q là tập tất cả các đỉnh của ngũ giác lồi conv(I) nằm trong nửa mặt phẳng bờ P Q và không chứa điểm nào của J. (Nửa mặt phẳng này là duy nhất nếu |J| > 2). Xét các khả năng có thể đối với giá trị |TP Q|. |TP Q| = 0: Trường hợp này không thể xảy ra vì I bao J. |TP Q| = 1: Ở trường hợp này, có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Đó là trường hợp t = 2 ở Quan sát 1. |TP Q| = 4: Ở trường hợp này, có thể dựng được một lục giác lồi rỗng bằng cách dùng xích lồi bốn đỉnh của ngũ giác lồi conv(I) kết hợp với P và Q.

Hình 2.23 Trường hợp (5, ≥ 2): Ví dụ với |TP Q ∪ TQR| ≥ 4.

Xét trường hợp

2 ≤ |TP Q| ≤ 3.

(8.1)

Gọi R là đỉnh tiếp theo sau P, Q trên bao lồi của J sau khi kẻ P Q ( nếu |J| = 2 thì R ≡ Q). Xác định tập TQR tương tự như trên (nếu |J| = 2 thì TQR là tập hợp số đỉnh của ngũ giác lồi conv(I) ở nửa mặt phẳng còn lại so với TP Q). Lập luận tương tự như trên, ta giả sử

2 ≤ |TQR| ≤ 3.

(8.2)

a) |TP Q ∪ TQR| ≥ 4.

và xét ba khả năng:

Trong trường hợp này ta có thể chọn các đỉnh liên tiếp A, B, C, D của ngũ giác

b) |TP Q ∪ TQR| = 3 (tức là TP Q và TQR có ít nhất một điểm chung).

lồi conv(I) sao cho A, B ∈ TP Q và C, D ∈ TQR. Kí hiệu đỉnh còn lại của ngũ giác lồi conv(I) là E. Dựng các miền (AP QB) và (CQRD), mỗi miền chỉ chứa tối đa một điểm của 9-giác lồi H mà không tạo ra một lục giác lồi rỗng. Tiếp theo ta dựng miền (BQC), miền này có thể chứa tối đa hai đỉnh của 9-giác lồi H mà không tạo ra một lục giác lồi rỗng. Tiếp tục dựng hai miền (DRE) và (EP A). Lưu ý rằng hợp của năm miền này phủ hoàn toàn diện tích bên ngoài conv(I) (Hình 23). Mỗi miền trong ba miền (BQC), (DRE), và (EP A) có thể chứa tối đa hai đỉnh của 9-giác lồi H mà không tạo ra một lục giác lồi rỗng. (Nếu cần có thể thay R và P bởi lần lượt R(cid:48) ∈ J ∩ (cid:52)DRE và P (cid:48) ∈ J ∩ (cid:52)EP A thích hợp đẻ tạo ra các miền mới là (DR(cid:48)E) và (EP (cid:48)A) sao cho các tam giác tương ứng là (cid:52)DR(cid:48)E và (cid:52)EP (cid:48)A không chứa bất kỳ điểm nào khác của J như chứng minh ở Quan sát 1). Điều này kéo theo có nhiều nhất 2.1 + 3.2 = 8 đỉnh của 9-giác lồi H có thể nằm xung quanh ngũ giác lồi conv(I) mà không tạo ra một lục giác lồi rỗng. Điều này mâu thuẫn với giả thiết H là đa giác lồi 9 đỉnh. Lưu ý trường hợp đặc biệt (5, 2) đã được chứng minh ở mục này.

Trường hợp này được giải quyết bằng cách tiếp cận tương tự như mục trước. Chọn ba đỉnh liên tiếp A, B, C của ngũ giác lồi conv(I) sao cho A, B ∈ TP Q và B, C ∈ TQR. Kí hiệu hai đỉnh còn lại của ngũ giác lồi là D và E sao cho các đỉnh C, D, E là liên tiếp. Dựng các miền (AP QB) và (BQRC). Tiếp theo dựng các miền (CRD), (DRE, (EP A). Nếu cần có thể thay thế R và P bởi các điểm nằm trong J ∩ (cid:52)CRD, J ∩ (cid:52)DRE, J ∩ (cid:52)EP A. Như trên, ta đi đến đánh giá rằng có nhiều nhất 2.1 + 3.2 = 8 đỉnh của 9-giác lồi H có thể nằm xung quanh ngũ giác lồi conv(I) mà không tạo ra một lục giác lồi rỗng.

c) |TP Q ∪ TQR| ≤ 2.

Trường hợp này dẫn đến các khả năng dựng được một 9-giác lồi H (cid:48) nằm trong

9-giác lồi H đã cho (tương ứng với t = 3 ở Quan sát 1).

2.9 Các trường hợp (6, ≥ 4)

Cách tiếp cận giống như ở mục 2.8. Ý tưởng chính là chia phần diện tích bên ngoài conv(I) thành ba miền tam giác và bốn miền tứ giác. Mỗi miền tam giác được xác định bởi hai đỉnh của conv(I) và một đỉnh của conv(J). Mỗi miền này có thể chứa tối đa hai đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng. Mỗi miền tứ giác được xác định bởi hai đỉnh của lục giác lồi conv(I) và hai đỉnh liên tiếp của conv(J). Mỗi miền này có thể chứa tối đa một đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng. Xét xích gồm các đỉnh liên tiếp của conv(J) là VWXY Z, trong đó V = Z nếu i = 4. Xác định các tập hợp TV W , TW X , TXY , TY Z như Mục 2.8 (có nghĩa TV W là tập hợp các đỉnh của lục giác lồi conv(I) nằm trong nửa mặt phẳng bờ V W và không chứa thêm bất kỳ điểm nào của J. Như trong Mục 2.8, ta giả sử

2 ≤ |TKL| ≤ 3((K, L) ∈ {(V, W ), (W, X), (X, Y ), (Y, Z)}).

(9.1)

Bằng cách cho t = 3, 4, 5 như trong Quan sát 1 (mục 8), ta cũng có thể giả sử

|TKL ∪ TLM | ≥ 3.

(9.2)

|TKL ∪ TLM ∪ TM N | ≥ 4.

(9.3)

|TV W ∪ TW X ∪ TXY ∪ TY Z| ≥ 5.

(9.4)

{(V, W, X, Y ), (W, X, Y, Z)} trong (9.3). Lưu ý rằng (9.4) cũng đúng cho trường hợp (6,4), mà Quan sát 1 không áp dụng được (vì t > j). Chú ý tiếp theo là bằng cách xây dựng, ta không thể có một điểm P ∈ TKL ∩ TM N với P /∈ TLM ((K, L, M, N ) ∈ {(V, W, X, Y ), (W, X, Y, Z)}). Bây giờ ta xây dựng cụ thể các miền tam giác và miền tứ giác. Một ví dụ cụ thể như trong Hình 24. Tổng hợp các trường hợp con được minh họa trong Hình 25.

với (K, L, M ) ∈ {(V, W, X), (W, X, Y ), (X, Y, Z)} trong (9.2) và (K, L, M, N ) ∈

2.9.1 TW X ∩ TXY (cid:54)= ∅

Hình 2.24 Các trường hợp (6, ≥ 4). Ví dụ với TW X ∩ TXY (cid:54)= ∅.

Kí hiệu các đỉnh liên tiếp của lục giác lồi conv(I) là A, B, C, D, E, F sao cho B ∈ TW X , C ∈ TW X ∩ TXY và D ∈ TXY . Lưu ý rằng F /∈ TW X và F /∈ TXY vì nếu không thì |TW X | > 3 hoặc |TXY | > 3. Xét các khả năng sau:

(1) A /∈ (TV W ∪ TWX ) (Hình 25a).

Từ (9.1) và (9.2) ta có B, C ∈ TXY và D ∈ TW X. (9.3) kéo theo E ∈ TXY . Dựng ba miền tứ giác là (BV W W C), (CW XD) và (DXY E). Tiếp theo dựng miền tam giác (AV B). (Nếu cần có thể thay V bởi một điểm thích hợp V (cid:48) ∈ J ∩ (cid:52)AV B). • Nếu E ∈ TY Z thì từ (9.4) suy ra E ∈ TY Z. Dựng miền tứ giác (EY ZF ) và miền tam giác (F ZA) (nếu cần có thể thay Z bởi Z(cid:48)). • Nếu E /∈ TY Z thì từ (9.1) suy ra A, E ∈ TY Z. (F /∈ TXY kéo theo F /∈ TXY \TY Z. Ở trường hợp này dựng miền tam giác (EY F ) cùng với miền tứ giác (F Y ZA). Ở cả hai trường hợp, ta xây dựng được một tập hợp gồm các miền tứ giác và miền tam giác.

Trong các trường hợp sau ta giả sử A ∈ (TV W ∪ TWX )

(2)E /∈ (TXY ∪ TY Z).

Trường hợp này đối xứng với trường hợp trên. Do vậy, trong trường hợp sau, ta giả thiết E ∈ (TXY ∪ TY Z)

(3)A ∈ TWX \TV W (Hình 25b).

Từ (9.1) suy ra E, F ∈ TV W. (F /∈ TWX kéo theo F /∈ TWX \TV W). Dựng các miền tam giác (F W A) và (BXC) cùng với các miền tứ giác (EV W F ), (AW XB) và (CXY D). Điều này kéo theo D ∈ TXZ vì nếu không thì |TY Z ∪ TV W| = |{E, F }| < 3. Lưu ý rằng (E ∈ TV W) ∧ (E ∈ (TXY ∪ TY Z)) kéo theo E ∈ TY Z. Do đó ta có thể dựng được miền tứ giác (DY ZE). Vậy là ta đã dựng được sáu miền như mong muốn.

Hình 2.25 Trường hợp (6, ≥ 4): Tổng hợp các trường hợp. Các hình (a)-(c) là trường hợp B ∈ TW X , C ∈ TW X ∪ TXY và D ∈ TXY . Hình (a) là trường hợp A /∈ TV W \TW X. Hình (b) là trường hợp A ∈ TWX \TV W và E ∈ (TXY ∪ TY Z). Hình (c) là Trường hợp A ∈ (TV W ) và E ∈ TY Z. Hình (d) là trường hợp A, B /∈ TV W \TW X và C, D ∈ TXY \TW X. Chỉ những vị trí của các điểm như trong hình vẽ là cần thiết

để dựng các miền như đã mô tả. Trong trường hợp sau ta giả sử A ∈ TV W

(4) E ∈ TXY \TY Z.

Trường hợp này đối xứng với trường hợp trên. Vậy nên ta giả sử E ∈ TY Z trong

trường hợp sau

(5) A ∈ TV W và E ∈ TY Z, xem Hình 25c.

• B ∈ TV W ∧ D ∈ TY Z. Dựng miền tứ giác (AV W B) và miền tam giác (F V A). (Nếu cần có thể thay V bởi V (cid:48)). Tương tự dựng miền tứ giác (DY ZE) cùng với miền tam giác (EZF ) (Thay Z bởi Z(cid:48) nếu cần). • B /∈ TV W ∧ D ∈ TY Z. Dựng miền (DY ZE) cùng với miền (EZF ) như trường hợp trước. Nếu B /∈ TV W thì từ (9.1) ta có F ∈ TV W . Trong trường hợp này, dựng miền tam giác (AW B) cùng với miền tứ giác (F V W A). • B ∈ TV W ∧ D /∈ TY Z. Trường hợp này đối xứng với trường hợp trên. • B /∈ TV W ∧ D /∈ TY Z. Điều này kéo theo F ∈ TV W và F ∈ TY Z. Tương tự dựng các miền (F V W A) với (EY ZF ) và các miền (AW B) và (DY E). Trong mỗi trường hợp ta đều tạo ra một tập lợp gồm bốn miền tứ giác và hai miền tam giác, các miền này phủ hoàn toàn diện tích bên ngoài conv(I) như đã chỉ ra.

2.9.2 TW X ∩ TXY = ∅

Dựng miền tứ giác (BW XC) và (CXY D). Xét bốn khả năng sau:

Xem Hình 25d. Bằng cách dựng, ta thấy tồn tại các đỉnh liên tiếp của conv(I) là A, B, C, D sao cho A, B ∈ TW X \TXY và C, D ∈ TXY \TW X . Dựng các miền tứ giác (AW XB), (CXY D) và miền tam giác (BXC). Kí hiệu các đỉnh còn lại của lục giác lồi conv(I) là E và F sao cho D, E, F là các đỉnh liên tiếp. Bây giờ ta xét bốn khả năng: • D ∈ TY Z ∧ A ∈ TV W . Ta suy ra E ∈ TY Z vì nếu không thì |TXY ∪ TY Z| < 3 . Tương tự F ∈ TV W vì nếu không thì |TV W ∪ TW X | < 3 . Dựng các miền (DY ZE) và (F V W A) cùng với miền (EZF ). (Thay Z bởi Z(cid:48) nếu cần). • D /∈ TY Z ∧ A ∈ TV W . Như trường hợp trên, dựng miền (F V W A). Nếu E ∈ TXY \ T Y Z thì ta có |TY Z ∪ TV W ∪ TW X | = |A, B, F | < 4. Do vậy giả sử E ∈ TY Z. Khi đó ta có F ∈ TY Z vì ngược lại thì |TY Z| < 2. Dựng các miền (DY E) và (EY ZF ). • D ∈ TY Z ∧ A /∈ TV W . Trường hợp này đối xứng với trường hợp hợp trên.

• D /∈ TY Z∧A /∈ TV W Lưu ý rằng trường hợp này là vô lý vì nó kéo theo |TY Z ∪TV W | = |{E, F }| < 3. Trong mỗi trường hợp đã xét, ta có thể dựng được sáu miền như đã khẳng định ở trên.

2.10 Các trường hợp (≥ 7, ≥ 5, ≥ 1)

Bảng 3 Các trường hợp (≥ 7, ≥ 5, ≥ 1): Tổng hợp các trường hợp con. (Π biểu thị các hoán vị có thể)

Như vậy, ta đã giải quyết tất cả các trường hợp ngoại trừ trường hợp (≥ 7, ≥ 5, ≥ 1). Những trường hợp này, không kể ba trường hợp đặc biệt phía dưới, đều có thể giải quyết được tất cả thông qua cách lập luận tương tự các phần trên. Đặt K := conv(J) ∩ (X\∂J). Cố định một điểm P ∈ K. Xét các tia xuất phát từ P qua mỗi đỉnh của đa giác lồi j-cạnh conv(J). Cách làm này chia phần diện tích bên ngoài conv(J) thành j miền và trong mỗi miền có thể chứa tối đa hai đỉnh của conv(I) mà không tạo ra một lục giác lồi rỗng. (Để rõ hơn điều này, dựng miền

2.10.1 Quy tắc 1

tam giác và thay P bởi P (cid:48) phù hợp nếu cần). Xét tất cả các khả năng phân bố đỉnh (được tổng kết trong Bảng 3). Ta muốn chia diện tích bên ngoài đa giác lồi i cạnh conv(I) thành các miền và chỉ ra rằng trong mỗi trường hợp, nhiều nhất tám đỉnh của 8-giác lồi có thể nằm trong hợp của các miền này mà không taọ ra một lục giác lồi rỗng. Ba quy tắc đơn giản sau là đủ để chứng minh điều này:

Quy tắc 1 giải quyết trường hợp khi hai đỉnh của conv(I) nằm trong cùng một

miền.

Hình 2.26 Quy tắc 1

Quy tắc 1 Gọi A1, A2 là hai đỉnh liên tiếp của conv(I) nằm trong cùng một miền (aP b), trong đó a và b là hai đỉnh liên tiếp của conv(J). Khi đó không đỉnh nào của 9-giác lồi có thể nằm trong miền (A1abA2) mà không tạo ra một lục giác lồi rỗng.

Chứng minh Từ sự tồn tại của ngũ giác lồi rỗng A1aP (cid:48)bA2, trong đó P (cid:48) ∈ J∩(cid:52)aP b được chọn một cách thích hợp (Hình 26).Suy ra, nếu có một điểm Q là đỉnh của 9-giác lồi H nằm trong miền ngũ giác (A1aP (cid:48)bA2) thì QA1aP (cid:48)bA2 là một lục giác lồi rỗng.

2.10.2 Quy tắc 2

Hình 2.27 Quy tắc 2

Quy tắc 2 cho ta đánh giá cận trên về số đỉnh của 9-giác lồi có thể nằm giữa hai miền không rỗng.

Quy tắc 2 Gọi A1, A2 là hai đỉnh liên tiếp của conv(I) nằm trong các miền phân biệt (a1P b1) và (a2P b2), trong đó a1, b1 và a2, b2 lần lượt là các đỉnh liên tiếp của conv(J). Giả sử a1, b1, a2, b2 thuộc xích lồi gồm các đỉnh liên tiếp của conv(J). Đặt S := (A1b1a2A2) nếu A1b1a2A2 là một tứ giác lồi và S := (A1b1A2) ∪ (A1a2A2) trong trường hợp tứ giác A1b1a2A2 không lồi. Khi đó, có nhiều nhất hai đỉnh của 9-giác lồi có thể nằm trong S.

Chú ý Trong Quy tắc 2, có thể b1 = a2.

2.10.3 Ứng dụng của Quy tắc 1 và 2

Chứng minh Một miền tam giác không chứa bất kỳ điểm nào của J và phủ kín miền S có thể dựng được bằng cách chọn A1, A2 và một điểm thích hợp ar từ các đỉnh liên tiếp của conv(J) nằm giữa b1 và a2 (tính cả b1 và a2). Vì miền này luôn "chứa" miền S (theo cách xây dựng) nên suy ra rằng miền S chỉ có thể chứa tối đa hai đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng (Hình 27).

Hai quy tắc 1 và 2 là đủ để giải quyết các trường hợp (7, 5, ≥ 1) với sự phân bố Π(2, 2, 2, 1, 0), (7, 6, ≥ 1) với phân bố Π(2, 2, 2, 1, 0, 0), (7, 7, ≥ 1) với phân bố Π(2, 2, 2, 1, 0, 0, 0), (7, 8, ≥ 1) với phân bố Π(2, 2, 2, 1, 0, 0, 0, 0), (8, 5, ≥ 1) với phân bố Π(2, 2, 2, 2, 0), (8, 6, ≥ 1) với phân bố Π(2, 2, 2, 2, 0, 0), (8, 7, ≥ 1) với phân bố

Π(2, 2, 2, 2, 0, 0, 0), (8, 8, ≥ 1) với phân bố Π(2, 2, 2, 2, 0, 0, 0, 0). Để rõ hơn, áp dụng Quy tắc 1 vào hai đỉnh bất kỳ của conv(I) nằm trong cùng một miền. Lưu ý rằng hai đỉnh như vậy ứng với một số "2" trong cách phân bố như trên. Với các đỉnh liên tiếp của conv(I) nằm trong các miền phân biệt, áp dụng Quy tắc 2. Lưu ý rằng trong các trường hợp này, Quy tắc 2 cần áp dụng chính xác là 4 lần vì luôn có đúng 4 vị trí khác không trong cách phân bố ở trên. Điều này dẫn tới tối đa 4.2=8 đỉnh của 9-giác lồi H có thể được xếp vào mà không tạo ra lục giác lồi rỗng. Một ví dụ được chỉ ra trong Hình 28.

(2, 0, 2, 1, 0, 2)

Hình 2.28 Áp dụng Quy tắc 1 và 2 cho trường hợp (7, 6, ≥ 1) với sự phân bố

2.10.4 Quy tắc 3

Hình 2.29 Quy tắc 3

Quy tắc 3 giải quyết các trường hợp với một dãy các miền mà trong mỗi miền

chứa nhiều nhất một đỉnh của conv(I), xem Hình 29.

Hình 2.30 Chứng minh Quy tắc 3 với n = 1

Quy tắc 3 Cho 1 ≤ n ≤ i − 2. Xét dãy A0, A1, ..., An+1 là các đỉnh liên tiếp của conv(I). Với 1 ≤ l ≤ n + 1, lấy Al ∈ (alP bl), trong đó al và bl là các đỉnh liên tiếp

của conv(J) . Giả sử với 1 ≤ l ≤ n, mỗi miền (alP bl) chứa đúng một đỉnh của conv(I) và a1, b1, a2, b2, ..., an+1, bn+1 là các đỉnh liên tiếp của một xích lồi trích ra từ conv(J). Khi đó, nhiều nhất n + 2 đỉnh của 9-giác lồi nằm trong hợp của các miền ∪n+1 l=1 (Al−1alAl).

Chú ý Trong Quy tắc 3, có thể bl = al+1(1 ≤ l ≤ n) hoặc bn+1 = a1. Hơn nữa,

2A2) mà không có điểm nào của J nằm trong (cid:52)A1a(cid:48)

2A2) và ta có thể chọn a(cid:48)

l=2 (Al−1alAl) mà không tạo ra một lục giác lồi rỗng.

có thể A0 và A1 cùng nằm trong miền (an+1P bn+1). Chứng minh Ta chứng minh quy nạp theo n.

Nếu n = 1, ta lập luận rằng A1 không thể nằm bên trên đường a1b1 trong khi A0 và A2 nằm bên dưới a1b1 ("nằm bên dưới" nghĩa là nằm trong nửa mặt phẳng bờ a1b1 và chứa P ). Vì nếu ngược lại, |Ta1b1| = 1 và có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho (trường hợp t = 2 trong Quan sát 1 ở Mục 8). Giả sử A0 cũng nằm bên trên a1b1 (trường hợp A1 và A2 cùng nằm bên trên a1b1 là tương tự). Dựng miền tứ giác (A0a1b1A1) với miền tam giác (A1a2A2). Nếu cần, thay a2 bởi một điểm thích hợp a2 ∈ (cid:52)A1a2A2 đẻ tạo ra miền tam giác mới (A1a(cid:48) 2A2. Các miền này phủ diện tích của (A0a1A1) ∪ (A1a2A2). Với các điểm nằm trong (A1a2A2) thì điều này là rõ ràng vì (A1a2A2) phủ phần diện tích này. Lưu ý rằng, không thể có điểm Q ∈ ((A0a1A1) \ (A1a(cid:48) 2A2)) \ (A0a1b1A1). Điểm như vậy phải nằm trên phần diện tích bị bôi đen trong Hình 30. Nếu a2 nằm bên phải của b1A1 (hoặc a2 = b1) thì Q ∈ (A1a(cid:48) 2 := b1. Các miền tứ giác và tam giác cho phép nhiều nhất 1+2=3 đỉnh của 9-giác lồi nằm trong mà không tạo ra một lục giác lồi rỗng. Bước quy nạp tiếp theo, giả sử yêu cầu bài toán đúng cho 1, 2, ..., n − 1. Qua giả thiết quy nạp, ta thấy có nhiều nhất (n − 1) + 2 đỉnh của 9-giác lồi có thể nằm trong hợp của các miền ∪n l=1(Al−1alAl). Nhiều nhất hai đỉnh nữa của 9-giác lồi H có thể nằm trong miền (AnanAn+1)\ ∪n l=1 (Al−1alAl) mà không tạo ra một lục giác lồi rỗng. Do đó, số đỉnh của 9-giác lồi có thể nằm trong hợp của các miền ∪n+1 l=1 (Al−1alAl) nhiều nhất là (n − 1 + 2) + 2 = n + 3 mà không tạo ra một lục giác lồi rỗng. Cũng từ giả thiết quy nạp, có nhiều nhất (n − 1) + 2 đỉnh của 9-giác lồi H có thể nằm trong hợp của các miền ∪n+1 Tương tự, nhiều nhất hai đỉnh nữa của 9-giác lồi có thể nằm trong miền (A0a1A1)\∪n+1 l=2 (Al−1alAl) mà không tạo ra một lục giác lồi rỗng. Do đó, cận trên là chính xác nếu và chỉ nếu có đúng hai đỉnh của 9-giác lồi lần lượt nằm trong các miền (A0a1A1) và (Anan+1An+1). Ta cũng suy ra A0 phải nằm phía dưới đường a1b1 và An+1 phải nằm phía dưới đường anbn vì nếu không thì các miền (A0a1A1) và (Anan+1An+1) có thể thay bởi

(cid:12)∪n

2.10.5 Ứng dụng các Quy tắc 1-3

lần lượt các miền (A0a1b1A1) và (AnanbnAn+1) như trên. Miền này chỉ có thể chứa một đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng và hợp của các của các miền này vẫn phủ phần diện tích tương tự. (cid:12) Điều này dẫn tới (cid:12) (cid:12) = n < n + 1 mặc dù có thể dựng được một 9-giác l=1Talbl lồi H (cid:48) nằm trong 9-giác lồi H đã cho theo Quan sát 1. Để thấy được, lưu ý rằng a1, b1, a2, b2, ..., an, bn là các đỉnh liên tiếp của một xích lồi trích ra từ conv(J) với độ dài L > n + 1. Từ đó ta có điều phải chứng minh.

Dựa trên ba Quy tắc ta có thể giải quyết tất cả các trường hợp còn lại của (≥ 7, ≥ 5, ≥ 1) ngoại trừ (7, 7, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1), (7, 8, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1, 0), (8, 8, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1, 1) (Những trường hợp này không cho phép áp dụng trực tiếp Quy tắc 3. Ta giải quyết các trường hợp này riêng ở những mục sau). Với những trường hợp còn lại, ít nhất một số 2 sẽ xuất hiện trong phân bố. Ta có thể lập luận như sau: Với hai đỉnh liên tiếp bất kỳ của conv(I) nằm trong cùng một miền, áp dụng Quy tắc 1. Lưu ý rằng hai điểm như vậy tương ứng với số 2 trong phân bố trên. Không có đỉnh nào của 9-giác lồi có thể nằm trong các miền như vậy. Bây giờ ta chọn dãy các miền liên tiếp lớn nhất chứa tối đa một đỉnh của conv(I) trong mỗi miền và áp dụng Quy tắc 3 (tương ứng chọn Quy tắc 2 nếu không có miền nào trong các miền đó chứa một đỉnh). Số đỉnh của 9-giác lồi có thể nằm trong hợp của các miền tương ứng bằng q + s.2, trong đó q là tổng của số các số 1 xuất hiện trong phân bố ở trên và s là số các chuỗi phân biệt. Nhận xét rằng, s bằng số các khoảng trống giữa hai lần xuất hiện số 2 trong phân bố. Số này chính bằng số các số 2 trong phân bố, suy ra q + s.2 là tổng của các phần tử trong dãy phân bố. Dễ dàng kiểm tra đươc rằng tổng này luôn nhỏ hơn 9. Do đó, trong các trường hợp này thì đều dựng được một lục giác lồi rỗng (ví dụ minh họa trong Hình 31).

2.10.6 Trường hợp (1, 1, 1, 1, 1, 1, 1)

Hình 2.31 Trường hợp (8, 8, ≥ 1) với sự phân bố (2, 1, 1, 1, 0, 2, 0, 1)

2.10.7 Trường hợp (1, 1, 1, 1, 1, 1, 1, 0)

Trường hợp này được giải quyết bằng cách áp dụng Quy tắc 3 với n = 5 bảy lần với mỗi đỉnh của conv(I) như là điểm xuất phát. Mỗi miền (Ar−1arAr) bị loại ra đúng một lần. Do vậy, trong hợp của tất cả các miền có nhiều nhất (7.(5+2))/6<9 đỉnh của 9-giác lồi có thể nằm trong mà không tạo ra một lục giác lồi rỗng.

Với trường hợp (1, 1, 1, 1, 1, 1, 1, 0), kí hiệu các đỉnh của conv(J) theo chiều kim đồng hồ thứ tự là al(1 ≤ l ≤ 8) và giả sử miền (a6P a7) là miền không chứa điểm nào của conv(I). Áp dụng Quy tắc 3 với n = 5, ta có thể kết luận có nhiều nhất 5+2=7 đỉnh của 9-giác lồi có thể nằm trong hợp của các miền ∪6 l=1(Al−1alAl), xem Hình 32.

Hình 2.32 Trường hợp (7, 8, ≥ 1) với sự phân bố (1, 1, 1, 1, 1, 1, 1, 0)

Xét A6, lưu ý rằng A6 không thể nằm dưới đường a1a8 và phía dưới đường a6a7 được vì nếu ngược lại thì tồn tại một 9-giác lồi H (cid:48) := a8a1a2...a7a6 nằm trong 9-giác lồi H đã cho. Nếu A6 nằm bên trên đường a1a8 , chỉ có một đỉnh của 9-giác lồi có thể nằm trong miền tứ giác (A6a8a1A0) (vì khi đó miền này tồn tại) và do đó, có nhiều nhất tám đỉnh của 9-giác lồi có thể nằm trong hợp của các miền ∪6 l=1(Al−1alAl) ∪ (A6a8a1A0) mà không taọ ra một lục giác lồi rỗng, theo cách dựng thì miền này phủ hoàn toàn diện tích bên ngoài conv(I). Tương tự, nếu A0 nằm bên trên đường a6a7 (cũng là A6 theo cách dựng) thì nhiều nhất tám đỉnh của 9-giác lồi có thể nằm trong hợp của các miền ∪6 l=1(Al−1alAl) ∪ (A6a6a7A0) (theo cách dựng, miền này che phủ hoàn toàn diện tích bên ngoài conv(I)) mà không tạo ra một lục giác lồi rỗng. Cuối cùng, nếu A0 nằm phía dưới a6a7 và A6 nằm bên trên a6a7 ta thấy rằng A5 nhất định phải nằm bên trên đường a6a7 vì nếu ngược lại thì |Ta6a7| < 2 và có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho theo Quan sát 1. Do đó, miền (A5a6a7A6) tồn tại, miền này chỉ có thể chứa nhiều nhất một đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng. Bây giờ, áp dụng Quy tắc 3 với n = 5, ta suy ra có nhiều nhất 7 đỉnh của 9-giác lồi H có thể nằm trong hợp của các miền ∪5 l=1(Al−1alAl) ∪ (A6a8A0) mà không tạo ra một lục giác lồi rỗng. Do đó, nhiều nhất tám đỉnh của 9-giác lồi có thể nằm trong hợp của các miền ∪5 l=1(Al−1alAl) ∪ (A6a8A0) ∪ (A5a6a7A6) (theo cách dựng thì miền này che phủ hoàn toàn diện tích bên ngoài conv(I)) mà không tạo ra một lục giác lồi rỗng.

2.10.8 Trường hợp (1, 1, 1, 1, 1, 1, 1, 1)

Lưu ý rằng trong trường hợp (1, 1, 1, 1, 1, 1, 1, 1), ta áp dụng lập luận quy nạp với n = 6 tám lần với mỗi đỉnh của conv(I) như là một điểm xuất phát (tương tự trường hợp (7, 7, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1) ở Mục 10.6) chỉ mang lại cho ta ước lượng (8.(6+2))/7>9 đỉnh của 9-giác lồi có thể nằm trong hợp của tất cả các miền. Do đó, đòi hỏi cách tiếp cận khác cho trường hợp này được đặt ra. Kí hiệu các đỉnh của conv(J) theo chiều kim đồng hồ thứ tự là ar(1 ≤ r ≤ 8). Xét bốn đỉnh liên tiếp của 8-giác lồi conv(J) là as, at, au, av. Lưu ý rằng không có điểm nào của conv(I) có thể nằm phía dưới đường asat và phía dưới đường auav ("phía dưới" được hiểu là nằm trong nửa mặt phẳng chứa P ) vì nếu ngược lại thì ta có thể sử dụng điểm đó để dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Kí hiệu Rt là miền nằm phía trên hai đường asat và atau, xem Hình 33. Hợp của tất cả các miền Rr(1 ≤ r ≤ 8) xác định một miền cho các đỉnh của conv(I). Kí hiệu các đỉnh của conv(I) là Am (Am ∈ (amP am+1)), 1 ≤ r ≤ 8, a9 := a1). Lưu ý rằng Am nằm trong Rm hoặc Rm+1 (hoặc cả hai) (1 ≤ r ≤ 8, R9 := R1). Xét ba khả năng sau:

TH1: Tồn tại miền Rw mà không có Am nào nằm trong nó

Hình 2.33 Trường hợp (8, 8, ≥ 1) với sự phân bố (1, 1, 1, 1, 1, 1, 1, 1) :Xác định Rt

Có nhiều nhất một miền như vậy vì nếu ngược lại thì ta có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Để rõ hơn điều này, loại bỏ tiếp các khả năng của Rz tiếp theo bởi tính chất này là Rw+1, Rw+2, Rw+3 hoặc Rw+4. Trong

n=1 Tanan+1

(cid:83)l−1 (cid:12) (cid:12) (cid:12)

trường hợp dầu tiên, ta có |Tawaw+1| < 2 và trong ba trường hợp còn lại ta có thể thay một trong ba đỉnh của 8-giác lồi a1a2...a8 bởi hai trong bốn điểm Am để dựng một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Gọi a1 là điểm liên kết với miền không chứa bất kỳ điểm nào của Am. Vì sự tồn tại của một miền như vậy là độc lập với cách chọn điểm P nằm trong ngũ giác a6a2a3a4a5. Điểm P như vậy chắc chắn tồn tại vì nếu không thì có thể dựng được một lục giác lồi rỗng, xem Hình 34. (một cách chọn điểm P khác có thể giải quyết một cách phân bố khác. Với trường hợp này thì ta chọn điểm P như trên). Kết quả, có nhiều nhất ba đỉnh của 9-giác lồi có thể nằm trong miền (A6a6P a2A1) vì nếu không thì có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. (vì 5+4=9) Ta cần chứng minh Am ∈ Rm ∩ Rm+1 với 2 ≤ m ≤ 7, có nghĩa là mỗi Am nằm ở bên trên cả hai đường am−1am và am+1am+2(2 ≤ m ≤ 7, a9 := a1) . Để rõ hơn, ta bắt đầu từ đường a1a2 và tiến hành theo chiều kim đồng hồ để chứng minh rằng Am nằm trên (cid:12) (cid:12) am−1am ( 2 ≤ m ≤ 7). Lưu ý đến các cấu hình, trong đó (cid:12) < l(2 ≤ l ≤ 8) suy ra có thể dựng được một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho theo Quan sát 1 Mục 8. Bây giờ bắt đầu từ đường a1a8 và tiến hành theo chiều kim đồng hồ để chứng minh Am nằm bên trên đường am+1am+2(2 ≤ m ≤ 7, a9 := a1). Cuối cùng, như ta giả sử rằng không có Ar nào nằm trong R1, nó kéo theo A1 ∈ R2 và A8 ∈ R8. Do đó, trường hợp này có thể giải quyết như minh hoa trong hình 34.

Hình 2.34 Trường hợp (8, 8, ≥ 1) với sự phân bố (1, 1, 1, 1, 1, 1, 1, 1): R1 không

TH2: Ít nhất một Am nằm trong mỗi miền Rr(1 ≤ r ≤ 8) và đặt A1 ∈ R1\R2

chứa Am nào.

Ta phải chứng minh rằng điều này dẫn đến Au ∈ Ru(3 ≤ u ≤ 8) vì nếu ngược lại thì xuất hiện một 9-giác lồi H (cid:48) nằm trong 9-giác lồi H đã cho. Để rõ hơn, đầu tiên ta xét điểm A8, nếu A8 ∈ R1 \ R8 thì 9-giác lồi H (cid:48) := A1a2a3...a8A8 nằm trong 9-giác lồi H đã cho xuất hiện. Do đó, A8 ∈ R8. Tiếp theo xét đến A7, rồi A6 và cứ tiếp tục như vậy. Cuối cùng, như ta đã giả giả thiết rằng có ít nhất một điểm Am nằm trong mỗi miền Rr(1 ≤ r ≤ 8), nó kéo theo A2 ∈ R2, xem hình 35. Trong trường hợp này, miền bên ngoài conv(I) có thể chia thành 8 miền tứ giác (Alalal+1Al+1) (1 ≤ l ≤ 8, a9 := a1, A9 := A1) và hợp của các miền này chỉ chứa tối đa tám đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng.

TH3: Mỗi Am nằm trong cả Rm và Rm+1.

Một lần nữa, miền bên ngoài của conv(I) có thể chia thành tám miền tứ giác (Alalal+1Al+1) (1 ≤ l ≤ 8, a9 := a1, A9 := A1) và hợp của các miền này chỉ chứa tối đa tám đỉnh của 9-giác lồi mà không tạo ra một lục giác lồi rỗng.

Hình 2.35 Trường hợp (8, 8, ≥ 1) với sự phân bố (1, 1, 1, 1, 1, 1, 1, 1): A1 ∈ R1 \ R2

Kết luận

Chương 1 của Luận văn đã trình bày tổng quan về bài toán Erd˝os-Szekeres về đa giác lồi và bài toán Erd˝os về đa giác lồi rỗng. Chương 2 của Luận văn trình bày chứng minh bài toán Erd˝os cho lục giác lồi rỗng, dựa theo chứng minh trong bài báo của Gerken. Từ đây, như là một hệ quả, ta suy ra:

Số điểm cần thiết ở vị trí tổng quát mà từ đó có thể tìm được sáu điểm là đỉnh

30 ≤ E(6) ≤ 1717.

tạo thành lục giác lồi rỗng phải thỏa mãn bất đẳng thức

Gần đây, sử dụng cách chứng minh tương tự của Gerken, Koselev cũng đã chứng

30 ≤ E(6) ≤ 463.

minh một bất đẳng thức tốt hơn

Chứng minh của Gerken và Koselev là rất tỉ mỉ, công phu và nó có thể được sử dụng để nghiên cứu tiếp theo giả thuyết Erd˝os bài toán lục giác lồi rỗng.

Tài liệu tham khảo

[1] Đoàn Hữu Dũng, Lời giải của bài toán Ecđôtsơ trong một trường hợp đặc biệt (với lời nhận xét của Hoàng Chúng), Tạp chí Toán học và Tuỏi trẻ, số 33, tháng 6, 1967, trang 14-16.

[2] Đoàn Hữu Dũng, Tạ Duy Phượng, Nguyễn Tiến Thịnh, Bài toán Erd˝os về đa

giác lồi (Bản thảo), 150 trang.

[3] Bonnice W. E., On convex polygons determined by a finite planar set, Amer.

Math. Monthly 81 (1974), 749-752.

[4] Knut Dehnhardt, Heiko Harborth, and Zsolt Lángi, A partial proof of the Erd˝os-Szekeres conjecture for hexagons, Journal of Pure and Applied Mathe- matics: Advances and Applications,Volume 2 Number 1 (2009), 69-86.

[5] Paul Erd˝os, Some more problems on elementary geometry, Austral. Math. Soc.

Gaz. 5 (1978), 52-54.

[6] P. Erd˝os and G. Szekeres, A combinatorial problem in geometry, Composi-

tioMath. 2, 463 (1935).

[7] T. Gerken, On empty convex hexagons in planar point set, Discrete Comput.

Geom., 39 (2008), 239-272.

[8] H. Harborth, Konvexe Funfecke in ebenen Punktmengen, Elem. Math., 33

(1978), 116-118.

[9] J. D. Horton, Sets with no empty 7-gons, Canad. Math. Bull., 26 (1983), 482-

484.

[10] Kalbfleisch J.D., Kalbfleisch J.G., Stanton R.G., A combinatorial problem on convex regions, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La, 1970. Congr. Numer. 1 (1970), 180-188.

[11] V. A. Koshelev, On Erd˝os-Szekeres problem for empty hexagons in the plane, Modeling and analysis of information systems, 16 (2009), 22-74 On Russian.

[12] Wanter D. Morris and Valeru Soltan, The Erd˝os-Szekeres problem on points in convex position - A survey, Bulletin of the American Mathematical Society (N. S.), 37(4):437–458, 2000.

[13] M. Overmars, Finding sets of points without empty convex 6-gons, Discrete

Comput. Geom., 29 (2003), 153-158.

[14] M. Overmars, B. Scholten, I. Vincent, Sets without empty convex 6-gons, Bull.

European Assoc. Theor. Comput. Sci., 37 (1989), 160-168.

[15] G. Szekeres, L. Peters, Computer solution to the 17-point Erdos-Szekeres prob-

lem, ANZIAM J., 48 (2006), 151-164.

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

VỀ LỤC GIÁC LỒI RỖNG

Mục lục

Mở đầu

Chương 1

TỔNG QUAN VỀ BÀI TOÁN ERD ¨OS VỀ ĐA GIÁC LỒI RỖNG

1.1 Bài toán 1

1.2 Bài toán 2

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 )

1.4 Bài toán 4

Chương 2

CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ

2.1 Định lý E(6) ≤ ES(9)

2.2 Lược đồ chứng minh

2.3 Các trường hợp đơn giản

2.4 Các trường hợp (3, ≥ 0) và (≥ 6, 3)

2.5 Các trường hợp (4, ≥ 0) và (≥ 7, 4)

2.6 Các trường hợp (5, 0) và (≥ 7, 5, 0)

2.7 Các trường hợp riêng

2.8 Các trường hợp (5, ≥ 2)

2.9 Các trường hợp (6, ≥ 4)

2.10 Các trường hợp (≥ 7, ≥ 5, ≥ 1)

Kết luận

Tài liệu tham khảo

Có thể bạn quan tâm

Luận văn Thạc sĩ: Chế tạo và nghiên cứu tính chất điện, từ của vật liệu multiferroic Ba₀.₇Ca₀.₃TiO₃/ NiFe₂O₄

Luận văn Thạc sĩ: Nghiên cứu vật liệu biến hóa dạng chuỗi một chiều chế tạo từ kim loại đồng trên đế FR-4 hoạt động tại tần số MHz ứng dụng trong truyền năng lượng không dây

Luận văn Thạc sĩ: Đánh giá khả năng tác động tới môi trường biển của việc xả nước thải từ sự cố nhà máy điện hạt nhân Fukushima sử dụng công cụ ERICA

Luận văn Thạc sĩ: Xây dựng mô hình đầu dò nơtron và gamma sử dụng nhấp nháy EJ-276 ghép nối với mảng nhân quang silicon

Luận văn Thạc sĩ: Đánh giá khả năng ảnh hưởng của bức xạ ion hóa đến sức khỏe cư dân khu vực mỏ đất hiếm Đông Pao, xã Bản Hon, huyện Tam Đường, tỉnh Lai Châu

Luận văn Thạc sĩ: Sử dụng phương pháp nhiễu xạ neutron khảo sát cấu trúc tinh thể và pha trật tự từ trong vật liệu Pr2FeCrO6

Luận văn Thạc sĩ: Nghiên cứu phân lập, xác định cấu trúc và hoạt tính ức chế NO của các hợp chất thứ cấp từ chủng vi nấm biển Aspergillus sp. CL251

Luận văn Thạc sĩ: Phân tích một số hợp chất bisphenol thôi nhiễm từ bao bì nhựa lên một số mẫu thực phẩm nền tinh bột

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá hoạt tính kháng khuẩn, kháng nấm của loài hoa mộc (Osmanthus fragrans (Thunb.) Lour.) ở Việt Nam

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá tác dụng kháng viêm của loài côi Turpinia montana (Blume) Kurz

Luận văn Thạc sĩ: Tổng hợp và đặc trưng tính chất vật liệu composite có cấu trúc nano chitosan–cyclodextrin/TiO₂–Ag

Luận văn Thạc sĩ: Nghiên cứu chế tạo và khảo sát một số tính chất của màng phủ trên cơ sở nhựa epoxy gốc nước và khung cơ kim - ZIF

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất napthoquinone chứa nguyên tố flo bằng phản ứng đa thành phần

Luận văn Thạc sĩ: Nghiên cứu điều chế vật liệu Bioglass và tổ hợp lai với polymer ALG-F127 định hướng ứng dụng trong điều trị nội nha

Luận văn Thạc sĩ: Khảo sát thành phần hóa học và hoạt tính ức chế enzyme α-glucosidase trên một số hợp chất phân lập từ thịt quả bình bát nước (Annona glabra L.).

Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất của benzazole

Luận văn Thạc sĩ: Nghiên cứu chiết tách lignin từ vỏ sầu riêng Ri6 (Durio zibethinus Murr.) và tổng hợp vật liệu biocomposite định hướng ứng dụng trong bảo quản sau thu hoạch

Luận văn Thạc sĩ: Nghiên cứu tổng hợp hạt nano bạc phủ acid hyaluronic mang doxorubicin định hướng ứng dụng trong điều trị ung thư

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và hoạt tính kháng viêm của loài rau dừa nước (Ludwigia adscendens)

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP