Luận văn thạc sĩ về lục giác lồi rỗng tại Đại học Quốc gia Hà Nội

"Luận văn thạc sĩ về lục giác lồi rỗng: Nghiên cứu và phân tích các tính chất hình học của lục giác lồi rỗng, ứng dụng trong toán học và khoa học kỹ thuật."

• Tác giả: Nguyễn Giang Thành
• Người hướng dẫn: PGS. Tạ Duy Phượng
• Trường học: Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
• Chuyên ngành: Phương pháp toán sơ cấp
• Đề tài: Về lục giác lồi rỗng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN ERDÖS VỀ ĐA GIÁC LỒI RỖNG
• 1.1. Bài toán 1
• 1.1.1. Bài toán 1a Tồn tại hay không tồn tại số ES(n)?
• 1.1.2. Bài toán 1b Nếu số ES(n) tồn tại thì xác định ES(n) như một hàm của n
• 2. CHƯƠNG 2: CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ
• 2.1. Lược đồ chứng minh
• 2.2. Các trường hợp đơn giản
• 2.2.1. Các trường hợp (3, ≥ 0) và (8,3)
• 2.2.2. Các trường hợp (6,3) và (7,3)
• 2.2.3. Các trường hợp (4, ≥ 0) và (≥ 7, 4)
• 2.2.4. Các trường hợp (5, 0) và (≥ 7, 5, 0)
• 2.2.4.1. Các trường hợp (5, 0) và (8, 5, 0)
• 2.2.4.2. Trường hợp (7, 5, 0)
• 2.2.5. Các trường hợp riêng
• 2.2.5.1. Trường hợp (5,1)
• 2.2.5.2. Trường hợp (6,1)
• 2.2.5.3. Các trường hợp (6,2) và (7,1)
• 2.2.6. Các trường hợp (5, ≥ 2)
• 2.2.7. Các trường hợp (6, ≥ 4)
• 2.2.8. Các trường hợp (≥ 7, ≥ 5, ≥ 1)
• 2.3. Ứng dụng của Quy tắc 1 và 2
• 2.4. Ứng dụng các Quy tắc 1-3
• 2.5. Trường hợp (1, 1, 1, 1, 1, 1, 1)
• 2.6. Trường hợp (1, 1, 1, 1, 1, 1, 1, 0)
• 2.7. Trường hợp (1, 1, 1, 1, 1, 1, 1, 1)
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về luận văn thạc sĩ về lục giác lồi rỗng

Luận văn thạc sĩ về lục giác lồi rỗng là một nghiên cứu quan trọng trong lĩnh vực hình học tổ hợp. Đề tài này không chỉ khám phá các khái niệm cơ bản mà còn đi sâu vào các bài toán nổi bật như giả thuyết Erdős-Szekeres. Nghiên cứu này nhằm mục đích làm rõ các vấn đề liên quan đến lục giác lồi rỗng và ứng dụng của nó trong toán học hiện đại.

1.1. Khái niệm lục giác lồi rỗng và ứng dụng

Lục giác lồi rỗng là một đa giác có sáu đỉnh, không chứa điểm nào bên trong. Khái niệm này có ứng dụng quan trọng trong việc giải quyết các bài toán hình học tổ hợp, đặc biệt là trong việc xác định số điểm cần thiết để tạo thành một lục giác lồi rỗng từ một tập hợp điểm cho trước.

1.2. Giả thuyết Erdo s Szekeres và tầm quan trọng

Giả thuyết Erdős-Szekeres, được phát biểu vào năm 1935, khẳng định rằng từ một tập hợp điểm lớn, có thể tìm ra một đa giác lồi. Điều này không chỉ có ý nghĩa lý thuyết mà còn mở ra nhiều hướng nghiên cứu mới trong hình học tổ hợp.

II. Vấn đề và thách thức trong nghiên cứu lục giác lồi rỗng

Nghiên cứu lục giác lồi rỗng đối mặt với nhiều thách thức, đặc biệt là trong việc xác định số điểm tối thiểu cần thiết để tạo thành một lục giác lồi rỗng. Các nhà nghiên cứu đã đưa ra nhiều giả thuyết và phương pháp khác nhau để giải quyết vấn đề này.

