Một số tính chất tổ hợp của đa giác lồi
Trong phần này, chúng tôi sẽ giới thiệu một số tính chất tổ hợp của đa giác lồi, bắt đầu bằng việc định nghĩa tập lồi Tập lồi trong mặt phẳng, trên đường thẳng hoặc trong không gian được định nghĩa là tập hợp U gồm các điểm có đặc điểm rằng, với bất kỳ hai điểm phân biệt X và Y thuộc U, mọi điểm trên đoạn thẳng nối X và Y cũng sẽ thuộc U.
Tập lồi trên đường thẳng có cấu trúc đơn giản bao gồm các tia, đoạn thẳng và các điểm, ngoại trừ đường thẳng và tập rỗng Mặc dù việc phân loại các tập lồi trong mặt phẳng là một thách thức, nhưng giao của các tập lồi luôn tạo thành một tập lồi Một khái niệm quan trọng là bao lồi K của tập U, được định nghĩa là giao của tất cả các tập lồi M mà trong đó U thuộc về M, do đó K là tập lồi nhỏ nhất chứa U.
Tập K = {A1, A2, , An} là tập hợp n điểm phân biệt trong mặt phẳng, với n ≥ 3 Tập M được gọi là n-giác lồi A1A2 An nếu M là giao của n nửa mặt phẳng α1, α2, , αn Mỗi nửa mặt phẳng αi chứa đường thẳng Aiai+1 (với An+1 = A1) là biên của nó, đảm bảo rằng các điểm A1, A2, , An tạo thành một hình đa giác lồi.
Nếu U là một tập hợp hữu hạn gồm n điểm (với n ≥ 3) trong mặt phẳng và các điểm này không nằm trên cùng một đường thẳng, thì bao lồi của U sẽ tạo thành một đa giác lồi Đa giác này có các đỉnh là một số hoặc tất cả các phần tử của tập hợp U.
Định lý Helly là một kết quả quan trọng trong lý thuyết tập lồi, cho rằng nếu S là một hệ bất kỳ các tập con lồi trong một mặt phẳng, và ba tập hợp bất kỳ trong S có ít nhất một điểm chung, thì tất cả các tập con trong S đều có điểm chung.
Hai tính chất cơ bản sau đây của đa giác lồi sẽ được sử dụng thường xuyên ở chương này.
Tính chất 1.1.4 Số đường chéo u n của n-giác lồi M thỏa mãn u n = n(n − 3)
Chứng minh Thật vậy,n đỉnh của đa giácM được nối với nhau bởi n 2
= n(n−1) 2 đoạn thẳng, trong đó có đúng n đoạn là các cạnh của đa giác M Do đó ta có u n = n(n−1) 2 − n = n(n−3) 2
Một cách tính số đường chéo của đa giác M là dựa vào số đỉnh của nó Mỗi đỉnh sẽ tạo ra n - 3 đường chéo, và khi tổng hợp tất cả n đỉnh, các đường chéo sẽ được đếm hai lần Do đó, công thức tính số đường chéo là u_n = n(n - 3) / 2.
Tính chất 1.1.5 Tổng S n các góc trong một n-giác lồi thỏa mãn
Chúng ta sẽ chứng minh công thức tổng các góc trong của đa giác bằng phương pháp quy nạp toán học Bắt đầu với trường hợp n = 3, công thức đã biết là tổng các góc trong của tam giác A1A2A3 Giả sử công thức đúng với n, chúng ta sẽ chứng minh nó đúng với n + 1 Bằng cách chia đa giác lồi A1A2 An+1 theo đường chéo A1A3, ta có tam giác A1A2A3 và n-góc lồi A1A3 An+1 Tổng các góc trong của n-góc lồi là Sn = (n - 2) × 180° Tổng các góc trong của đa giác A1A2 An+1 sẽ là Sn+1 = 180° + Sn = 180° + (n - 2) × 180° = (n - 1) × 180°.
Một cách tính khác: Đa giác M = A 1 A 2 A n có thể chia bởi n − 3 cạnh
A 1 A k (k = 3, 4, , n − 1) thành n − 2 tam giác, và tổng các góc trong của n − 2 tam giác này bằng S n
Mệnh đề 1.1.6 Tồn tại một n-giác lồi M (n ≥ 3) sao cho ba đường chéo bất kì của M không đồng quy.
Chúng ta sẽ chứng minh rằng tồn tại một n-giác lồi M nội tiếp một đường tròn và không có ba đường chéo nào đồng quy bằng phương pháp quy nạp toán học.
Với n ≤ 5, n-giác lồi là n-giác lồi thông thường, khẳng định của mệnh đề là đúng Khi n > 6, giả sử n-giác lồi M n = A 1 A 2 A n nội tiếp đường tròn C và không có ba đường chéo nào đồng quy Tập hợp P gồm tất cả các đường thẳng nối các giao điểm của các đường chéo của đa giác M n có hữu hạn đường thẳng và hữu hạn giao điểm với đường tròn C Do đó, tồn tại một điểm.
A n+1 nằm trên đường tròn C và không nằm trên bất kì đường thẳng nào thuộc
Điểm A n+1 có thể được lựa chọn trên cung tròn giới hạn bởi A 1 và A n, mà không chứa các điểm A 2, A 3, …, A n−1 Khi đó, chuỗi điểm A 1, A 2, …, A n, A n+1 sẽ tạo thành một (n + 1)-giác lồi, trong đó không có ba đường chéo nào đồng quy.
Mệnh đề 1.1.7 khẳng định rằng, với n điểm (n ≥ 4) trên mặt phẳng, nếu không có ba điểm nào thẳng hàng và bất kỳ bốn điểm nào cũng tạo thành đỉnh của một tứ giác lồi, thì n điểm đó sẽ là đỉnh của một n-giác lồi.
Chứng minh GọiS là tập hợp các điểm đã cho và giả sử bao lồi của S là k-giác
M sẽ chứng minh rằng mọi điểm X ∈ S đều là đỉnh của M Giả sử tồn tại một điểm Y ∈ S nằm bên trong k-giác M Từ một đỉnh Z tùy ý của M, ta vẽ tất cả các đường chéo nối với đỉnh Z, dẫn đến việc k-giác M được chia thành k - 2 tam giác, trong đó điểm Y sẽ nằm trong một tam giác nào đó Giả sử tam giác đó là ABC, khi đó bốn điểm A, B, C, Y không tạo thành tứ giác lồi, điều này mâu thuẫn với giả thiết ban đầu.
Chọn một điểm P bất kỳ trong đa giác lồi M và tiến hành dựng các hình chiếu vuông góc từ P lên các đường thẳng chứa các cạnh của M Kết quả là, ít nhất một trong các hình chiếu này sẽ nằm trên cạnh của M.
Chúng ta sẽ chứng minh rằng trong tất cả các đường thẳng chứa cạnh của đa giác M, có một đường thẳng có khoảng cách nhỏ nhất đến điểm P, được ký hiệu là ` Giả sử cạnh AB nằm trên đường thẳng này, chúng ta sẽ chứng minh rằng hình chiếu vuông góc Q của P lên ` nằm trên đoạn thẳng AB Nếu Q không nằm trên AB, tức là Q thuộc ` nhưng không thuộc AB, thì đoạn thẳng PQ sẽ nối một điểm bên trong với một điểm bên ngoài đa giác M, và giả sử PQ cắt cạnh CD tại điểm R Do đó, ta có |PR| < |PQ|.
Hình 1.1: nên khoảng cách từ P đến CD nhỏ hơn khoảng cách từ P đến `, điều này mâu thuẫn với cách chọn ` (Kí hiệu |P Q| là độ dài đoạn thẳng P Q).
Bài toán 1.1.9 Cho n-giác đều (n ∈N , n ≥ 3) Tìm n biết rằng số đường chéo của n-giác đều là 27.
Lời giải Từ Tính chất 1.1.4 ta được u n = n(n − 3)
n = 9 (nhận) n = −6 (loại)Vậy n-giác đều cần tìm là 9-giác đều.
Đếm số giao điểm
Trong phần này chúng tôi trình bày một số bài toán về xác định số giao điểm trong hệ đoạn thẳng, đường thẳng và đường tròn.
Mệnh đề 1.2.1 Một đường gấp khúc khép kín gồm 2n + 1 đoạn thẳng (n ≥ 1) có thể tự cắt nhau tại nhiều nhất (2n + 1)(n − 1) điểm.
Trong một đoạn AB thuộc đường gấp khúc, số giao điểm tối đa có thể là 2n − 2, do AB không bị cắt bởi hai đoạn kề Từ đó, ta có thể ước tính số lượng giao điểm k với công thức: k ≤ (2n+1)(2n−2).
Ta có thể tạo ra một đường gấp khúc khép kín với số giao điểm chính xác là (2n + 1)(n − 1) Xem xét đa giác A1, A2, , A2n+1, trong đó không có ba đường chéo nào đồng quy bên trong Khi đó, đường gấp khúc A1, An+1, A2n+1, An, A2n, An−1, , A2, An+2, A1 sẽ có đúng (2n + 1)(n − 1) giao điểm.
Mệnh đề 1.2.2 Cho n-giác lồi A 1 A 2 A n không có ba đường chéo nào đồng quy Khi đó số giao điểm của các đường chéo trong n-giác lồi là n 4
Để chứng minh, ta xem xét đường chéo cố định A1Ak (với k = 3, 4, , n - 1) và xác định số giao điểm của nó với các đường chéo khác Đường thẳng A1Ak chia mặt phẳng thành hai nửa, trong đó một nửa chứa (k - 2) đỉnh của đa giác, còn nửa kia chứa (n - k) đỉnh Do đó, đường chéo A1Ak cắt các đường chéo khác tại (n - k)(k - 2) điểm Số giao điểm tổng quát trên tất cả các đường chéo xuất phát từ A1 được ký hiệu là a1(n) và có công thức a1(n) = n - 1.
Khi cộng số giao điểm của tất cả các đỉnh trong một đa giác, mỗi giao điểm sẽ được đếm 4 lần Do đó, tổng số giao điểm A(n) của các đường chéo trong đa giác được xác định dựa trên công thức này.
Một cách tính khác cho số giao điểm của hai đường chéo trong một n-góc là dựa vào bốn đỉnh tương ứng của nó Số giao điểm này chính là số cách chọn bốn đỉnh trong tổng số n đỉnh của n-góc, do đó có n 4 giao điểm.
Bài toán 1.2.3 đề cập đến năm điểm trong mặt phẳng, trong đó không có hai đoạn thẳng nối hai điểm bất kỳ nào song song hoặc vuông góc với nhau Từ mỗi điểm, ta dựng đường vuông góc với tất cả các đoạn thẳng đã nêu Kết quả là số giao điểm của hệ này không vượt quá 310.
Lời giải Số đoạn thẳng tạo bởi năm điểm đã cho là 5 2
Trong bài viết này, chúng ta sẽ phân tích một tình huống hình học với 10 điểm, mỗi điểm là điểm đầu của bốn đoạn thẳng Từ mỗi điểm, có sáu đường thẳng vuông góc với các đường thẳng nối các điểm khác Đầu tiên, chúng ta sẽ xem xét hai điểm bất kỳ trong số năm điểm đã cho, giả sử là A và B, và đếm số giao điểm của các đường thẳng vuông góc từ A với các đường thẳng vuông góc từ các điểm khác, được ký hiệu là C, D và E Chúng ta sẽ chia sáu đường vuông góc từ A thành hai nhóm để tiếp tục phân tích.
Ba đường thẳngp 1 , p 2 , p 3 vuông góc với các đường thẳngBC, BD, BE; Các đường thẳng này cắt sỏu đường vuụng gúc kẻ từ B tại 3 ã 6 = 18 giao điểm.
Ba đường thẳng q1, q2, q3 được kẻ từ điểm A vuông góc với các đường CD, CE, DE, giao với năm trong số sáu đường thẳng vuông góc kẻ từ điểm B Điều này xảy ra vì có một đường vuông góc từ B song song với q1, q2 hoặc q3 Từ đó, ta có thêm 15 giao điểm khác.
Suy ra các đường vuông góc từ A và B cắt nhau tại 18 + 15 = 33 giao điểm. Người ta có thể chọn hai trong năm điểm đã cho theo 5 2
= 10 cách, vì vậy số giao điểmp khụng được vượt quỏ10 ã 33 = 330 Chỳ ý rằng năm điểm đó cho tạo thành đỉnh của 5 3
= 10 tam giác, trong đó ba đường cao đồng quy Vì vậy ta được p ≤ 330 − 2 ã 10 = 310.
Trong mặt phẳng, với n ≥ 3 điểm cho trước, không có hai đoạn thẳng nối hai điểm bất kỳ nào song song hoặc vuông góc với nhau Từ mỗi điểm, ta dựng đường vuông góc với tất cả các đoạn thẳng đã vẽ Số giao điểm của hệ thống này sẽ không vượt quá một giới hạn nhất định.
Chứng minh Số đoạn thẳng tạo bởinđiểm đã cho là n 2
Trong một tập hợp gồm n điểm, số đường thẳng vuông góc có thể được tạo ra từ mỗi điểm là n(n−1)/2, với mỗi điểm là điểm đầu của (n−1) đoạn thẳng Từ mỗi điểm, ta có thể vẽ (n−1)(n−2)/2 đường thẳng vuông góc với các đường thẳng nối các điểm khác Để hiểu rõ hơn, hãy xem xét hai điểm bất kỳ trong số n điểm, giả sử là A và B, và đếm số giao điểm của các đường thẳng vuông góc từ A với các đường thẳng vuông góc từ các điểm còn lại, được ký hiệu là X1, X2, , Xn−2 Chúng ta sẽ chia (n−1)(n−2)/2 đường vuông góc từ A thành hai nhóm khác nhau.
Các đường thẳng p 1 , p 2 , , p n−2 vuông góc với các đường thẳng
BX 1 , BX 2 , , BX n−2 ; (n − 2) đường thẳng này cắt (n−1)(n−2) 2 đường vuông góc kẻ từ B tại (n − 2) ã (n−1)(n−2) 2 = n 3 −5n 2 2 +8n−4 giao điểm.
2 −(n −2) = n 2 −5n+6 2 đường vuông góc còn lại kẻ từAgiao với (n−1)(n−2) 2 −
1 = n 2 −3n 2 đường thẳng vuụng gúc kẻ từ B Từ đú ta cú thờm n 2 −5n+6 2 ã n 2 −3n 2 = n 4 −8n 3 +21n 2 −18n
Suy ra các đường vuông góc từ A và B cắt nhau tại n 3 −5n 2 +8n−4
Số giao điểm của phương trình \(2 + n^4 - 8n^3 + 21n^2 - 18n = n^4 - 6n^3 + 11n^2 - 2n - 8\) có thể được xác định bằng cách chọn hai trong số n điểm đã cho, với tổng số cách chọn là \(\frac{n(n-1)}{2}\) Do đó, số giao điểm không vượt quá \(n^4 - 6n^3 + 11n^2 - 2n - 8\) và có thể được tính bằng biểu thức \(n(n-1)/2 = n^6 - 7n^5 + 17n^4 - 13n^3 - 6n^2 + 8n\) Lưu ý rằng n điểm này có thể tạo thành đỉnh của một hình đa diện với n mặt.
= n 3 −3n 6 2 +2n tam giác, trong đó ba đường cao đồng quy.
Đếm tam giác
Một bài toán cổ điển trong hình học tổ hợp là xác định số lượng tam giác có đỉnh hoặc cạnh nằm trong một tập hợp gồm n phần tử đã cho.
Mệnh đề 1.3.1 Trên mỗi cạnh của một tứ giác lồi chọnn điểm phân biệt Khi đó có 2n 2 (5n − 3) tam giác có đỉnh thuộc 4n điểm ấy.
Từ 4n điểm cho trước, có thể chọn được 4n 3 bộ ba điểm phân biệt Tuy nhiên, cần lưu ý rằng có 4 trường hợp bộ ba điểm có thể nằm trên cùng một cạnh của tứ giác.
Do đó số tam giác chọn được là 4n 3
Mỗi tam giác có thể thuộc một trong hai loại: loại thứ nhất là khi mỗi đỉnh của tam giác nằm trên ba cạnh khác nhau của tứ giác, và loại thứ hai là khi hai đỉnh của tam giác nằm trên cùng một cạnh của tứ giác trong khi đỉnh thứ ba nằm trên một cạnh khác Số lượng tam giác thuộc loại thứ nhất là 4n^3 và số lượng tam giác thuộc loại thứ hai là 4n^3 - 4n^2 Tổng số tam giác được tính là 4n^3 + 4n^3 - 4n^2 = 2n^2(n - 3).
Mệnh đề 1.3.2 Cho n-giác lồi M (n ≥ 6) Khi đó có n(n−4)(n−5)
6 tam giác có đỉnh là đỉnh của M và cạnh là đường chéo của M.
Để chứng minh số tam giác có đỉnh thuộc đa giác M, ta trừ đi số tam giác có một hoặc hai cạnh là cạnh của M Có n(n − 4) tam giác với một cạnh là cạnh của M, vì mỗi cạnh trong n cạnh của M cho phép chọn đỉnh thứ ba theo n − 4 cách Ngoài ra, có n tam giác với hai cạnh là cạnh của M, vì mỗi tam giác như vậy gồm hai cạnh kề và được xác định duy nhất bởi đỉnh chung của chúng Do đó, số tam giác có đỉnh là đỉnh của M và cạnh là đường chéo của M được tính như sau.
Mệnh đề 1.3.3 Cho n-giác lồi M không có ba đường chéo nào đồng quy Khi đó có n(n−1)(n−2)
6 ã n 3 +18n 120 2 −43n+60 tam giỏc cú cạnh nằm trờn cỏc cạnh hoặc đường chéo của M.
Chúng ta chia tập hợp P(n) các tam giác thành các lớp S0, S1, S2, S3, với mỗi lớp Si chứa các tam giác có đúng i đỉnh trong số các đỉnh của M (i = 0, 1, 2, 3) Rõ ràng rằng số lượng tam giác trong lớp S3 là |S3| = n3.
Mỗi tam giác trong lớp S 2
Hình 1.3: có hai đỉnh thuộc M, giả sử B 1 , B 2 , và đỉnh thứ ba của tam giác là giao điểm của hai đường chéo B 1 B 3 và B 2 B 4 (Hình 1.3(a)) Nếu chúng ta chọn bốn đỉnh
B 1 , B 2 , B 3 , B 4 từ các đỉnh của M thì ta được chính xác bốn hình tam giác thuộc
Bằng cỏch lập luận tương tự ta được|S 1 | = 5 ã n 5
Trong một tập hợp S gồm n (n ≥ 3) điểm phân biệt trên mặt phẳng, với điều kiện không có ba điểm nào thẳng hàng, có ít nhất n(n−2) tam giác được tạo thành với các đỉnh thuộc S, mà không chứa bất kỳ điểm nào khác trong S.
Để chứng minh, từ tập S, ta chọn hai điểm bất kỳ X và Y Xét nửa mặt phẳng α có bờ là đường thẳng XY, trong đó α chứa nhiều hơn một điểm của S Gọi Z là điểm có khoảng cách ngắn nhất tới XY trong nửa mặt phẳng α Khi đó, tam giác XY Z sẽ "rỗng", tức là không chứa bất kỳ điểm nào thuộc S Điều này được chứng minh bằng cách phản.
Hình 1.4 chứng minh sự tồn tại của điểm A thuộc tập S nằm trong tứ giác 4XY Z Giả sử dA và dZ lần lượt là khoảng cách từ A đến XY và từ Z đến XY Khi đó, diện tích tứ giác 4AXY nhỏ hơn diện tích tứ giác 4ZXY, tức là dA < dZ (Hình 1.4(a)), điều này dẫn đến mâu thuẫn với cách chọn điểm Z.
Trong không gian hai chiều, có tối đa n cặp điểm X, Y thuộc tập S sao cho toàn bộ tập S nằm hoàn toàn trong một trong hai nửa mặt phẳng được giới hạn bởi đường thẳng XY, điều này xảy ra khi X và Y là hai đỉnh kề của bao lồi của S Đối với mỗi cặp X, Y như vậy, có ít nhất một tam giác 4XY Z (với Z thuộc S) là "rỗng" Đối với mỗi cặp X, Y khác, điều này cũng tương tự.
− n cặp) có ít nhất hai tam giác "rỗng" Nếu chúng ta cộng các số này với tất cả các cặp X, Y ta được ít nhất n + 2h n 2
= n(n − 2) tam giác "rỗng", và mỗi tam giác được tính ít nhất ba lần Vậy ta có ít nhất n(n−2) 3 tam giác thỏa yêu cầu bài toán.
Mệnh đề 1.3.5 Trong mặt phẳng cho 3n điểm (n ≥ 1) sao cho không có ba điểm nào thẳng hàng Khi đó các điểm này là đỉnh của n tam giác rời nhau.
Sử dụng phương pháp quy nạp toán học, chúng ta chứng minh rằng với n = 1, khẳng định của mệnh đề là đúng Giả sử khẳng định đúng với n = k, ta sẽ chứng minh cho n = k + 1 Xét 3k + 3 điểm trong mặt phẳng mà không có ba điểm nào thẳng hàng, bao lồi của các điểm này tạo thành đa giác A1A2 As (với 3 ≤ s ≤ 3k + 3) Có hai trường hợp được xem xét: Thứ nhất, với tam giác A1A2A3 và 3k điểm còn lại, nếu tất cả các điểm này nằm trong nửa mặt phẳng không chứa A2, theo giả thiết quy nạp, chúng tạo thành k tam giác rời nhau, cộng với A1A2A3, ta có (k + 1) tam giác rời nhau Thứ hai, chọn một điểm B từ 3k điểm sao cho góc BA1A2 là nhỏ nhất, nửa mặt phẳng có bờ là A1B không chứa A2 sẽ chứa 3k điểm, theo giả thiết cũng tạo thành k tam giác rời nhau, cùng với A1A2B, ta có (k + 1) tam giác rời nhau.
Một cách chứng minh khác là vẽ tất cả các đường thẳng nối hai điểm bất kỳ trong số 3n điểm đã cho, sau đó chọn một hướng khác với tất cả các hướng của các đường đã vẽ Qua mỗi điểm trong 3n điểm, ta kẻ một đường thẳng theo hướng đã chọn, từ đó tạo thành một hệ gồm 3n đường thẳng song song phân biệt Các đường song song này được chia thành n bộ ba gần nhau, với các điểm trên mỗi đường thuộc cùng một bộ ba tạo thành đỉnh của các tam giác rời nhau.
Phương pháp song song có thể áp dụng để giải bài toán liên quan đến tổng các số nguyên dương k1, k2, , kn bằng N Cần chứng minh rằng bất kỳ tập hợp nào gồm N phần tử trong mặt phẳng đều có thể được phân chia thành n lớp, với số phần tử tương ứng là k1, k2, , kn, sao cho các bao lồi của từng lớp là rời rạc.
Đếm đa giác
Trong bài viết này, chúng tôi nghiên cứu bài toán đếm số k-giác có đỉnh từ n điểm đã cho, với điều kiện 4 ≤ k ≤ n Đặc biệt, chúng tôi tập trung vào bài toán Cayley liên quan đến số k-giác lồi, trong đó các đỉnh là đỉnh của một n-giác lồi và các cạnh là đường chéo của n-giác đó.
Mệnh đề 1.4.1 (Cayley) Cho n-giác lồi M và số k thỏa 3 ≤ k ≤ n 2 Khi đó có n(n−k−1)! k!(n−2k)! k-giác lồi có đỉnh là đỉnh của M và cạnh là đường chéo của M.
Giả sử M là n-giác A1, A2, , An, chúng ta sẽ xác định số lượng k-giác có đỉnh là An−1 Kí hiệu các đỉnh còn lại của k-giác là Ai1, Ai2, , Aik−1, với các chỉ số i1, i2, , ik−1 thỏa mãn 1 ≤ i1 < i2 < < ik−1 ≤ n − 3 và các điều kiện i2 − i1 ≥ 2, i3 − i2 ≥ 2, , ik−1 − ik−2 ≥ 2 Do đó, (k − 1) chỉ số có thể được chọn theo công thức n−k−1 chọn k−1, dẫn đến số lượng k-giác thỏa mãn yêu cầu với đỉnh An−1 là n−k−1 chọn k−1.
Cộng số này cho tất cả các đỉnh của M thì mỗi k-giác đã được đếm k lần, vậy số c(k, n) k-giác thỏa yêu cầu là c(k, n) = n k ã n − k − 1 k − 1
6 , điều này đã được chứng minh ở Mệnh đề 1.3.2.
Trong việc giải quyết các bài toán Hình học tổ hợp, chúng ta thường áp dụng phương pháp Tạo đa giác để bao quanh một tập hợp hữu hạn các điểm bằng một đa giác hoặc một góc.
Bổ đề 1.4.3 khẳng định rằng với n điểm hữu hạn không nằm trên một đường thẳng, luôn tồn tại một đa giác lồi được tạo thành từ các điểm này Đặc biệt, các điểm còn lại sẽ nằm bên trong đa giác, không bị nằm ngoài.
Để chứng minh, vì số điểm đã cho là hữu hạn, ta có thể xác định một đường tròn với bán kính đủ lớn để bao quanh tất cả các điểm này Tiếp theo, ta vẽ một đường thẳng l nằm ngoài đường tròn Gọi A1 là điểm gần nhất với đường thẳng l; nếu có nhiều điểm, chọn A1 là điểm cuối ở bên phải Từ A1, ta kẻ một đường thẳng d song song với l.
Quay đường thẳng d quanh điểm A1 theo hướng ngược chiều kim đồng hồ cho đến khi gặp một điểm đã cho, ta sẽ có đường thẳng d1 Điểm gặp được gọi là A2, và nếu có nhiều điểm thuộc d1, A2 sẽ là điểm xa A1 nhất.
Bằng cách quay đường thẳng d1 quanh điểm A2, ta tạo ra đường thẳng d2 và tiếp tục quá trình này cho đến khi thu được đường thẳng đi qua A1, được gọi là dm Kết quả là một đa giác lồi A1 A2 Am đáp ứng yêu cầu của bài toán.
Chú ý 1.4.4 Đa giác lồi được tạo thành theo cách trên gọi là đa giác bao n điểm đã cho.
Bổ đề 1.4.5 về góc bao khẳng định rằng, với n điểm hữu hạn không nằm trên cùng một đường thẳng, luôn tồn tại một góc nhỏ hơn góc bẹt với đỉnh là một trong những điểm đó, sao cho tất cả các điểm còn lại nằm trong miền của góc.
Chứng minh Lập luận cách giải tương tự Bổ đề 1.4.3, ta thu được góc A\ 2 A 1 A m là góc phải tìm.
Bài toán 1.4.6 yêu cầu chọn bốn trong năm điểm trên mặt phẳng, với điều kiện không có ba điểm nào thẳng hàng, để tạo thành một tứ giác lồi Kết quả cho thấy có tối đa năm tứ giác lồi có thể được hình thành từ năm điểm này.
Kí hiệu S là tập hợp các điểm đã cho, trong khi K là bao lồi của S Có thể có các trường hợp khác nhau, trong đó K có thể là một ngũ giác Khi K là ngũ giác, mọi tứ giác có đỉnh thuộc S đều là tứ giác lồi và có 5 đỉnh.
Trong bài viết này, chúng ta sẽ khám phá về tứ giác lồi và cách xác định vị trí của các điểm trong tứ giác K được định nghĩa là tứ giác lồi A1 A2 A3 A4, với đỉnh A5 nằm trong khu vực S và bên trong tứ giác K Khi P là giao điểm của hai đường chéo A1 A2 và A3 A4, A5 sẽ trở thành điểm nằm trong một trong bốn tam giác: A1 A2 P, A2 A3 P, A3 A4 P, hoặc A1 A4 P.
A 5 ∈ 4A 1 A 2 P Khi đó ta có chính xác ba tứ giác lồi đó là A 1 A 2 A 3 A 4 , A 1 A 5 A 3 A 4
Hình 1.6 mô tả tam giác K với các đỉnh A1, A2, A3, trong khi hai đỉnh A4 và A5 nằm trong K Các đường thẳng A1A4, A2A4, A3A4 cắt các cạnh của K tại các điểm B1, B2, B3, chia K thành sáu tam giác, trong đó A5 là điểm trong của một trong số đó Giả sử A5 thuộc tứ giác A1A4B3, bốn điểm A1, A3, A4, A5 tạo thành một tứ giác lồi.
Hệ điểm và đường thẳng
Trong nghiên cứu này, chúng tôi tập trung vào các vấn đề liên quan đến hệ hữu hạn điểm và đường thẳng trong mặt phẳng Một trong những phương pháp chính được áp dụng là Nguyên lý cực hạn, cho thấy rằng trong một tập hợp hữu hạn các số thực không rỗng, luôn tồn tại số nhỏ nhất và số lớn nhất.
Nhờ nguyên lý này ta có thể xét các phần tử mà một đại lượng nào đó có giá trị nhỏ nhất hoặc lớn nhất.
Mệnh đề 1.5.1 (Sylvester - Gallai) khẳng định rằng trong một tập hợp hữu hạn các điểm S trên mặt phẳng, nơi không có ba điểm nào cùng nằm trên một đường thẳng, luôn tồn tại ít nhất một đường thẳng chỉ chứa hai điểm thuộc tập hợp S.
Chứng minh rằng tập hợp L bao gồm các đường thẳng hữu hạn đi qua ít nhất hai điểm trong tập S Để thực hiện điều này, ta cần xem xét các khoảng cách từ một điểm thuộc S đến các đường thẳng trong L.
Hình 1.7: thuộc L, ta xét khoảng cách dương nhỏ nhất và giả sử đó là khoảng cách từ
Cho A thuộc tập S và l thuộc tập L Gọi B là hình chiếu của A lên l, khi đó đường thẳng l chia thành hai tia gốc tại B Chúng ta sẽ chứng minh rằng trên mỗi tia có nhiều nhất một điểm thuộc S Giả sử một trong hai tia gốc B chứa hai điểm C1 và C2 thuộc S.
Trong tam giác 4AC1C2, với điều kiện 0 ≤ |BC1| ≤ |BC2|, tam giác này có thể là tam giác tù hoặc tam giác vuông (khi B ≡ C1), với góc lớn nhất tại C1 Điều này dẫn đến việc |C1C2| < |AC2| Bằng cách tính diện tích của tam giác 4AC1C2 theo hai phương pháp khác nhau, ta có thể suy ra khoảng cách từ
C 1 đếnAC 2 nhỏ hơn khoảng cách từA đếnl Điều này mâu thuẫn với cách chọn
A và l Vì vậy có đúng hai điểm thuộc S trên đường thẳng l.
Trong bài toán 1.5.2, cho 10 đường thẳng không song song, với điều kiện rằng qua giao điểm của bất kỳ hai đường thẳng nào trong số đó luôn có ít nhất một đường thẳng còn lại đi qua Điều này dẫn đến kết luận rằng tất cả 10 đường thẳng này đều đồng quy.
Giả sử rằng 10 đường thẳng không đồng quy Xét đường thẳng d, nếu có một hoặc nhiều giao điểm của hai đường thẳng đã cho không nằm trên d, ta gọi A là điểm gần d nhất Theo giả thiết, qua điểm A có ít nhất ba đường thẳng.
Ba đường thẳng cắt nhau tại ba điểm B, C, và D, trong đó điểm C nằm giữa B và D Do không có hai đường thẳng nào song song, mỗi đường thẳng đều tạo ra các giao điểm khác nhau.
Theo giả thiết, tồn tại một đường thẳng cắt đoạn thẳng AD tại điểm E, nằm giữa A và D Khi đó, khoảng cách từ E đến đường thẳng d sẽ nhỏ hơn khoảng cách từ A đến d, điều này tạo ra mâu thuẫn với cách chọn điểm A và đường thẳng d Do đó, có thể kết luận rằng 10 đường thẳng này đồng quy.
Trong mặt phẳng, với một tập hữu hạn S chứa n ≥ 3 điểm không thẳng hàng, khi xét các đường thẳng nối giữa hai điểm trong S, sẽ có ít nhất n đường thẳng phân biệt được hình thành.
Chúng ta sẽ chứng minh mệnh đề bằng phương pháp quy nạp toán học Đầu tiên, với n = 3, khẳng định của mệnh đề là đúng Giả sử khẳng định đúng với n = k (k ≥ 4), chúng ta sẽ chứng minh cho n = k + 1 Theo Mệnh đề 1.5.1, trong số các đường thẳng nối hai điểm thuộc S, tồn tại một đường thẳng chỉ chứa hai điểm A và B ∈ S Xét điểm A và đặt S0 = S\{A} Có hai trường hợp xảy ra: Nếu tất cả k điểm thuộc S0 nằm trên một đường thẳng l, ta có hệ gồm (k + 1) đường thẳng phân biệt {AX : X ∈ S0} ∪ {l} Ngược lại, theo giả thiết quy nạp, sẽ có ít nhất k đường thẳng phân biệt nối hai điểm thuộc S0 mà không có đường thẳng nào trùng với đường thẳng AB, vì đường thẳng AB chỉ chứa hai điểm thuộc S.
Bài toán 1.5.4 Cho bốn điểm không thẳng hàng trong mặt phẳng. i) Từ bốn điểm ấy ta có thể chọn ra một tam giác có một góc không vượt quá
45 ◦ ii) Tồn tại một hệ bốn điểm như vậy sao cho không có tam giác nào có góc nhỏ hơn 45 ◦
Lời giải i) Ta xét hai trường hợp bao lồi của bốn điểm đã cho.
Trường hợp 1: Bao lồi là tam giác4A 1 A 2 A 3 và điểmA 4 nằm bên trong4A 1 A 2 A 3 (Hình 1.9(a)) Khi đó các đoạn thẳng A 1 A 4 , A 2 A 4 , A 3 A 4 chia các góc trong của
4A 1 A 2 A 3 thành sáu góc nhỏ, trong đó có ít nhất một góc không lớn hơn 180 6 ◦ =
Trong trường hợp 2, bao lồi là tứ giác A1 A2 A3 A4, trong đó bốn góc nội tại được chia bởi hai đường chéo thành tám góc nhỏ Ít nhất một trong số tám góc này không lớn hơn 45 độ Tình huống này xảy ra khi bốn điểm đã cho tạo thành đỉnh của một hình chữ nhật.
Mệnh đề 1.5.5 Cho n ≥ 3 điểm không thẳng hàng trong mặt phẳng. i) Từ n điểm ấy ta có thể chọn ra một tam giác có một góc không vượt quá
. ii) Tồn tại một hệ n điểm như vậy sao cho không có tam giác nào có góc nhỏ hơn
Để chứng minh, chúng ta có thể áp dụng lập luận tương tự như trong Bài toán 1.5.4, từ đó xác định các trường hợp bao lồi của n điểm đã cho Điều này sẽ dẫn đến việc chứng minh được kết quả cần thiết Hơn nữa, điều này xảy ra khi n điểm đã cho tạo thành đỉnh của một n-giác đều.
Cho 10 điểm trên mặt phẳng, với điều kiện rằng trong bất kỳ bốn điểm nào cũng luôn có ba điểm thẳng hàng Dựa vào điều này, ta có thể loại bỏ một điểm trong số 10 điểm đã cho, để chín điểm còn lại nằm trên cùng một đường thẳng.
Lời giải Nếu tất cả 10 điểm cùng thuộc một đường thẳng thì bài toán được chứng minh.
Giả sử không phải cả 10 điểm đều nằm trên một đường thẳng, ta chọn bốn điểm A, B, C, D mà không phải tất cả thẳng hàng Theo giả thiết, trong bốn điểm này, A, B, C phải nằm trên một đường thẳng d, trong khi D không nằm trên d Chúng ta sẽ chứng minh rằng sáu điểm còn lại cũng thuộc đường thẳng d.
Hệ đoạn thẳng
Trong bài viết này, chúng tôi sẽ khám phá một số tính chất tổ hợp của hệ hữu hạn đoạn thẳng nằm trên một đường thẳng, cũng như các dây cung của một đường tròn.
Bài toán 1.6.1 Cho 50 đoạn thẳng cùng nằm trên một đường thẳng Khi đó tồn tại 8 đoạn thẳng có điểm chung hoặc đôi một phân biệt.
Lời giải Giả sử 50 đoạn thẳng thuộc tia Axnằm ngang, hướng từ trái qua phải.
Giả sử khẳng định ban đầu là sai, tức là chỉ có tối đa 7 đoạn thẳng có điểm chung Trong số 50 đoạn thẳng, giả sử a1 là đoạn thẳng gần Anhất, khi đó chỉ có tối đa 6 đoạn thẳng có điểm chung với a1 Ngoài a1 và các đoạn thẳng chung với a1, sẽ còn ít nhất 43 đoạn thẳng khác, vì tổng số đoạn thẳng là 50 trừ đi 7.
Trong 43 đoạn thẳng, đoạn thẳng a2 có đầu trái gần điểm A nhất và có thể có tối đa 6 đoạn thẳng giao nhau với a2 Ngoài a2 và các đoạn thẳng giao nhau, còn lại ít nhất 36 đoạn thẳng.
Cứ tiếp tục như vậy ta chọn đến đoạn thẳnga 7 và các đoạn thẳng có điểm chung với nó, ta còn ít nhất đoạn thẳng.
Gọi một trong các đoạn còn lại là a 8 Khi đó a 1 , a 2 , , a 8 là 8 đoạn thẳng đôi một phân biệt.
Trên một đường thẳng có (n 2 + 1) đoạn thẳng, với điều kiện rằng không có (n + 1) đoạn thẳng nào có điểm chung, sẽ tồn tại (n + 1) đoạn thẳng đôi một không có điểm chung.
Chứng minh Giả sử (n 2 + 1) đoạn thẳng thuộc tia Axnằm ngang, hướng từ trái qua phải.
Trong một tập hợp gồm n đoạn thẳng, đoạn thẳng a1 được xác định là đoạn có đầu trái gần điểm A nhất Đoạn thẳng này có thể giao nhau với nhiều nhất (n − 1) đoạn thẳng khác Ngoài a1 và các đoạn thẳng giao nhau với nó, còn tồn tại ít nhất một đoạn thẳng khác không giao với a1.
(n 2 + 1) − n đoạn thẳng, gọi a 2 là đoạn thẳng có đầu trái gần A nhất.
Có nhiều nhất (n − 1) đoạn thẳng có điểm chung với a 2 Ngoài a 2 và các đoạn thẳng có điểm chung với nó, còn ít nhất
(n 2 + 1) − 2n đoạn thẳng, gọi a 3 là đoạn thẳng có đầu trái gầnA nhất.
Có nhiều nhất (n − 1) đoạn thẳng có điểm chung với a 3 Ngoài a 3 và các đoạn thẳng có điểm chung với nó, còn ít nhất
Cứ tiếp tục như vậy ta chọn đến đoạn thẳnga n và các đoạn thẳng có điểm chung với nó, ta còn ít nhất (n 2 + 1) − n 2 = 1 đoạn thẳng.
Gọi một trong các đoạn còn lại làa n+1 Ta có a 1 , a 2 , , a n+1 làn + 1 đoạn thẳng đôi một không có điểm chung.
Trong mệnh đề 1.6.3, tập hợp điểm S = {X1; X2; ; Xn} được xác định trên mặt phẳng với điều kiện n ≥ 3 và khoảng cách giữa hai điểm bất kỳ là khác nhau Đối với mỗi i = 1, 2, , n, ta vẽ đoạn thẳng Ui nối điểm Xi với điểm Xj ∈ S\{Xi} gần nhất Kết quả là các đoạn thẳng Ui này không thể tạo thành một đường gấp khúc khép kín.
Chứng minh rằng không tồn tại đoạn thẳng XpXq trong một đường gấp khúc khép kín Giả sử ngược lại, nếu đoạn U i tạo thành một đường gấp khúc khép kín, ta xét đoạn dài nhất XpXq Khi đó, với mọi điểm Xr khác Xq, ta có |XpXr| < |XpXq|, điều này dẫn đến Xq không phải là điểm gần Xp nhất Do đó, kết luận rằng không tồn tại đoạn thẳng XpXq.
Một số tính chất tổ hợp của đa giác không lồi
Trong phần này, chúng tôi sẽ khám phá một số tính chất tổ hợp của các đa giác không lồi Đầu tiên, chúng tôi định nghĩa một chu trình: một đường gấp khúc khép kín L = A1 A2 An A1 được gọi là chu trình nếu ba đỉnh kề nhau của L không nằm trên cùng một đường thẳng.
Định lý Jordan khẳng định rằng mọi đường gấp khúc khép kín L = A1 A2 An A1 sẽ chia mặt phẳng thành hai vùng, trong đó chỉ có một vùng bị giới hạn, tức là nằm bên trong một hình tròn nào đó.
Phần không gian bị giới hạn bởi mặt phẳng và các điểm trên đường gấp khúc khép kín L được gọi là đa giác, cụ thể là n-giác, ký hiệu là M = A1 A2 An Đường gấp khúc L được xem là biên của đa giác này.
Trong hình học, các đoạn A_i A_(i+1) (với i = 1, 2, , n và A_(n+1) = A_1) được gọi là cạnh của đa giác M, trong khi các điểm A_i (với i = 1, 2, , n) được xem là các đỉnh của M Những điểm không nằm trên biên của M được gọi là điểm trong của M Nếu các đỉnh A_i và A_j không phải
Hình 1.10: là hai đỉnh kề nhau thì đoạn A i A j được gọi là đường chéo của M (Lưu ý rằng một số đường chéo có thể chứa các điểm không thuộc M (Hình 1.10(a)).
Chúng tôi sẽ giải thích rõ hơn về góc trong tại đỉnh A i của đa giác M = A 1 A 2 A n Để minh họa, chúng tôi sẽ vẽ một đường tròn có tâm tại A i, đảm bảo rằng đường tròn này chỉ cắt đa giác tại hai điểm.
X i ∈ A i−1 A i và Y i ∈ A i A i+1 là điểm chung của đường tròn với biên của đa giác
Hai điểm X_i và Y_i trên đường tròn chia nó thành hai cung, trong đó một cung nằm trong đa giác M Góc X_i A_i Y_i được gọi là góc trong của M Đối với đa giác lồi, đoạn X_i Y_i nằm trong M, do đó tất cả các góc trong của đa giác lồi đều nhỏ hơn 180 độ Ngược lại, đa giác không lồi có ít nhất một góc trong lớn hơn 180 độ.
Mệnh đề 1.7.3 Tồn tại ít nhất ba góc trong của một đa giác không lồi nhỏ hơn 180 ◦
Chứng minh rằng m-giác M 0 không lồi của M (với 3 ≤ m < n) có mỗi đỉnh là một đỉnh của M Góc trong của M tại mỗi đỉnh tương ứng sẽ nhỏ hơn hoặc bằng góc trong của M 0, dẫn đến việc các góc này đều nhỏ hơn 180° Do đó, có ít nhất m góc trong của M nhỏ hơn 180°.
Mệnh đề 1.7.4 chỉ ra rằng mọi đa giác không lồi đều có ít nhất một đường chéo nằm hoàn toàn bên trong nó, đồng thời cũng tồn tại ít nhất một đường chéo đi qua các điểm bên ngoài đa giác.
Trong một đa giác không lồi M, có thể chứng minh rằng tồn tại ít nhất một đường chéo nằm hoàn toàn bên trong đa giác Bằng cách áp dụng kết quả từ Mệnh đề 1.7.3, chúng ta có thể chọn một đỉnh A của đa giác sao cho góc A nhỏ hơn 180 độ.
B và C là hai đỉnh liền kề của đỉnh A trong đa giác M Giả sử không có đỉnh nào khác nằm trong tam giác 4ABC, thì đường chéo BC hoàn toàn nằm trong M Nếu tam giác này chứa một đỉnh khác của M, ta chọn đỉnh D có khoảng cách gần nhất đến A; nếu có nhiều đỉnh như vậy, ta sẽ chọn một đỉnh bất kỳ Khi đó, đường chéo AD cũng nằm hoàn toàn trong M.
Chúng ta sẽ chứng minh sự tồn tại của một đường chéo trong đa giác M, bao gồm các điểm nằm ngoài đa giác này Để làm điều này, chúng ta sẽ xem xét bao lồi M' của đa giác M, trong đó mỗi đỉnh của M đều được đưa vào.
M 0 là một đỉnh của M Suy ra các cạnh của M 0 là cạnh hoặc đường chéo của
Khi đó tồn tại một số điểm nằm trên cạnh của M0 nhưng không thuộc M, vì nếu mọi điểm trên cạnh của M0 đều thuộc M thì M0 sẽ tương đương với M và M trở thành đa giác lồi, điều này dẫn đến mâu thuẫn.
Mệnh đề 1.7.5 Tồn tại ít nhất (n − 3) đường chéo nằm hoàn toàn bên trong một n-giác không lồi.
Chúng ta sẽ chứng minh khẳng định bằng phương pháp quy nạp toán học Đầu tiên, với n = 4, khẳng định của mệnh đề là đúng Giả sử khẳng định đúng với k-giác không lồi (k < n), chúng ta sẽ chứng minh cho n-giác Theo Mệnh đề 1.7.4, mọi đa giác không lồi đều có ít nhất một đường chéo nằm hoàn toàn bên trong Chúng ta chia n-giác không lồi M bằng một đường chéo nằm hoàn toàn bên trong, dẫn đến M được chia thành (k + 1)-giác và (n − k + 1)-giác (2 ≤ k ≤ n − 2) Theo giả thiết quy nạp, tồn tại ít nhất (k − 1) đường chéo nằm hoàn toàn bên trong (k + 1)-giác và (n − k − 2) đường chéo nằm trong (n − k + 1)-giác Do đó, tổng số đường chéo nằm hoàn toàn bên trong n-giác không lồi M là ít nhất 1 + (k − 2) + (n − k − 2) = n − 3.
Hệ đường cong và miền
Trong chương này, chúng tôi sẽ khám phá các bài toán tổ hợp liên quan đến việc chia một đối tượng hình học thành nhiều phần với các hình dạng khác nhau thông qua các đường thẳng hoặc đường cong Đầu tiên, chúng tôi sẽ ôn tập một số khái niệm liên quan đến chủ đề này.
Cho A là tập hợp các điểm, hoặc là một mặt phẳng.
Một điểm X được gọi là điểm trong của A nếu A chứa một hình tròn tâm X bán kính dương.
Tập hợp A được coi là mở khi mọi điểm X thuộc A đều là điểm trong của A Ngược lại, điểm X được gọi là điểm biên của A nếu nó không phải là điểm trong của A và cũng không phải là điểm trong của phần bù của A.
Chia mặt phẳng bởi các đường thẳng
Giả sử A là tập hợp tất cả các điểm trên mặt phẳng, còn L là hệ thống hữu hạn các đường thẳng phân biệt trong cùng mặt phẳng Mỗi miền của mặt phẳng được xác định bởi sự giao nhau của các đường thẳng này.
Hình 2.1 được xác định bởi các đường trong tập hợp L, cho thấy rằng nó bị giới hạn Trong trường hợp này, hình này được tạo thành bởi các điểm nằm bên trong của một số đa giác lồi, cụ thể là các miền 5, 8, 11 và 14.
Phạm vi "hình dạng" của các miền trong Hình 2.1 có thể không bị giới hạn, với các miền đa dạng như phần bên trong của một góc (miền 1, 3, 6, 12) hoặc bên trong của một "đa giác" không bị giới hạn bởi các cạnh (miền 2, 4, 7, 9, 10, 13).
Ngoài các miền đã được liệt kê, còn tồn tại một số miền không bị giới hạn với "hình dạng" khác, bao gồm nửa mặt phẳng và phần bên trong của một dải song song Những miền này xuất hiện khi mặt phẳng được chia bởi một tập hợp các đường thẳng loại thứ nhất, tức là các đường thẳng song song.
Mệnh đề 2.1.1 Chon đường thẳng trên mặt phẳng Khi đó mặt phẳng có thể bị chia thành nhiều nhất p(n) = n 2 +n+2 2 miền khác nhau bởi n đường thẳng đã cho.
Chứng minh rằng số miền tối đa có thể được chia bởi n đường thẳng q1, q2, , qn là p(n) Khi thêm đường thẳng qn+1, số miền tăng lên tương ứng với số giao điểm của qn+1 với các đường thẳng trước đó Tối đa có n giao điểm, do đó số miền tăng thêm nhiều nhất là (n + 1) Từ đó, ta có p(n + 1) ≤ p(n) + (n + 1) Để tìm công thức cho p(n), ta thiết lập các phương trình và bất phương trình như sau: p(1) = 2, p(2) ≤ p(1) + 2, p(3) ≤ p(2) + 3, , p(n) ≤ p(n - 1) + n.
Giá trị p(n) = 1/2 (n² + n + 2) đạt được khi và chỉ khi với mỗi i = 1, 2, , n, đường thẳng q_i có đúng (i - 1) giao điểm với các đường thẳng q_1, q_2, , q_{i-1} Điều này chỉ xảy ra khi hệ đường thẳng không có hai đường nào song song và không có ba đường nào đồng quy.
Theo mệnh đề 2.1.2, với n ≥ 4 đường thẳng trên mặt phẳng, nếu không có hai đường thẳng nào song song và không có ba đường thẳng nào đồng quy, thì sẽ có ít nhất \(2 \times 3^{(n - 1)}\) tam giác được hình thành từ sự chia cắt của n đường thẳng này.
Chứng minh rằng hệ đường thẳng L được chia thành hai tập hợp L1 và L2, với S là tập hợp các giao điểm Đường thẳng p thuộc L1 khi và chỉ khi tất cả các giao điểm trong S nằm hoàn toàn trong một nửa mặt phẳng có bờ là p; nếu không, p thuộc L2 Chúng ta sẽ chứng minh rằng |L1| ≤ 2, từ đó suy ra |L2| ≥ n − 2 Giả sử |L1| ≥ 3 với các đường thẳng p1, p2, p3 tạo thành tam giác ABC, trong đó mọi điểm X thuộc S đều nằm trong tam giác này Tuy nhiên, mọi đường thẳng p thuộc L\{p1, p2, p3} chỉ cắt tối đa hai trong ba đoạn thẳng AB, BC, AC, dẫn đến giao điểm của p và p1 không nằm trong tam giác ABC.
Mỗi đường thẳng p thuộc tập L1 xác định ít nhất một miền hình tam giác, trong đó hai đỉnh của tam giác nằm trên đường thẳng p và đỉnh thứ ba nằm ở vị trí khác.
Trong hình 2.2, điểm Y thuộc tập S được xác định sao cho khoảng cách đến đường thẳng p là nhỏ nhất Mỗi đường thẳng p trong tập L2 tạo ra ít nhất hai miền tam giác, với ít nhất một tam giác nằm trong mỗi nửa mặt phẳng được giới hạn bởi đường thẳng đó Khi tổng hợp số lượng miền tam giác từ tất cả các đường thẳng trong L, mỗi miền sẽ được đếm ba lần Do đó, số lượng miền tam giác N sẽ được tính toán theo công thức thích hợp.
Mệnh đề 2.1.3 nêu rõ rằng với n ≥ 2 đường thẳng thuộc hai họ đường thẳng thứ hai, có trọng tâm tại hai điểm phân biệt P và Q, trong đó có p đường thẳng đi qua P và q đường thẳng đi qua Q (với p, q ≥ 1 và p + q = n), không có đường thẳng nào đi qua cả hai điểm P và Q, và không có hai đường thẳng nào song song Dựa trên các điều kiện này, n đường thẳng sẽ chia mặt phẳng thành tối đa n² + 8n - 4 miền.
Gọi N(p, q) là số miền của mặt phẳng bị chia bởi hai họ đường thẳng Các đường thẳng trong họ P chia mặt phẳng thành N(p, 0) = 2p miền Khi có một đường thẳng đi qua Q, mặt phẳng được chia thêm (p + 1) phần, dẫn đến N(p, 1) = N(p, 0) + (p + 1) Nếu thêm một đường thẳng nữa từ họ thứ hai, mặt phẳng sẽ được chia thêm (p + 2) phần Do đó, với q ≥ 2, ta có N(p, q) = N(p, q - 1) + p + 2.
Với mỗi số không âmp, q ta có pq ≤ p+q 2 2
, đẳng thức xảy ra khi p = q Ta được
Giá trị N(p, q) được xác định khi n là số chẵn với p = q = n/2 Đối với n lẻ, n có dạng 2k + 1, số miền mà mặt phẳng bị chia ra đạt giá trị lớn nhất khi {p, q} = {k, k + 1} hoặc {p, q} = {k + 1, k} Cụ thể, với n lẻ, ta có thể đặt p = (n - 1)/2 + r và q = (n + 1)/2 - r, trong đó r thuộc tập số nguyên (Z) Khi đó, N(p, q) sẽ bằng n - 1.
Dấu bằng xảy ra khi r = 1 2 , điều này không thể bởi r ∈Z.
Với r < 1 2 thì −r 2 + r ≤ −0 2 + 0 = 0 suy ra N (p, q) ≤ n 2 +8n−5 4 Đẳng thức xảy ra khi r = 0, khi đó p = k, q = k + 1.
Với r > 1 2 thì −r 2 + r ≤ −1 2 + 1 = 0 suy ra N (p, q) ≤ n 2 +8n−5 4 Đẳng thức xảy ra khi r = 1, khi đó p = k + 1, q = k.
Chia mặt phẳng bởi các đường cong khép kín
Trong bài viết này, chúng tôi sẽ thảo luận về việc đếm số lượng miền trong mặt phẳng bị chia cắt bởi các đường cong khép kín, bao gồm các đường tròn và biên của các đa giác lồi.
Mệnh đề 2.2.1 Cho n đường tròn trên mặt phẳng Khi đó mặt phẳng có thể bị chia thành nhiều nhất k(n) = n 2 − n + 2 miền khác nhau bởi n đường tròn đã cho.
Chứng minh rằng k(1) = 2 Giả sử k(n) là số miền lớn nhất mà mặt phẳng bị chia bởi n đường tròn Khi thêm một đường tròn thứ (n + 1), đường tròn này có thể giao với n đường tròn trước tối đa 2n điểm, tạo ra nhiều nhất 2n cung tròn trên đường tròn mới, mỗi cung chia một miền ban đầu thành hai miền mới Do đó, k(n + 1) ≤ k(n) + 2n Từ đó, suy ra rằng k(n) ≤ 2 + 2 + 4 + + 2(n - 1) = n^2 - n + 2 Đẳng thức chỉ xảy ra khi hai đường tròn bất kỳ cắt nhau tại hai điểm phân biệt và ba đường tròn bất kỳ không có điểm chung.
Mệnh đề 2.2.2 Hai n-giác lồi có thể chia mặt phẳng thành nhiều nhấtN (n) = 2n + 2 miền.
Chứng minh Bất kì miền nào bị phân chia bởi hai n-giác thuộc vào một trong ba loại sau:
(a) miền bao gồm tất cả các điểm nằm bên trong cả hai đa giác, có nhiều nhất một miền như vậy.
(b) miền bao gồm tất cả các điểm nằm bên ngoài đa giác, đây là miền không bị giới hạn, có nhiều nhất một miền như vậy.
(c) các miền bao gồm các điểm nằm trong một đa giác nhưng không nằm trong đa giác còn lại Ta ước tính số lượng các miền này là N 0 (n).
Mỗi miền thuộc loại (c) là một đa giác với ít nhất ba cạnh, được hình thành từ các đoạn thẳng là cạnh hoặc một phần của các cạnh của hai n-giác đã cho Mỗi cạnh của n-giác có thể được chia thành tối đa ba đoạn.
Hình 2.3: các biên của miền thuộc loại (c), do đó ta có
Khi xem xét hai n-góc đều có cùng tâm S, ta có thể tạo ra một n-góc mới bằng cách quay n-góc ban đầu quanh tâm S một góc α = π/n Số miền của mặt phẳng bị chia bởi hai n-góc này là (2n + 2), do đó, ta có công thức N(n) = 2n + 2.
Chia đa giác lồi
Mệnh đề 2.3.1 chỉ ra rằng, đối với n-giác lồi M với n ≥ 4, tất cả các đường chéo của nó sẽ chia M thành các miền, trong mỗi miền sẽ có ít nhất một k-giác Cụ thể, với n là số lẻ, k sẽ bằng n, trong khi với n là số chẵn, k sẽ bằng n − 1.
Giả sử miền M được chia thành k-giác lồi P Qua mỗi đỉnh của M có tối đa hai cạnh hoặc đường chéo liên kết với cạnh của P Mỗi cạnh của P được xác định bởi hai đỉnh của M, dẫn đến kết luận rằng k ≤ 2n^2 = n.
Nếu n là số lẻ, giá trị k = n có thể đạt được Xét n-giác đều nội tiếp đường tròn tâm S, không có đường chéo nào đi qua S Điểm S nằm trong miền P, là đa giác có đúng n cạnh Khi quay M một góc 2π/n quanh tâm S, đa giác M sẽ trở thành chính nó (xem Hình 2.4 với n = 5).
Nếu n là số chẵn, giá trị k = n không thể đạt được Giả sử một trong những miền mà M bị chia bởi các đường chéo là n-giác P Mỗi đỉnh X của M sẽ có hai cạnh hoặc đường chéo XY, XZ chứa cạnh của P, với Y và Z là hai đỉnh kề nhau Giả sử M = A1 A2 An và hai cạnh của P nằm trên A1 Ai và A1 Ai+1 Do P nằm trong phần bên trong của góc Ai+1 A1 Ai, nên cạnh hoặc đường
Trong hình 2.5, đường chéo thứ hai từ A i+1 chứa cạnh A i+1 A 2 của P, và đường chéo hoặc cạnh thứ hai từ A 2 chứa cạnh A 2 A i+2 Lặp lại quy trình này, ta nhận thấy rằng với mỗi k = 1, 2, , n, các cạnh của P nằm trên các đường chéo hoặc cạnh A i+k−1 A k và A k A i+k (với A n+j = A j cho mọi j) Tuy nhiên, một số cạnh của P cũng nằm trên các đường chéo A i+1 A 1 và A i+1 A 2 Khi so sánh với k = i + 1, ta có A 1 = A 2i, dẫn đến i = 1 2 hoặc i = n+1 2, tạo ra mâu thuẫn Do đó, trong trường hợp n chẵn, không thể có một miền nào nhiều hơn (n − 1) cạnh.
Mệnh đề 2.3.2 Cho n-giác lồi M (n ≥ 4) không có ba đường chéo nào đồng quy Khi đó đa giác M được chia thành (n−1)(n−2)(n 2 −3n+12)
24 miền bởi các đường chéo của nó.
Các đường chéo trong đa giác chia thành các miền k-giác lồi, với 3 ≤ k ≤ n Đặt f(n) là số miền mà đa giác bị chia, trong đó r_k biểu thị số miền là k-giác.
Rõ ràng, f(n) = r3 + r4 + + rn, trong đó chúng ta xem xét tổng số V các đỉnh của k-giác và tổng số U các góc trong của các k-giác Đối với V, chúng ta có thể xác định các giá trị liên quan đến cấu trúc hình học của k-giác.
V = 3r^3 + 4r^4 + + nr^n có thể được diễn đạt theo cách khác, trong đó mỗi giao điểm của các đường chéo sẽ tạo thành một đỉnh của 4 miền, theo như Bài toán 1.2.3 với đúng n.
4 giao điểm như vậy), và mỗi đỉnh của đa giác M là một đỉnh của chính xác (n − 2) miền tam giỏc Điều này suy ra V = 4 ã n 4
Tổng U của các góc trong của tất cả các miền được xác định dựa trên Tính chất 1.1.5, trong đó tổng các góc trong của một k-giác lồi được thỏa mãn.
Tổng các góc trong của một đa giác có thể được xác định thông qua các giao điểm của các đường chéo, nơi các góc trong "gặp nhau" tạo thành một góc đầy đủ 360° Tổng các góc trong không tại các giao điểm này sẽ bằng tổng các góc trong của đa giác M.
Bằng cách so sánh cả hai biểu thức cho U, chúng ta thu được
+ (n − 1)(n − 2). cuối cùng, bằng cách khai triển, ta được f(n) = (n−1)(n−2)(n 2 −3n+12)
Mệnh đề 2.3.3 n-giác lồi M n được chia thành các tam giác bởi các đường chéo sao cho các đường chéo này không cắt nhau Khi đó
(i) Số tam giác là t(n) = n − 2, số đường chéo dùng để chia là w(n) = n − 3. (ii) Cú T (n) = n−2 1 ã 2n−3 n−2 cách chia như vậy.
Để chứng minh, ta sử dụng lập luận về tổng các góc trong của một tam giác, từ đó suy ra rằng tổng các góc trong của một đa giác M n là 180° × t(n) = (n − 2) × 180° Điều này dẫn đến t(n) = n − 2 Cần lưu ý rằng mỗi cạnh của đa giác M n chỉ thuộc về một trong số t(n) tam giác, trong khi mỗi đường chéo thuộc w(n) là cạnh của hai tam giác Do đó, ta có n + 2 × w(n) = 3 × t(n) = 3(n − 2), từ đó suy ra w(n) = n − 3.
(i) Giả sử ta đã biết số T (k) với k = 3, 4, , n, ta sẽ suy ra T (n + 1) số cách phân chia(n + 1)-giác M n+1 = A 1 A 2 A n+1 Ta chọn hai đỉnh cố định bất kì của
M n+1 , giả sửA 1 , A 2 Khi đó sự phân chia đa giácM n+1 có thể xảy ra hai trường hợp sau:
(1) Tam giác A 1 A 2 A 3 và n-giác A 1 A 3 A n+1 (hoặc tam giácA 1 A 2 A n+1 và n-giác
A 2 A 3 A n+1 ) thì n-giác có thể phân chia theo T (n) cách.
(2) Phân chia thành tam giác A 1 A 2 A k+1 , k-giác A 2 A 3 A k+1 , (n − k + 2)-giác
A 1 A k+1 A n+1 (với 3 ≤ k ≤ n − 1), xem Hình 2.7 Theo giả thiết thì hai đa giác
Hình 2.7: trên có thể chia bởiT (k)và tương ứng T (n − k + 2)cách Áp dụng quy tắc nhân, số phộp phõn chia với tam giỏc A 1 A 2 A k+1 là T (k) ã T (n − k + 2) Khi đú ta được
Để tính toán tất cả các số T(n), ta sử dụng công thức T(k) = T(n - k + 2) với điều kiện T(3) = 1 Tiếp theo, chúng ta sẽ xác định biểu thức rõ ràng của T(n) dựa trên số cạnh n Để thực hiện điều này, ta cần tìm số cách phân chia đa giác M_n bằng cách sử dụng đường chéo A_1 A_k (với k = 3, 4, , n - 1) Đường chéo này sẽ chia M_n thành một k-giác và một (n - k + 2)-giác, do đó số cách phân chia M_n sẽ là tích T(k) và T(n - k + 2) Khi cộng số này với tất cả các đường chéo của M_n, ta sẽ có kết quả cuối cùng.
Trong tổng số S, mỗi cách phân chia M n sử dụng nhiều lần một đường chéo Theo công thức (i), ta có (n − 3) đường chéo của M n, do đó S = (n − 3) × T(n).
Theo công thức (2.3.3) ta có Pn−1 k=3 T (k) ã T (n − k + 2) = T (n + 1) − 2 ã T (n), thay vào (2.3.4) ta được
Bắt đầu với T (3) = 1 và thay vào (2.3.5) ta thu được
Chia không gian
Trong phần cuối của chương này chúng tôi xem xét sự phân chia không gian theo các hệ mặt khác nhau (mặt phẳng hoặc mặt cầu).
Mệnh đề 2.4.1 Trong không gian cho n mặt phẳng phân biệt Khi đó không gian có thể bị chia thành nhiều nhất r(n) = 1 6 (n 3 + 5n + 6) miền bởi n mặt phẳng đã cho.
Chứng minh rằng r(1) = 2 Giả sử ta đã biết số miền lớn nhất r(n − 1) mà không gian bị chia bởi (n − 1) mặt phẳng α 1 , α 2 , , α n−1, với n ≥ 2 Khi thêm mặt phẳng mới α n, số miền phân chia tăng lên bằng số miền trên mặt phẳng α n bị chia bởi các mặt phẳng α 1 , α 2 , , α n−1 Số giao tuyến tối đa giữa các mặt phẳng α 1 , α 2 , , α n−1 và α n là (n − 1) đường thẳng Theo Mệnh đề 2.1.1, số miền mặt phẳng có thể bị chia nhiều nhất bởi (n − 1) đường thẳng là p(n − 1) = (n−1)² + (n−1) + 2 = n² − n + 2 miền.
Do đó ta có bất đẳng thức r(n) ≤ r(n − 1) + p(n − 1) Dùng cách lập luận tương tự với Mệnh đề 2.1.1 ta suy ra r(n) ≤ 1
Giá trị r(n) = 1 6 (n 3 + 5n + 6) đạt được khi và chỉ khi không có hai mặt phẳng nào song song và không có bốn mặt phẳng nào có điểm chung.
Mệnh đề 2.4.2 Trong không gian chon mặt cầu phân biệt Khi đó không gian có thể bị chia thành nhiều nhất K(n) = n 3 (n 2 − 3n + 8) miền bởi n mặt cầu đã cho.
Chúng ta chứng minh rằng, theo Mệnh đề 2.4.1, hình cầu thứ n được thêm vào hệ thống gồm (n − 1) hình cầu trước đó Dựa vào Mệnh đề 2.2.1, số giao tuyến tối đa giữa (n − 1) hình cầu trước và hình cầu thứ n là k(n − 1) = n^2 − 3n + 4.
Từ đó ta có K (n) ≤ K(n − 1) + k(n − 1), hiển nhiên K(1) = 2, suy ra
Giá trị K(n) = n^3(n^2 - 3n + 8) chỉ đạt được khi không tồn tại ba mặt cầu nào có hai điểm chung khác nhau và không có bốn mặt cầu nào có điểm chung.
Phủ hình và bao hình
Trong chương này, chúng tôi nghiên cứu các bài toán phủ hình và bao hình, tập trung vào việc xem xét một đối tượng hình học chứa nhiều đối tượng khác bên trong Chúng tôi phân tích khả năng xếp chồng các đối tượng "bên trong" và tìm kiếm cách phân bố tối ưu để chúng bao phủ toàn bộ hoặc phần lớn đối tượng ban đầu Những vấn đề này có ứng dụng thực tiễn, chẳng hạn như trong việc cắt vật liệu nhằm giảm thiểu lượng phế thải, và việc giải quyết chúng một cách tối ưu có thể mang lại hiệu quả kinh tế đáng kể.
Trong chương này, chúng tôi sẽ giải thích một số thuật ngữ quan trọng, bắt đầu với khái niệm về các đối tượng hình học Tất cả các đối tượng hình học được đề cập đều là đóng, tức là chúng bao gồm tất cả các điểm biên Theo định nghĩa, hai đối tượng M1 và M2 được coi là phủ lên nhau (overlap) nếu mọi điểm trong M1 cũng nằm trong M2; ngược lại, nếu không thỏa mãn điều kiện này, M1 và M2 được xem là không phủ lên nhau.
Trong lý thuyết tập hợp, nếu hệ S = {M 1 , M 2 , , M n } bao gồm các đối tượng và M 0 ⊆ Sn i=1 M i, thì hệ S được coi là phủ đối tượng M 0, tức là M 0 bị phủ bởi hệ S Cụ thể, khi S chỉ gồm một đối tượng M 1, ta có thể nói ngắn gọn rằng M 0 bị phủ bởi M 1.
Nếu hai đối tượng bất kỳ M i , M j (i 6= j ) của hệ S = {M 1 , M 2 , , M n } không phủ nhau và nếu chúng ta có Sn i=1 M i ⊆ M 0 , thì chúng ta nói rằng hệ S được bao bởi M 0
Nếu đối tượng M 0 phủ S và hệ S phủ M 0 thì chúng ta nói rằng đối tượngM o được xếp chồng (tiled) bởi hệ S.
Phủ hình
Trong chương này, chúng tôi sẽ khám phá hệ thống các đối tượng nằm trong một vùng bị chặn của mặt phẳng, nơi chúng bị che phủ lẫn nhau do kích thước diện tích của chúng Diện tích của một vật thể hình học M trong mặt phẳng được ký hiệu là |M|.
Bài toán 3.1.1 Trên một sàn nhà có diện tích3 m 2 , người ta đặt hai tấm thảm
K 1 , K 2 , mỗi tấm có diện tích 2 m 2 Khi đó phần chồng lên nhau của các tấm thảm có diện tích ít nhất là 1 m 2
Lời giải Từ sơ đồ như Hình 3.1 ta có
Bây giờ chúng ta sẽ tổng quát hóa công thức cho trường hợp n ≥ 2 đối tượng
M 1 , M 2 , , M n Cụ thể, ta có công thức sau:
(−1) r+1 |M j 1 ∩ M j 2 ∩ ∩ M j r | , (3.1.1) trong đó tổng của vế phải được lấy trên tất cả các tập con khác rỗng
Bài toán 3.1.2 đề cập đến đa giác M0 có diện tích 6 cm², bao phủ ba tam giác M1, M2, M3, mỗi tam giác có diện tích 3 cm² Trong đó, hai trong ba tam giác M1, M2, M3 chồng lấp lên nhau tạo thành một vùng có diện tích tối thiểu là 1 cm².
Lời giải Áp dụng công thức (3.1.1) ta thu được
Do đó tổng |M 1 ∩ M 2 | + |M 1 ∩ M 3 | + |M 2 ∩ M 3 | ≥ 3, suy ra ít nhất một trong ba giá trị |M 1 ∩ M 2 | , |M 1 ∩ M 3 | , |M 2 ∩ M 3 | lớn hơn hoặc bằng 1.
Chú ý rằng trong công thức (3.1.1) nếu i là lẻ thì
(−1) r+1 |M j 1 ∩ M j 2 ∩ ∩ M j r | , (3.1.2) trong khi với i chẵn thì
(−1) r+1 |M j 1 ∩ M j 2 ∩ ∩ M j r | , (3.1.3) trong đó cả hai vế phải của (3.1.2) và (3.1.3) các tổng được lấy trên cả các tập con khác rỗng {j 1 , j 2 , , j r } của {1, 2, , n} của nhiều nhất i phần tử.
Bài toán 3.1.3 đề cập đến một đa giác M0 có diện tích 10 cm², bao phủ bốn đa giác M1, M2, M3, M4, mỗi đa giác có diện tích 6 cm² Trong số bốn đa giác này, ba trong số chúng chồng lấn lên nhau tạo thành một vùng có diện tích tối thiểu là 1 cm².
Lời giải Tương tự cách giải quyết Bài toán 3.1.2 ta có được
≥ |M 1 | + |M 2 | + |M 3 | + |M 4 | − 2 ã |M 1 ∪ M 2 ∪ M 3 ∪ M 4 | (3.1.4) Bây giờ chúng ta sẽ chứng minh bất đẳng thức
Tương tự như Mệnh đề 3.1.2, tập hợp M 0 = M 1 ∪ M 2 ∪ ∪ M n được chia thành các phần rời rạc X 1 ∩ X 2 ∩ ∩ X n, với X i = M i hoặc X i = M 0 \ M i (i thuộc {1, 2, , n}) Nếu X i = M i với ít nhất r ≥ 3 giá trị khác nhau của chỉ số i, thì diện tích phần X 1 ∩ X 2 ∩ ∩ X n ở vế trái của (3.1.5) được tính r 3 lần, trong khi ở vế phải được tính (r − 1) lần Đối với mọi r ≥ 3, bất đẳng thức r 3 được xác lập.
Để xác minh điều kiện ≥ r − 2, ta có thể viết ra hệ số của nhị thức Với r = 1 và r = 2, ta nhận thấy rằng 0 > 1 − 2 và 0 = 2 − 2, từ đó chứng minh được điều cần thiết.
Bài toán 3.1.4 Cho tam giác nhọnABC có diện tích bằng 1 Chứng minh rằng tồn tại một tam giác vuông có diện tích không vượt quá √ 3 phủ kín 4ABC.
Lời giải Giả sử BC là cạnh lớn nhất của 4ABC Kẻ trung tuyến AM, đặt
M A = R, M B = M C = a Vẽ đường tròn c(M, R) cắt đường thẳng BC tại D, E.
Ta sẽ chứng minh 4ADE thỏa mãn bài toán.
Thật võy, kẻ đường caoAH Ta cúS 4ADE = 1 2 ã DE ã AH = R ãAH;AH = 2S 4ABC BC =
2a = 1 a nênS 4ADE = R a Ta chứng minh R a ≤ √
3. Trong hai gócAM B,\ AM C\tồn tại một góc lớn hơn hoặc bằng90 ◦ , giả sử\AM C ≥
90 ◦ Khi đó AM 2 + M C 2 ≤ AC 2 Suy ra
Vậy tam giác vuông ADE có diện tích không quá √ 3 phủ kín tam giác ABC.
Trong bài toán 3.1.5, cho bốn điểm trên mặt phẳng với khoảng cách giữa bất kỳ hai điểm nào luôn lớn hơn 1 Cần chứng minh rằng không thể bao phủ tất cả bốn điểm này bằng một hình tròn có đường kính tối đa là √2.
Trong bài viết này, chúng ta sẽ chứng minh rằng trong bốn điểm A, B, C, D đã cho, luôn tồn tại hai điểm có khoảng cách lớn hơn √2 Để làm rõ điều này, chúng ta sẽ xem xét ba trường hợp khác nhau.
Trong một tứ giác lồi với bốn đỉnh A, B, C, D, tồn tại ít nhất một góc lớn hơn hoặc bằng 90 độ, giả sử góc A (∠Ab) ≥ 90° Chúng ta sẽ chứng minh rằng độ dài cạnh BC lớn hơn căn bậc hai của một giá trị nhất định.
2. Thật vậy, do Ab≥ 90 ◦ nên BC 2 ≥ AB 2 + BC 2 > 1 + 1 = 2.
2. (b) Ba điểm A, B, C là đỉnh của một tam giác, điểmD nằm trên cạnh hoặc bên trong 4ABC.
- Giả sử D nằm trên cạnh AB thì AD > 1, DB > 1 nên AB > 2 > √
- Giả sử D nằm bên trong 4ABC tồn tại một trong ba góc ADB,[ ADC,[ CDB[ lớn hơn hoặc bằng 120 ◦ , giả sử ADB[ ≥ 120 ◦
Khi đú AB 2 ≥ DA 2 + DB 2 − 2 ã DA ã DB ã cos 120 ◦ = 3 > 2.
2.(c) Bốn điểm A, B, C, D thẳng hàng Bài toán hiển nhiên đúng.
