Tài liệu Về sự tồn tại lục giác lồi rỗng trong bài toán erdós

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HẰNG VỀ SỰ TỒN TẠI LỤC GIÁC LỒI RỖNG TRONG BÀI TOÁN ERDŐS LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN-2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HẰNG VỀ SỰ TỒN TẠI LỤC GIÁC LỒI RỖNG TRONG BÀI TOÁN ERDŐS Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60 46 01 13 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học PGS.TS. TẠ DUY PHƯỢNG THÁI NGUYÊN-2015 Mục lục Mở đầu iii 1 Tổng quan bài toán Erdős về đa giác lồi 1.1 Giới thiệu và xây dựng kết quả chính . 1.2 Phương pháp chứng minh . . . . . . . . 1.3 Định nghĩa và kí hiệu . . . . . . . . . . 1.3.1 Định nghĩa . . . . . . . . . . . . 1.3.2 Vị trí . . . . . . . . . . . . . . . rỗng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Chứng minh công thức đánh giá E(6) ≤ 463 2.1 Trường hợp đơn giản . . . . . . . . . . . . . . . . . . . . 2.2 Trường hợp với j = 0 (1 ≤ i ≤ 5) . . . . . . . . . . . . . 2.2.1 Cấu hình dạng (8,1,0) . . . . . . . . . . . . . . . 2.2.2 Cấu hình dạng (8,2,0) . . . . . . . . . . . . . . . . 2.2.3 Cấu hình dạng (8,3,0) . . . . . . . . . . . . . . . . 2.2.4 Cấu hình dạng (8,4,0) . . . . . . . . . . . . . . . . 2.2.5 Cấu hình dạng (8,5,0) . . . . . . . . . . . . . . . . 2.3 Trường hợp với một điểm ở trong . . . . . . . . . . . . . 2.3.1 Cấu hình dạng (8,3,1) . . . . . . . . . . . . . . . . 2.3.2 Cấu hình dạng (8,4,1) . . . . . . . . . . . . . . . . 2.3.3 Cấu hình dạng (8,7,1) . . . . . . . . . . . . . . . . 2.4 Các trường hợp, trong đó sử dụng tính chất tối thiểu của bát giác . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Cấu hình dạng (8,3, ≥ 2) . . . . . . . . . . . . . . 2.4.2 Cấu hình dạng (8,4, ≥ 2) . . . . . . . . . . . . . . 2.4.3 Cấu hình dạng (8,5, ≥ 3) . . . . . . . . . . . . . . 2.4.4 Cấu hình dạng (8,6,5) . . . . . . . . . . . . . . . . 2.5 Các trường hợp áp dụng tính cực tiểu của bát giác . . . . 2.5.1 Cấu hình dạng (8,6,4) . . . . . . . . . . . . . . . . i . . . . . 1 1 3 6 7 9 . . . . . . . . . . . 14 14 14 15 15 16 17 18 18 19 19 20 . . . . . . . 21 22 23 24 26 27 28 2.6 2.7 2.5.2 Cấu hình dạng (8,5,2) . . . . . . . . . . . . . . 2.5.3 Cấu hình dạng (8,7,5) . . . . . . . . . . . . . . Trường hợp cá biệt . . . . . . . . . . . . . . . . . . . 2.6.1 Cấu hình dạng (8,6,3) . . . . . . . . . . . . . . 2.6.2 Cấu hình dạng (8,7,4) . . . . . . . . . . . . . . Phần cơ bản của chứng minh: Các trường hợp đặc biệt 2.7.1 Cấu hình dạng (8,7,3) . . . . . . . . . . . . . . 2.7.2 Cấu hình dạng (8,6,2) . . . . . . . . . . . . . . 2.7.3 Cấu hình dạng (8,6,1) . . . . . . . . . . . . . . 2.7.4 Cấu hình dạng (8,5,1) . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 34 35 35 38 42 42 47 52 58 63 ii Mở đầu Giả thuyết Erdős-Szekeres được đề cập từ rất sớm (vào năm 1935): 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. Bất chấp sự cố gắng của hàng trăm nhà toán học đã nghiên cứu và viết hàng trăm bài báo, giả thuyết Erdős-Szekeres mới chỉ được chứng minh trọn vẹn cho các trường hợp n = 3, 4, 5. Gần đây, năm 2006, trường hợp n = 6 đã được chứng minh bởi Szekeres và Peters nhờ máy tính. Sau đó, năm 2009, ba nhà toán học là Knut Dehnhardt, Heiko Harboth và Zsolt Lángi đã đưa ra một chứng minh thuần túy toán học cho một trường hợp riêng của trường hợp n = 6. Năm 1978, Erdős đã phát biểu một bài toán mới, đó là bài toán Erdős về đa giác lồi rỗng: Cho n là một số tự nhiên bất kỳ, tồn tại hay không số nguyên dương nhỏ nhất E(n) sao cho từ mọi tập chứa tối thiểu E(n) điểm ở vị trí tổng quát trên mặt phẳng đều có thể chọn ra được n điểm là đỉnh của một đa giác lồi rỗng. 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. Ngay sau đó, cũng vào 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 mà với n ≥ 7 không thể lấy ra được đa giác lồi rỗng 7 đỉnh. Như vậy,chỉ còn lạ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, Koselev đã Chứng minh định lý: mọi tập với tối thiểu 463 điểm ở vị trí tổng quát trên mặt phẳng đều chứa 6 điểm tạo thành lục giác lồi rỗng. Luận văn có mục đích trình bày chứng minh công thức E(6) ≤ 463 theo bài báo của Koselev [20]. Để làm rõ bức tranh toàn cục, Luận văn cũng trình bày tổng quan về bài toán Erdős về đa giác lồi rỗng. Luận văn gồm 2 chương: iii Chương 1: Tổng quan về bài toán Erdős về đa giác lồi rỗng. Chương 2: Chứng minh đánh giá E(6) ≤ 463 của Koselev. Luận văn được hoàn thành dưới sự hướng dẫn của PGS.TS. Tạ Duy Phượng. Tôi xin bày tỏ lòng biết ơn Thầy đã tận tình giúp đỡ tôi trong suốt quá trình tập dượt nghiên cứu và viết luận văn. Tôi xin trân trọng cảm ơn các Thầy Cô giáo trường Đại học Khoa học - Đạị học Thái Nguyên và Viện Toán học Việt Nam đã tận tình giảng dạy và giúp đỡ để tôi hoàn thành khóa học. Cuối cùng xin chân thành cảm ơn gia đình, bạn bè đã động viên, giúp đỡ, khích lệ và tạo mọi điều kiện cho tôi trong quá trình học tập và nghiên cứu. Thái Nguyên, ngày 10 tháng 4 năm 2015 Nguyễn Thị Hằng iv Chương 1 Tổng quan bài toán Erdős về đa giác lồi rỗng 1.1 Giới thiệu và xây dựng kết quả chính Năm 1935 Erdős-Szekeres đã phát biểu bài toán sau đây. Bài toán 1(Erdős-Szekeres) Cho số nguyên n ≥ 3, hãy tìm một số nguyên dương nhỏ nhất g(n) sao cho từ một tập hợp bất kỳ các điểm trên mặt phẳng ở vị trí tổng quát và chứa tối thiểu g(n) điểm thì có thể chọn ra một tập hợp con có n điểm là đỉnh của một đa giác lồi n cạnh. Năm 1978 Erdős đã phát biểu một dạng khác của bài toán trên. Bài toán 2 (Erdős-Szekeres) Cho số nguyên bất kì n ≥ 3, hãy tìm số nguyên dương nhỏ nhất h(n) sao cho từ mọi tập điểm X trên mặt phẳng ở vị trí tổng quát và chứa tối thiểu h(n) điểm có thể chọn ra một tập hợp gồm n điểm mà các phần tử của nó là đỉnh của một n giác lồi và rỗng. Nghĩa là n giác lồi này không chứa một điểm nào bên trong X. Ta nhắc lại tập các đỉnh trên mặt phẳng ở vị trí tổng quát nếu như không có ba điểm nào nằm trên một đường thẳng. Cả hai bài toán đều là những bài toán điển hình trong hình học tổ hợp và lý thuyết Ramsey (xem [5], [6], [7]). Bài toán thứ nhất Erdős-Szekeres đã xét trong bài báo [2]. Erdős-Szekeres 1 đã chứng minh rằng  tồn tại g(n) với n bất kì và được dựa trên đánh giá trên 2n − 4 g(n) ≤ n − 2 +1 và cũng đưa ra một giả thuyết g(n) = 2n−2 +1. Giả thuyết này đã được khẳng định cho n ≤ 6. Ở đây trường hợp g(n) = 3 là hiển nhiên. Trường hợp g(4) = 5 đã được chứng minh bởi Klein năm 1935 (xem trong Hình 1 trong đó biểu thị tất cả khả năng phân bố các điểm trên mặt phẳng). Mệnh đề g(5) = 9 đã được Ender Makai chứng minh. Tuy nhiên, có vẻ như Makai mới chỉ ra phản ví dụ nói rằng g(5) ≥ 9. Mệnh đề g(5) = 9 đã được chứng minh bởi Đoàn Hữu Dũng 1967 [1]. Mệnh đề g(6) = 17 đã được khẳng dịnh bởi Szekeres và Peter năm 2006. Ngoài ra năm 1961, Erdős-Szekeres đã chứng minh đánh giá dưới g(n) ≥ 2n−2 +1. Hình 1: Mọi tập hợp từ năm điểm đều chứa tứ giác lồi   2n − 4 Bất đẳng thức g(n) ≤ n − 2 + 1 đã được nhiều lần làm tốt lên. Đã có ba kết quả liên tiếp vào năm 1998. Kết quả đầu  tiên thuộc về hai 2n − 4 vợ chồng F.Chung và R.Graham: g(n) ≤ n − 2 (xem [9]). Kết quả   2n − 4 thứ hai thuộc về Kleitman và Pachter là g(n) ≤ + 7 − 2n n−2 (xem [10]).  Và cuối  cùng đánh giá tốt thứ ba thì thuộc về Tóth và Valtr 2n − 5 g(n) ≤ n − 3 +2 (xem [11]). Trong năm 2005 thì Tóth và Vailtr thay   2n − 5 đánh giá trên bằng đánh giá g(n) ≤ n − 3 + 1 với (n ≥ 5) tốt hơn một đơn vị (xem [12]) và đây cũng là đánh giá tốt nhất cho tới nay. Như vậy giả thuyết Erdős-Szekeres chưa được chứng minh cũng chưa có phản ví dụ. Bài toán 2 được nghiên cứu tương đối sâu hơn. Đẳng thức h(3) = 3 và h(4) = 5 là hiển nhiên (xem Hình 1). Đánh giá h(5) = 10 đã được chứng minh bởi Harborth 1978 (xem [13]). Năm 1983 Horton đã chứng 2 minh rằng h(n) không tồn tại khi n ≥ 7 (xem [14]). Mãi đến năm 2006 Gerken mới chứng minh  được  tồn tại của h(6) và chứng minh bất đẳng 13 thức h(6) ≤ g(9) ≤ + 1 = 1717 (xem [15]). Và tất cả những 6 đánh giá dưới cho h(6) đã chứng minh được bằng máy tính. Đánh giá dưới đầu tiên thuộc về Overmars và Scholten năm 1988, đó là h(6) ≥ 27 (xem [16]). Đánh giá tiếp theo năm 2001 cũng bởi Overmars và cũng là đánh giá tốt nhất hiện nay h(6) ≥ 30 (xem [17]). Sai khác giữa đánh giá trên và đánh giá dưới là quá lớn. Làm giảm đánh giá này là một bài toán khó. B.A.Koselev đã chứng minh định lý sau đây. Định lí 1. (Koselev, [20], 2008) Ta có bất đẳng thức h(6) ≤ max {g(8), 400} ≤ 463. Lịch sử của bài toán Erdős-Szekeres có thể xem trong bài báo tổng quan của Soltan [5]. 1.2 Phương pháp chứng minh Ta nói rằng một tập hữu hạn điểm trên mặt phẳng chỉ chứa k-giác đã cho nếu như từ tập đó có thể chọn được tập hợp k điểm là các đỉnh của một k -giác. Hình 2: Định nghĩa các tập H, I, J, K Để chứng minh Định lý 1 cần khẳng định rằng trong một tập hợp bất kì trên mặt phẳng ở vị trí tổng quát mà có số điểm lớn hơn hoặc bằng 463 3 thì phải tồn tại lục giác lồi rỗng. Ta cố định một tập điểm bất kì, ta nhận xét rằng tập điểm X chứa tối thiểu X một bát giác lồi. Quan hệ bao hàm trong tập hợp tất cả các bát giác lồi tạo nên tập hợp X là một quan hệ chặt. Bởi vậy luôn luôn có thể nói về các bát giác nhỏ nhất kể các điểm từ trong X . Chọn một trong chúng và kí hiệu tập đỉnh của chúng là tập H . Kí hiệu I 0 = (conv(H)\H) ∩ X là tập tất cả các điểm của X nằm bên trong bao lồi của H. Hoặc I 0 là rỗng (khi đó ta có bát giác rỗng). Hoặc là conv(I 0 ) chứa đa giác lồi là một đoạn (2-giác) hoặc là một điểm (1-giác). Ta kí hiệu I là tập tất cả các đỉnh (I = ∂(conv(I 0 )) ∩ X). Nếu |I| > 2 thì có thể xây dựng J 0 = (conv(I)\I) ∩ X như là tập hợp tất cả các điểm của X mà nằm bên trong bao lồi của I . Nhận xét rằng nếu J 0 6= 0 thì conv(J 0 ) cũng là đa giác lồi (có thể là 1-giác hoặc 2-giác), bởi vậy thì ta có thể xây dựng J như là tập hợp tất cả các đỉnh của nó. Tương tự xây dựng tập K, L và quá trình này sẽ kết thúc sau hữu hạn bước. Hình 3: Tập hợp dạng (8,0,0,...) và (8,3,0,...) Đặt i = |I| và j = |J|, ... Ta nói rằng tập X có dạng (8, i, j, ...). Trong trường hợp suy biến thì xuất hiện dạng (8, 0, 0, ...), (8, i, 0, ...), ...(xem Hình 3). 4 Hình 4: Sự các định không duy nhất của các dạng Ta nhận xét rằng các dạng này không duy nhất. Ví dụ tập hợp trong Hình 4 có dạng (8, 4, 1, ...), nếu như bát giác lồi tối thiểu trong đó lấy A1 A2 ...A8 . Ta sẽ có dạng (8, 5, 2, ...), nếu như xét bát giác B1 B2 ...B8 . Dưới đây chúng ta sẽ không nói về sự đa dạng của các bát giác lồi trong X. Khi ta nói về dạng của tập X, thì ta hiểu X có một bát giác lồi, tương ứng với nó thì X có một dạng đã cho. Để chứng minh sự tồn tại của lục giác lồi rỗng trong tập hợp X thì đầu tiên chúng ta xét tập con H 0 = conv(H) ∩ X . Ta có bổ đề sau: Bổ đề (Valtr) Cho X, H, I, J, K như trong định nghĩa ở trên. Nếu |H| ≥ 7 và trong X không có lục giác lồi rỗng thì K = ∅. Câu nói "như trong bổ đề" nói chung không hoàn toàn là chính xác bởi vì từ trước tới nay ta luôn luôn giả thiết rằng |H| = 8. Nhưng rõ ràng trong định nghĩa về các bao lồi lồng nhau trong Hình 2 thì có thể cho cả trường hợp |H| = 6 8. Từ Bổ đề ta suy ra ngay sự tồn tại lục giác lồi rỗng trong mọi tập hợp dạng (8, i, j, k, ...), khi k > 0. Bởi vậy tiếp theo chúng ta chỉ xét các trường hợp (8, i, j, 0, 0, 0, ...). Để cho ngắn gọn chúng ta sẽ nói chỉ về các trường hợp đó là cấu hình dạng (8, i, j). Tất cả các trường hợp đó sẽ gồm 43 cấu hình bởi vì i và j có thể thay đổi trong miền giới hạn: 0 ≤ i ≤ 2 hoặc 3 ≤ i ≤ 7 và 0 ≤ j ≤ 7. 5 Theo ý tưởng, mỗi trường hợp trong 43 trường hợp cần phải xét riêng. Nhưng mà chúng ta có thể chia tất cả tập hợp này ra thành 7 lớp để với mỗi lớp đó có thể áp dụng cách tiếp cận riêng để chứng minh. Trong 6 lớp đầu tiên chúng ta sử dụng phương pháp nào đó để khẳng định sự tồn tại của lục giác lồi rỗng trong tập H 0 . Trong lớp thứ 7 thì chúng ta cần sử dụng nhiều thông tin hơn về tập X . Trong trường hợp này thì ta gọi là trường hợp đặc biệt và nó thuộc vào cấu hình dạng (8, 7, 3), (8, 6, 2), (8, 6, 1), (8, 5, 1) Ta có định lí sau. Định lý. Giả sử X ⊂ R2 là tập các điểm ở vị trí tổng quát và |X| ≥ g(8). Khi đó, trong mỗi 39 trường hợp không phải trường hợp đặc biệt thì tồn tại tập H 0 chứa lục giác lồi rỗng. Với 4 trường hợp đặc biệt, ta có thể chỉ ra ví dụ, trong đó H 0 không chứa lục giác lồi rỗng. Giả thiết rằng ta đã chứng minh được định lý. Khi đó ta có thể phân loại tất cả các cấu hình trên mặt phẳng. Hơn nữa, ngay lập tức ta có thể chứng minh định lý 1 cho hầu hết tất cả các trường hợp trong cấu hình này. Với những trường hợp đặc biệt thì chúng ta cần phải sử dụng các phần tử của X\H 0 , để H 0 thỏa mãn định lý. Có nghĩa là tự nó không chứa lục giác lồi rỗng, hay như ta sẽ nói nó thể hiện phản ví dụ. Khi đó chúng ta phải đặt những hạn chế rất nặng lên trên các phân bố điểm trong các phản ví dụ. 1.3 Định nghĩa và kí hiệu Trong mục này chúng ta đưa vào một số những khái niệm hình học mà chúng được sử dụng trong các chứng minh tiếp theo. 6 1.3.1 Định nghĩa Hình 5: Định nghĩa các miền sector Cho ba điểm bất kì X, Y, Z trên mặt phẳng ở vị trí tổng quát. Ta xác định PXY (Z) là nửa mặt phẳng mở tương ứng với nửa đường thẳng XY, chứa điểm Z . Xích lồi là tập hợp các đỉnh liên tiếp của một đa giác lồi. Xích lồi ABC đã cho xác định 3-sector (xem Hình 5 bên trái) (ABC) = (PAB (C) ∩ PBC (A))\conv({A, B, C}). Xích lồi ABCD xác đinh 4-sector (xem Hình 5 ở giữa) (ABCD) = ((ABC) ∩ (BCD)\conv({A, B, C, D}). Xích lồi ABCDE xác định 5-sector hay miền cấm của ngũ giác (xem Hình 5 bên phải) (ABCDE) = ((ABCD) ∩ (BCDE)\conv({A, B, C, D, D}). Ta nói rằng điểm được xác định từ một đa giác lồi đã cho bởi một đường thẳng chứa cạnh của đa giác đó nếu đa giác đó được đặt trong nửa mặt phẳng khác tương ứng với đường thẳng đó. Mọi miền cấm của ngũ giác cũng là tập hợp các điểm được xác định từ ngũ giác ấy bởi đúng một đường thẳng (xem Hình 5 trong đó đường thẳng AE ). Tập các điểm tách khỏi đa giác bởi một đường thẳng cụ thể nào đó, thí dụ, đường thẳng P Q được gọi là 2-sector và kí hiệu là (P Q). Ta sẽ nói rằng, điểm được tách khỏi đa giác bởi hai đường thẳng trên cạnh của chúng đồng thời nếu điểm ấy được xác định từ đa giác bởi cả hai đường thẳng đã cho, nghĩa là điểm ấy nằm trong giao của hai 2-sector tương ứng. Ngược lại, điểm tách khỏi đa giác bởi hai đường thẳng chứa các cạnh của nó nếu nó tách khỏi đa giác bởi chỉ 1 trong 2 đường thẳng ấy, tức là nằm 7 trong hợp của các 2-sector tương ứng. Giả sử có một cấu hình (8, i, j), i ≥ 3. Mệnh đề 1. Các tính chất sau đây được thỏa mãn: (a) Mọi đường thẳng chứa cạnh của i-giác tách khỏi nó đúng ba đỉnh của bát giác. (b) Hai đường thẳng chứa hai cạnh liên tiếp của i-giác tách khỏi nó không ít hơn bốn đỉnh của bát giác. (c) Mọi đường thẳng chứa các cạnh liên tiếp của i-giác tách khỏi nó đồng thời không nhiều hơn hai đỉnh của bát giác. Hình 6: Trường hợp không thể xảy ra phân bố các đỉnh trong (a) của Mệnh đề 1 Chứng minh Mệnh đề 1. Đầu tiên xét phần (a). Giả sử rằng một đường thẳng nào đó tách khỏi i-giác nhiều hơn ba đỉnh của bát giác. Sử dụng các đỉnh này và đồng thời một cặp đỉnh của i-giác mà đường thẳng đi qua các điểm ấy, thì có thể xây dựng được một lục giác lồi rỗng trong cấu hình và chứng minh xong. Nếu giả thiết rằng đường thẳng tách khỏi i-giác ít hơn ba đỉnh của bát giác thì thay "chúng" (có thể là một đỉnh) bởi các đỉnh của đa giác, qua chúng kẻ đường thẳng, ta nhận được một bát giác nhỏ hơn (xem Hình 6) và điều này là không thể. 8 Phần (b) chứng minh tương tự phần (a). Xét phần (c). Giả thiết rằng hai đường thẳng chứa các cạnh liên tiếp của i-giác tách khỏi từ nó đồng thời ba đỉnh của bát giác (nhiều hơn ba đỉnh là không thể, theo phần (a)). Khi đó lại theo phần (a) hai đường thẳng này sẽ tách khỏi từ i-giác trong tổng thể chỉ ba đỉnh nêu trên, mà điều này không thể được theo (b). Mệnh đề 1 được chứng minh. 1.3.2 Vị trí Giả sử cho một cấu hình bất kì (8, i, j). Tách từ cấu hình này ra một cấu hình gồm i-giác ở giữa và j-giác bên trong. Cấu hình này cần dùng trong các chứng minh sau vì vậy chúng ta đi xét cấu hình này một cách kĩ càng hơn. Chúng ta cần phân loại tập hợp vị trí các đỉnh của i-giác và j-giác. Để đơn giản ta sẽ coi j = 3 và j = 4 bởi vì những trường hợp khác ta không cần xét. Hình 7: (i,3)-phân bố dạng [a1 , b1 , a2 , b2 , a3 , b3 ] Giả sử đầu tiên với j = 3. Ba đường thẳng đi qua các cạnh của tam giác chia mặt phẳng ngoài tam giác ra thành sáu phần, trong đó ba phần của chúng có dạng "tam giác", ba phần còn lại có dạng "tứ giác". Ta nói rằng cấu hình mà cấu tạo từ i-giác và tam giác là (i, 3)- phân bố dạng 9 [a1 b1 a2 b2 a3 b3 ], nếu như lượng các đỉnh của i-giác nằm bên trong tam giác a1 ; a2 ; a3 , còn lượng các đỉnh nằm bên trong tứ giác là b1 ; b2 ; b3 (xem Hình 7). Nói chung kí hiệu [a1 b1 a2 b2 a3 b3 ] xác định một cách không duy nhất. Ví dụ, cũng chính kết hợp đó chúng ta có thể nói về cấu hình (i, 3)-phân bố dạng [a2 b2 a3 b3 a1 b1 ] hoặc (i, 3)-phân bố dạng [a1 b3 a3 b2 a2 b1 ]. Nhưng như vậy không sai khác về mặt nguyên tắc các khả năng có thể viết của các đỉnh. Cách viết này từ quan điểm của chúng ta là tương đương và do đó sau này chúng ta sẽ sử dụng cách viết bất kì trong số đó. Ở đây, điều quan trọng cần nhấn mạnh là mọi cách viết cố định sẽ bắt đầu từ ai , có nghĩa là từ số đỉnh của i-giác trong miền, các đại lượng ai , bj sẽ liên tiếp nhau theo một trật tự được đặt trong các phần của mặt phẳng tương ứng (cùng chiều hoặc ngược chiều kim đồng hồ). Giả sử j = 4. Giống như j = 3 chúng ta xác định các phân bố như sau: Hình 8: Chia mặt phẳng và xác định các tập hợp Bi và các số bi Bốn đường thẳng đi qua các đỉnh của tứ giác chia mặt phẳng bên ngoài tứ giác thành một số phần, có thể có ba dạng khác nhau về mặt nguyên tắc. Tất cả các dạng đó được biểu diễn trong Hình 8. Trong trường hợp thứ nhất, tứ giác là hình bình hành. Trong trường hợp thứ hai thì tứ giác được xác định bởi một hình thang, còn trong trường hợp thứ ba thì là một tứ giác không phải là hình thang. Trong mỗi trường hợp này chúng ta tách ra các miền chia mặt phẳng xung quanh tứ giác mà được biểu thị trên Hình 8 bởi B1 ; B2 ; B3 ; B4 . Cho cấu trúc tạo thành từ i-giác và tứ giác, đặt bk là số đỉnh của i-giác nằm trong miền Bk , k = 1; 4. Với mỗi một trong ba trường hợp này, các đỉnh b1 ; b2 ; b3 ; b4 được xác định một cách duy nhất với sự chính xác đến vị trí mà chúng ta đưa vào kí hiệu B1 ; B2 ; B3 ; B4 . Ngầm hiểu rằng, các miền và số lượng các đỉnh trong chúng đã được sắp theo 10 thứ tự (theo chiều kim đồng hồ). Khi đại lượng phân bố các đỉnh b1 ; b2 ; b3 ; b4 trong cấu hình đã cho được cố định, ta xét các a1 ; a2 ; a3 ; a4 như sau: Hình 9: Chia mặt phẳng và xác định các tập hợp Ai và các số ai Trường hợp khi tứ giác là hình bình hành thì hiển nhiên (Hình 9 bên trái): Các số a1 ; a2 ; a3 ; a4 chính là số đỉnh của i-giác nằm trong miền tương ứng. Giả sử tứ giác là hình thang. Khi đó không hạn chế tổng quát các số b1 ; b2 ; b3 ; b4 có thể coi như được sắp xếp như trong Hình 8 và Hình 9. Xét "miền phụ" A0 , A, A00 , A3 , A4 (xem Hình 9 giữa). Kí hiệu a0 , a, a00 , a3 , a4 là số đỉnh của i-giác trong miền tương ứng. Chúng ta lấy các số nguyên không âm bất kì a1 , a2 với điều kiện a1 + a2 = a0 + a + a00 , a1 ≤ a0 + a, a2 ≤ a + a00 . Chúng ta sắp đặt chúng như trong Hình 10 bên trái. Nói một cách khác, chúng ta lấy a1 đỉnh của i-giác từ miền A0 ∪ A ∪ A00 đưa vào miền A0 ∪ A, các đỉnh còn lại đặt vào trong miền A ∪ A00 . Như vậy, khi xác định dạng phân bố chúng ta bỏ qua số lượng đỉnh i trong A và để được xác định ta đưa các đỉnh khác của nó vào trong miền A0 ∪ A và A ∪ A00 . Như vậy chúng ta đã thực hiện các bước làm như để chỉ ra, nhưng chúng không có ý nghĩa. Cuối cùng giả sử tứ giác không phải hình thang. Trường hợp này được biểu diễn trên Hình 9 bên phải. Ở đây một lần nữa không hạn chế tổng quát, xuất hiện các miền phụ A2 , A(1) , ..., A(5) , trong đó tương ứng có 11 a2 , a(1) , ..., a(5) đỉnh của i-giác. Chọn số nguyên không âm bất kì a1 , a4 , a3 có tính chất a1 + a4 + a3 = a(1) + ... + a(5) , a1 ≤ a(1) + a(2) , a4 ≤ a(2) + a(3) + a(4) , a(3) ≤ a(4) + a(5) . Hình 10: Xác định cuối cùng các số ai và bi Sắp đặt các số trên như trong Hình 10 bên phải. Nói cách khác chúng ta đưa a1 đỉnh của i-giác từ tập A(1) ∪ ... ∪ A5 vào miền A(1) ∪ A(2) ; đặt a4 đỉnh vào miền A(2) ∪ A(3) ∪ A(4) , a3 đỉnh còn lại chúng ta đưa vào miền A(4) ∪ A(5) . Như vậy, lần này chúng ta đã không quan tâm tới lượng đỉnh của i-giác trong miền A(1) ∪ A(2) , A(2) ∪ A(3) ∪ A(4) , A(4) ∪ A(5) . Nhưng để thuận tiện hơn, ta phân bố các đỉnh của nó theo các tập hợp này. Như trong trường hợp hình thang, ta không quan tâm tới cách phân bố như trên. Kết quả, chúng ta có thể nói rằng mỗi cấu trúc tạo thành từ i-giác và tứ giác (i, 4)-phân bố dạng [a1 b1 a2 b2 a3 b3 a4 b4 ]. Như vậy giống như trong trường hợp (i, 3) phân bố, dạng ở đây được xác định một cách không duy nhất. Thứ nhất là có sự tự do trong việc lựa chọn cách đánh số của các đại lượng ai , bi . Thứ hai là các số ai có thể nhận các giá trị thỏa mãn các hạn chế đã cho. Ngoài ra , như trước đây chúng ta sẽ viết liên tiếp ai , bi mỗi một lần đều bắt đầu từ vị trí a1 nào đó. Hình 11: Ví dụ về xác định không duy nhất dạng phân bố 12 Hình 11, bên trái biểu diễn cấu hình tạo thành từ lục giác và tứ giác. Nó có thể mô tả, ví dụ như (6, 4)-phân bố dạng [2, 0, 1, 0, 1, 1, 0, 1] (xem Hình 11 giữa). Có thể coi nó như (6, 4)-phân bố dạng [1, 0, 2, 0, 1, 1, 0, 1] (xem Hình 11 phải). Tất nhiên tồn tại một số cách giải thích khác nhưng với mỗi cách giải thích thì chúng đều biểu thị thông tin như nhau về vị trí tương quan giữa các đỉnh của lục giác và tứ giác, mà chúng ta sẽ cần cho chứng minh tiếp theo. 13 Chương 2 Chứng minh công thức đánh giá E(6) ≤ 463 2.1 Trường hợp đơn giản Trong mục này chúng ta sẽ xét cấu hình dạng sau đây: (8, 0, 0), (8, 6, 0), (8, 7, 0), (8, i, 6), (8, i, 7) với (3 ≤ i ≤ 7) Hiển nhiên trong mỗi cấu hình này tồn tại lục giác lồi rỗng. Đồng thời trong mục này chúng ta có thể đưa thêm vào trường hợp (8, 7, 2), vì trong cấu hình bất kỳ của dạng này chứa lục giác lồi rỗng. Chỉ cần kẻ một đường thẳng đi qua hai điểm X và Y nằm trong 7-giác, khi đó một trong hai nửa mặt phẳng chứa tối thiểu 4 đỉnh của thất giác và do đó cùng với X và Y tạo thành lục giác lồi rỗng. 2.2 Trường hợp với j = 0 (1 ≤ i ≤ 5) Xét các cấu hình dạng (8, 1, 0), (8, 2, 0), (8, 3, 0), (8, 4, 0), (8, 5, 0) và mỗi cấu hình này được xem xét riêng. 14