2.1. Thách thức trong việc chứng minh giả thuyết

Việc chứng minh giả thuyết Erdős-Szekeres cho trường hợp n = 6 đã gặp nhiều khó khăn. Mặc dù đã có nhiều nỗ lực, nhưng cho đến nay, vẫn chưa có lời giải hoàn chỉnh mà không sử dụng máy tính.

2.2. Các phương pháp nghiên cứu hiện tại

Các phương pháp nghiên cứu hiện tại bao gồm việc sử dụng các kỹ thuật hình học và lý thuyết đồ thị để phân tích các cấu hình điểm. Những phương pháp này giúp các nhà nghiên cứu tìm ra các đánh giá tốt hơn cho số điểm cần thiết để tạo thành lục giác lồi rỗng.

III. Phương pháp chứng minh E 6 ES 9 trong lục giác lồi rỗng

Một trong những mục tiêu chính của luận văn là chứng minh rằng E(6) ≤ ES(9). Điều này có ý nghĩa quan trọng trong việc xác định số điểm tối thiểu cần thiết để tạo thành một lục giác lồi rỗng.

3.1. Các bước chứng minh cơ bản

Chứng minh bắt đầu bằng việc xác định các cấu hình điểm và áp dụng các định lý hình học để đưa ra các đánh giá cho E(6). Các bước này bao gồm việc phân tích các trường hợp cụ thể và sử dụng các kỹ thuật hình học để chứng minh.

3.2. Kết quả và ý nghĩa của chứng minh

Kết quả của chứng minh cho thấy rằng E(6) không thể lớn hơn ES(9), từ đó mở ra hướng nghiên cứu mới trong việc tìm hiểu các lục giác lồi rỗng và ứng dụng của chúng trong toán học.

IV. Ứng dụng thực tiễn của lục giác lồi rỗng trong xây dựng

Lục giác lồi rỗng không chỉ có ý nghĩa lý thuyết mà còn có nhiều ứng dụng thực tiễn trong lĩnh vực xây dựng. Việc áp dụng các khái niệm này giúp tối ưu hóa thiết kế và cấu trúc công trình.

4.1. Tối ưu hóa thiết kế công trình

Sử dụng lục giác lồi rỗng trong thiết kế công trình giúp tối ưu hóa không gian và vật liệu. Các cấu trúc này có thể tạo ra các không gian mở rộng và giảm thiểu lãng phí vật liệu.

4.2. Các ví dụ thực tiễn

Nhiều công trình hiện đại đã áp dụng các nguyên lý của lục giác lồi rỗng để tạo ra các thiết kế độc đáo và hiệu quả. Ví dụ, các tòa nhà có hình dạng lục giác không chỉ đẹp mắt mà còn tiết kiệm năng lượng.

V. Kết luận và tương lai của nghiên cứu lục giác lồi rỗng

Nghiên cứu về lục giác lồi rỗng vẫn còn nhiều thách thức và cơ hội. Các nhà nghiên cứu cần tiếp tục khám phá và phát triển các phương pháp mới để giải quyết các vấn đề còn tồn tại.

5.1. Tương lai của nghiên cứu

Với sự phát triển của công nghệ và các phương pháp nghiên cứu mới, tương lai của nghiên cứu lục giác lồi rỗng hứa hẹn sẽ mang lại nhiều khám phá thú vị và ứng dụng thực tiễn.

5.2. Khuyến nghị cho nghiên cứu tiếp theo

Các nhà nghiên cứu nên tập trung vào việc phát triển các phương pháp chứng minh mới và ứng dụng các công nghệ hiện đại để giải quyết các vấn đề trong nghiên cứu lục giác lồi rỗng.

Nội dung chính

Tổng quan nghiên cứu

Bài toán về đa giác lồi rỗng là một trong những vấn đề nổi bật trong lĩnh vực hình học tổ hợp, được phát biểu lần đầu bởi P. Erdős vào năm 1978. Cụ thể, bài toán đặt ra câu hỏi về sự tồn tại số nguyên dương nhỏ nhất ( E(n) ) sao cho từ mọi tập điểm ở vị trí tổng quát trên mặt phẳng với ít nhất ( E(n) ) điểm, có thể chọn ra ( n ) điểm tạo thành đa giác lồi rỗng — đa giác không chứa điểm nào của tập ban đầu bên trong. Trước đó, giả thuyết Erdős-Szekeres (1935) đã xác định số điểm tối thiểu ( ES(n) ) để đảm bảo tồn tại đa giác lồi ( n )-đỉnh, với công thức dự đoán ( ES(n) = 2^{n-2} + 1 ). Tuy nhiên, giả thuyết này chỉ được chứng minh cho các trường hợp nhỏ như ( n=3,4,5,6 ), trong đó trường hợp ( n=6 ) được chứng minh gần đây bằng máy tính.

Nghiên cứu tập trung vào việc đánh giá và chứng minh các giới hạn trên dưới của ( E(6) ), trường hợp còn mở duy nhất của bài toán đa giác lồi rỗng. Theo các kết quả hiện tại, ( 30 \leq E(6) \leq 463 ), với đánh giá trên của Gerken (2008) cho thấy ( E(6) \leq ES(9) \leq 1717 ). Mục tiêu của luận văn là trình bày tổng quan về bài toán Erdős-Szekeres và bài toán Erdős về đa giác lồi rỗng, đồng thời trình bày chi tiết chứng minh đánh giá ( E(6) \leq ES(9) ) của Gerken. Phạm vi nghiên cứu tập trung vào các tập điểm trên mặt phẳng ở vị trí tổng quát, không có ba điểm thẳng hàng, trong khoảng thời gian từ năm 1935 đến 2013, với các kết quả chủ yếu được phát triển trong thế kỷ 20 và đầu thế kỷ 21.

Ý nghĩa của nghiên cứu nằm ở việc làm sáng tỏ một bài toán mở quan trọng trong hình học tổ hợp, góp phần phát triển các phương pháp chứng minh mới, ứng dụng định lý Ramsey, và mở rộng hiểu biết về cấu trúc hình học của các tập điểm lớn. Các số liệu cụ thể như ( ES(5) = 9 ), ( E(5) = 10 ), và đánh giá ( 30 \leq E(6) \leq 463 ) làm nổi bật tính thách thức và sự phát triển của lĩnh vực này.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính: giả thuyết Erdős-Szekeres về đa giác lồi và bài toán Erdős về đa giác lồi rỗng. Giả thuyết Erdős-Szekeres phát biểu rằng với mỗi số tự nhiên ( n \geq 3 ), mọi tập điểm ở vị trí tổng quát với ít nhất ( ES(n) = 2^{n-2} + 1 ) điểm đều chứa ( n ) điểm tạo thành đa giác lồi. Bài toán Erdős về đa giác lồi rỗng mở rộng khái niệm này, yêu cầu đa giác lồi không chứa điểm nào bên trong, với số điểm tối thiểu ( E(n) ).

Các khái niệm chuyên ngành quan trọng bao gồm:

• Đa giác lồi rỗng: đa giác lồi không chứa điểm nào của tập điểm ban đầu bên trong.
• Bao lồi (convex hull): đa giác lồi nhỏ nhất chứa toàn bộ tập điểm.
• Cấu hình điểm: phân loại các tập điểm dựa trên số lượng điểm nằm trong bao lồi và các đa giác lồi bao nhau.
• Định lý Ramsey: được sử dụng để chứng minh sự tồn tại của các cấu trúc đa giác lồi trong tập điểm lớn.
• Xích lồi (convex chain) và các miền tam giác, tứ giác, ngũ giác được định nghĩa để phân tích cấu trúc đa giác lồi.

Phương pháp nghiên cứu

Luận văn sử dụng phương pháp phân tích hình học tổ hợp kết hợp với kỹ thuật chứng minh bằng máy tính. Nguồn dữ liệu chính là các tập điểm ở vị trí tổng quát trên mặt phẳng, với các trường hợp cụ thể được phân loại theo số lượng điểm nằm trong bao lồi và các đa giác lồi bao nhau.

Phương pháp phân tích bao gồm:

• Phân loại các cấu hình điểm dựa trên số đỉnh của đa giác lồi bao ngoài và số điểm bên trong.
• Sử dụng các miền tam giác, tứ giác, ngũ giác để xác định khả năng tồn tại đa giác lồi rỗng.
• Áp dụng các bất đẳng thức và giới hạn trên dưới cho số lượng điểm trong các miền để loại trừ các trường hợp không tồn tại đa giác lồi rỗng.
• Sử dụng kỹ thuật đánh dấu theo hướng của bộ ba điểm và thuật toán tìm đa giác lồi rỗng lớn nhất.
• Timeline nghiên cứu kéo dài từ năm 1935 đến 2013, với các bước phát triển quan trọng như chứng minh ( ES(5) = 9 ) vào những năm 1960-1970, chứng minh ( ES(6) = 17 ) bằng máy tính năm 2006, và đánh giá ( E(6) \leq ES(9) ) năm 2008.

Cỡ mẫu trong các chứng minh là các tập điểm với số lượng từ 9 đến vài trăm điểm, được chọn mẫu theo vị trí tổng quát (không có ba điểm thẳng hàng) để đảm bảo tính tổng quát và tránh các trường hợp đặc biệt.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Chứng minh các giá trị nhỏ của ( ES(n) ) và ( E(n) ):

   • ( ES(3) = 3 ), ( ES(4) = 5 ), ( ES(5) = 9 ) đã được chứng minh chi tiết.
   • ( E(3) = 3 ), ( E(4) = 5 ), ( E(5) = 10 ) được xác định chính xác, với ( E(5) = 10 ) do Harborth chứng minh năm 1978.
   • Ví dụ tập 9 điểm không chứa ngũ giác lồi rỗng cho thấy ( E(5) \geq 10 ).

2. Giới hạn cho ( E(6) ):

   • Horton (1983) xây dựng tập điểm không chứa đa giác lồi rỗng 7 đỉnh, chứng minh ( E(n) ) không tồn tại với ( n \geq 7 ).
   • Overmars (2003) chứng minh ( E(6) \geq 30 ) bằng thuật toán và máy tính.
   • Gerken (2008) chứng minh ( E(6) \leq ES(9) ), với ( ES(9) \leq 1717 ), từ đó suy ra ( 30 \leq E(6) \leq 1717 ).
   • Koselev (2007) cải tiến đánh giá trên, cho ( E(6) \leq 463 ).

3. Phân tích chi tiết 57 trường hợp cấu hình đa giác lồi bao nhau:

   • Sử dụng các miền tam giác, tứ giác, ngũ giác để phân tích vị trí điểm và khả năng tạo đa giác lồi rỗng.
   • Mỗi trường hợp được chứng minh hoặc tìm thấy đa giác lồi rỗng 6 đỉnh, hoặc phát hiện mâu thuẫn với giả thiết nhỏ nhất của đa giác lồi 9 đỉnh.
   • Ví dụ, trong trường hợp (6,3,0), các phân bố điểm như (2,0,1,2,0,1) được giải quyết bằng cách xác định các miền chứa điểm và chứng minh tồn tại đa giác lồi rỗng.

4. Mối quan hệ giữa ( E(6) ) và ( ES(9) ):

   • Gerken chứng minh mọi 9-giác lồi đều chứa lục giác lồi rỗng, từ đó ( E(6) \leq ES(9) ).
   • Điều này giúp thu hẹp phạm vi tìm kiếm và đánh giá ( E(6) ).

Thảo luận kết quả

Nguyên nhân của các giới hạn trên xuất phát từ cấu trúc phức tạp của các tập điểm ở vị trí tổng quát và sự khó khăn trong việc loại trừ các trường hợp không tồn tại đa giác lồi rỗng. Việc phân tích chi tiết các cấu hình đa giác lồi bao nhau và sử dụng các miền hình học giúp kiểm soát số lượng điểm và vị trí của chúng, từ đó chứng minh sự tồn tại hoặc không tồn tại đa giác lồi rỗng.

So sánh với các nghiên cứu trước, kết quả của Gerken và Koselev là bước tiến quan trọng, giảm đáng kể khoảng cách giữa đánh giá trên và dưới của ( E(6) ). Việc sử dụng máy tính trong chứng minh ( ES(6) = 17 ) và đánh giá ( E(6) ) cho thấy sự cần thiết của công nghệ tính toán trong giải quyết các bài toán hình học tổ hợp phức tạp.

Ý nghĩa của các kết quả này không chỉ nằm ở việc giải quyết bài toán mở lâu năm mà còn mở ra hướng tiếp cận mới cho các bài toán tương tự trong hình học tổ hợp và lý thuyết đồ thị, đặc biệt là ứng dụng định lý Ramsey và các kỹ thuật phân tích cấu trúc điểm.

Dữ liệu có thể được trình bày qua các biểu đồ phân bố điểm trong các miền tam giác, tứ giác, ngũ giác, cũng như bảng tổng hợp các trường hợp cấu hình và kết quả chứng minh tương ứng, giúp minh họa rõ ràng quá trình phân tích và loại trừ.

Đề xuất và khuyến nghị

1. Phát triển thuật toán tối ưu hơn để xác định ( E(6) ):

   • Động từ hành động: Cải tiến, phát triển.
   • Target metric: Giảm độ phức tạp tính toán và tăng độ chính xác đánh giá.
   • Timeline: 2-3 năm.
   • Chủ thể thực hiện: Các nhà toán học ứng dụng và chuyên gia khoa học máy tính.

2. Mở rộng nghiên cứu sang các trường hợp ( n > 6 ) với các điều kiện đặc biệt:

   • Động từ hành động: Nghiên cứu, khảo sát.
   • Target metric: Xác định tồn tại hoặc không tồn tại ( E(n) ) cho các ( n \geq 7 ) trong các điều kiện giới hạn.
   • Timeline: 3-5 năm.
   • Chủ thể thực hiện: Cộng đồng nghiên cứu hình học tổ hợp.

3. Ứng dụng các kết quả vào lý thuyết đồ thị và các lĩnh vực liên quan:

   • Động từ hành động: Áp dụng, tích hợp.
   • Target metric: Phát triển các mô hình đồ thị có cấu trúc đa giác lồi.
   • Timeline: 1-2 năm.
   • Chủ thể thực hiện: Nhà nghiên cứu lý thuyết đồ thị và toán ứng dụng.

4. Tổ chức hội thảo chuyên đề về bài toán Erdős-Szekeres và đa giác lồi rỗng:

   • Động từ hành động: Tổ chức, kết nối.
   • Target metric: Tăng cường trao đổi học thuật và hợp tác quốc tế.
   • Timeline: Hàng năm.
   • Chủ thể thực hiện: Các trường đại học và viện nghiên cứu toán học.

Đối tượng nên tham khảo luận văn

1. Sinh viên và nghiên cứu sinh ngành Toán học, đặc biệt chuyên ngành Hình học tổ hợp:

   • Lợi ích: Hiểu sâu về bài toán Erdős-Szekeres, phương pháp chứng minh và các kỹ thuật phân tích hình học.
   • Use case: Làm nền tảng cho các nghiên cứu tiếp theo hoặc luận văn thạc sĩ, tiến sĩ.

2. Giảng viên và nhà nghiên cứu trong lĩnh vực Toán học ứng dụng và Lý thuyết đồ thị:

   • Lợi ích: Áp dụng các kết quả vào nghiên cứu cấu trúc đồ thị, thuật toán và mô hình hóa.
   • Use case: Phát triển các bài giảng, đề tài nghiên cứu mới.

3. Chuyên gia khoa học máy tính quan tâm đến thuật toán hình học:

   • Lợi ích: Nắm bắt các thuật toán tìm đa giác lồi rỗng, cải tiến thuật toán phân tích dữ liệu hình học.
   • Use case: Phát triển phần mềm, ứng dụng trong xử lý hình ảnh, đồ họa máy tính.

4. Nhà toán học lý thuyết và các nhà toán học quan tâm đến các bài toán mở:

   • Lợi ích: Tham khảo các phương pháp chứng minh, đánh giá giới hạn và các giả thuyết mở.
   • Use case: Đề xuất hướng nghiên cứu mới, giải quyết các bài toán chưa được chứng minh.

Câu hỏi thường gặp

1. Giả thuyết Erdős-Szekeres là gì và đã được chứng minh đến đâu?
   Giả thuyết Erdős-Szekeres phát biểu rằng với mỗi ( n \geq 3 ), mọi tập điểm ở vị trí tổng quát với ít nhất ( 2^{n-2} + 1 ) điểm đều chứa ( n ) điểm tạo thành đa giác lồi. Đến nay, giả thuyết này đã được chứng minh cho ( n = 3,4,5,6 ), trong đó trường hợp ( n=6 ) được chứng minh bằng máy tính năm 2006.

2. Sự khác biệt giữa ( ES(n) ) và ( E(n) ) là gì?
   ( ES(n) ) là số điểm tối thiểu để tồn tại đa giác lồi ( n )-đỉnh, không yêu cầu đa giác đó rỗng. Trong khi đó, ( E(n) ) là số điểm tối thiểu để tồn tại đa giác lồi rỗng ( n )-đỉnh, tức đa giác không chứa điểm nào bên trong. Do đó, ( E(n) \geq ES(n) ).

3. Tại sao bài toán về ( E(6) ) lại khó giải hơn các trường hợp khác?
   Trường hợp ( n=6 ) là trường hợp nhỏ nhất mà bài toán vẫn chưa có lời giải chính xác, do cấu trúc phức tạp của các tập điểm và số lượng lớn các trường hợp cấu hình cần phân tích. Việc chứng minh đòi hỏi kỹ thuật phân tích sâu và hỗ trợ tính toán máy tính.

4. Các phương pháp chính được sử dụng để chứng minh các giới hạn của ( E(6) ) là gì?
   Phương pháp chính bao gồm phân tích cấu hình đa giác lồi bao nhau, sử dụng các miền tam giác, tứ giác, ngũ giác để kiểm soát vị trí điểm, áp dụng định lý Ramsey, và sử dụng thuật toán tìm đa giác lồi rỗng lớn nhất kết hợp với tính toán máy tính.

5. Ứng dụng thực tiễn của nghiên cứu về đa giác lồi rỗng là gì?
   Nghiên cứu giúp phát triển các thuật toán xử lý hình ảnh, đồ họa máy tính, phân tích dữ liệu hình học, và mô hình hóa cấu trúc trong lý thuyết đồ thị. Ngoài ra, nó còn góp phần vào việc giải quyết các bài toán mở trong toán học và khoa học máy tính.

Kết luận

• Giả thuyết Erdős-Szekeres và bài toán Erdős về đa giác lồi rỗng là những vấn đề trung tâm trong hình học tổ hợp với nhiều ứng dụng rộng rãi.
• Các giá trị ( ES(n) ) và ( E(n) ) đã được xác định chính xác cho ( n \leq 5 ), trong khi trường hợp ( n=6 ) vẫn còn là thách thức lớn.
• Nghiên cứu đã chứng minh giới hạn ( 30 \leq E(6) \leq 463 ), với đánh giá ( E(6) \leq ES(9) ) là kết quả quan trọng.
• Phương pháp phân tích cấu hình đa giác lồi bao nhau và sử dụng các miền hình học là công cụ hiệu quả trong chứng minh.
• Các bước tiếp theo bao gồm phát triển thuật toán tối ưu, mở rộng nghiên cứu cho các trường hợp lớn hơn và ứng dụng kết quả vào các lĩnh vực liên quan.

Call-to-action: Các nhà nghiên cứu và sinh viên được khuyến khích tiếp tục khám phá bài toán mở này, áp dụng các kỹ thuật mới và công nghệ tính toán để tiến gần hơn đến lời giải hoàn chỉnh.

Trích đoạn nội dung tài liệu

Chương 1 TỔNG QUAN VỀ BÀI TOÁN ERDÖS VỀ ĐA GIÁC LỒI RỖNG 1.1 Bài toán 1 Với mỗi số tự nhiên n ≥ 3 , hãy xác định số nguyên dương nhỏ nhất ES(n) sao cho mọi tập tạo thành từ tối thiểu ES(n) điểm trên mặt phẳng ở vị trí tổng quát phải chứa n điểm là đỉnh của một đa giác lồi. Bài toán 1 được phát biểu vào năm 1935 và sau này được gọi là Bài toán Erdös- Szekeres. Erdös đã 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örgy 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 Bài toán 1a Tồn tại hay không tồn tại số ES(n)? 1.2 Bài toán 1b Nếu số ES(n) tồn tại thì xác định ES(n) như một hàm của n.

Sự tồn tại số ES(n) có thể được chứng minh bằng hai cách. Cách thứ nhất do Szekeres chứng minh không lâu sau khi E. Klein phát biểu bài toán, dựa trên định lí Ramsey (mà Ông đã tự tìm lại do không biết định lí này). Từ đó ta có bất đẳng thức ES(n) ≤ R4 (n, 5) , trong đó R4 (n, 5) là số Ramsey.

Tuy nhiên, đánh giá này là quá lớn so với thực tế. Thí dụ, với n = 5 thì ES(5) ≤ 210000 quá xa so với ES(5) = 9. Cách thứ hai do Erdös chứng minh dựa trên một số quan sát hình học và kết 2n−4 quả ta được một đánh giá tốt hơn ES(n) ≤ Cn−2 + 1. Như vậy, bài toán 1a đã được trả lời khẳng định.

5 TIEU LUAN MOI download : [e-mail] 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. 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 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 Bao lồi của năm điểm là một ngũ giác ABCDE. Khi ấy mọi bộ bốn điểm từ năm điểm ấy đều tạo thành tứ giác lồi (và điểm còn lại nằm ngoài tứ giác lồi đó). Trong 6 TIEU LUAN MOI download : [e-mail] trường hợp này ta có tất cả C54 = 5 tứ giác lồi. Đó chính là các tứ giác ABCD, ABCE, ABDE, ACDE, BCDE.

Tất cả các tứ giác này đều không chứa điểm còn lại (điểm thứ năm nằm bên ngoài tứ giác). Ta gọi các tứ giác lồi này là tứ giác lồi rỗng. Ngoài ra, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E (ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE). Và tất cả các tam giác này đều là các tam giác rỗng.

• Khả năng 2 (Hình 1.3 Bao lồi là một tứ giác chứa một điểm còn lại ở bên trong. Trong trường hợp này ta có một tứ giác lồi (kí hiệu là ABCD) chứa một điểm E ở bên trong. Tứ giác ABCD (chỉ chứa đúng một điểm E ở bên trong) được gọi là tứ giác gần rỗng. Vì không có ba điểm nào thẳng hàng nên E phải nằm về cùng phía với B (hoặc với D) của đường thẳng AC.

Do đó ta có tứ giác AECD (hoặc ABCE) là tứ giác lồi rỗng, còn tứ giác ABCE (hoặc tương ứng AECD) là tứ giác lõm. Tương tự, điểm E phải nằm cùng phía với A (hoặc với C) của đường chéo BD. Khi ấy tứ giác BEDC (hoặc tứ giác ABED) là tứ giác lồi rỗng và tứ giác ABED (hoặc tứ giác BCDE) là tứ giác lõm. Như vậy, trong Trường hợp 2 ta có hai tứ giác lồi rỗng, một tứ giác lồi gần rỗng và hai tứ giác lõm.

Ngoài ra, trong trường hợp này, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E. Đó là các tam giác: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Trong đó tất cả 6 tam giác có đỉnh E đều là tam giác rỗng (không chứa hai điểm còn lại bên trong). Vì khi kẻ đường chéo AC (hoặc BD) của tứ giác lồi ABCD thì do các điểm không thẳng hàng nên E phải nằm trong một trong hai tam giác ABC hoặc ACD (ABD hoặc BCD).

Như vậy ta có hai tam giác gần rỗng (chứa điểm E) và thêm hai tam giác rỗng nữa. • Khả năng 3 (Hình 1.4): 7 TIEU LUAN MOI download : skknchat@gmail.4 Bao lồi chứa ba điểm tạo thành tam giác, thí dụ, ABC. Hai điểm còn lại E và D nằm bên trong tam giác. Do không có ba điểm nào thẳng hàng (các điểm ở vị trí tổng quát) nên hai điểm E và D xác định một đường thẳng chia mặt phẳng tam giác ABC thành hai phần sao cho có hai đỉnh của tam giác ABC, thí dụ, A và B, nằm trên cùng một nửa mặt phẳng mở.

Hai điểm E và D cùng với A và B tạo thành một tứ giác lồi rỗng ABDE. Tứ giác này là tứ giác lồi duy nhất. Bốn tứ giác ABDC, ABEC, BDCE, ADCE còn lại là các tứ giác lõm. Ngoài ra, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E.

Đó là các tam giác: ABC (chứa hai điểm bên trong), ACD và BEC chứa một điểm bên trong (tam giác gần rỗng). Bảy tam giác còn lại ABD, ABE, ACE, ADE, BCD, BDE, CDE là các tam giác rỗng.2 Với chín điểm cho trước ở vị trí tổng quát (không có ba điểm nào thẳng hàng) bao giờ ta cũng tìm được năm điểm tạo thành một ngũ giác lồi. Theo Erdős và Szekeres, công thức ES(5) = 9 đã được Endre Makai chứng minh.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.5, xem [6]) chỉ ra rằng tồn tại tám điểm mà 8 TIEU LUAN MOI download : [e-mail] 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]).2 đã được Hoàng Chúng giới thiệu với bạn đọc Việt Nam trong Toán học và Tuổi trẻ số 4, tháng 2 năm 1967.

Ngay sau đó công thức ES(5) = 9 đã được Đoàn Hữu Dũng chứng minh trong Toán học và Tuổi trẻ số 6 tháng 6, 1967. Hoàn toàn độc lập (nhưng cùng phương pháp) với Đoàn Hữu Dũng, công thức này cũng được chứng minh bởi Bonnice năm 1974. Dưới đây chúng tôi trình bày chứng minh chi tiết công thức ES(5) = 9, kết hợp cả phương pháp hình học, (xem [1]) của Đoàn Hữu Dũng (sử dụng các đa giác lồi bao nhau) và ngôn ngữ cấu hình của Bonnice (xem [3]). Chứng minh (Đoàn Hữu Dũng, 1967; Bonnice, 1974) Lấy bao lồi của 9 điểm bất kỳ.

Gọi mỗi trường hợp (khả năng) có thể xảy ra là một cấu hình. Để phân loại các cấu hình, ta xét các đa giác lồi bao nhau, tức là đầu tiên lấy bao lồi của 9 điểm, bao lồi chỉ có thể là đa giác 9; 8; 7; 6; 5; 4; 3 đỉnh. Các điểm còn lại bên trong bao lồi tương ứng sẽ là 0; 1; 2; 3; 4; 5; 6. Khi số điểm còn lại bên trong bao lồi lớn hơn 3, ta lại lấy bao lồi của các điểm này để được các đa giác lồi.

Chỉ có duy nhất một trường hợp ba tam giác bao nhau. Các trường hợp còn lại chỉ có thể là hai hoặc một đa giác bao nhau (có thể chứa một hoặc hai điểm trong). Ta được tất cả 12 cấu hình khác nhau sau đây: Trường hợp 1 (Hình 1.6a) Cấu hình (9;0): Bao lồi là đa giác lồi 9 đỉnh. Mọi tập năm đỉnh đều tạo thành ngũ giác lồi (thậm chí lồi rỗng).

Trường hợp 2 (Hình 1.6b) Cấu hình (8;1): Bao lồi là đa giác lồi 8 đỉnh, một điểm còn lại nằm trong đa giác. Do không có ba điểm nào thẳng hàng nên năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng hoặc chứa một điểm trong). Trường hợp 3 (Hình 1.6c) Cấu hình (7;2): Bao lồi là đa giác lồi 7 đỉnh, hai điểm còn lại nằm trong đa giác. Do không có ba điểm nào thẳng hàng nên năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng, chứa một hoặc hai điểm trong).

9 TIEU LUAN MOI download : skknchat@gmail.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).7 Các cấu hình (6,3), (5,4), (4,5) Hình 1.8 Các cấu hình (3,6), (3,5,1) 10 TIEU LUAN MOI download : [e-mail] 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.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.