Chương 1 Bài toán đếm trong hình học tổ hợp Trong chương này chúng tôi trình bày một số tính chất tổ hợp của các đa giác lồi và các đa giác không lồi, cùng với một số bài toán đếm một số đối tượng hình học thỏa mãn một số tính chất nào đó: Đếm số giao điểm, đếm số tam giác, .1 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 trình bày một số tính chất tổ hợp của các đa giác lồi. Đầu tiên chúng tôi định nghĩa tập lồi. Tập lồi trong mặt phẳng (trên đường thẳng, trong không gian) là tập hợp U các điểm trong mặt phẳng (trên đường thẳng, trong không gian) có tính chất sau: Với hai điểm phân biệt bất kì X , Y thuộc U thì mọi điểm của đoạn thẳng XY cũng thuộc U. Tập lồi trên đường thẳng có cấu trúc đơn giản: Ngoại trừ đường thẳng, tập rỗng, các điểm thì các tập lồi là các tia và đoạn thẳng, có hoặc không có điểm biên.
Việc phân loại các tập lồi trong mặt phẳng rõ ràng là khó khăn, nhưng một công cụ đáng kể trong việc xây dựng các tập lồi là giao của các tập lồi là 4 một tập lồi. Một khái niệm quan trọng đó chính là bao lồi K của U : nó là giao của tất cả các tập lồi M thỏa mãn U ⊆ M (vì vậy K là tập lồi nhỏ nhất chứa U ). , An } là tập gồm n điểm phân biệt trong mặt phẳng (n ≥ 3). Tập M được gọi là n-giác lồi A1 A2.
An nếu M là giao của n nửa mặt phẳng α1 , α2 , ., αn sao cho với mỗi i = 1, 2,. , n đường thẳng Ai Ai+1 (trong đó An+1 = A1 ) là biên của nửa mặt phẳng αi và mỗi điểm Aj ∈ K\{Ai ; Ai+1 } đều nằm trong αi. Nếu U là một tập hợp hữu hạn gồm n điểm (n ≥3) trong mặt phẳng sao cho n điểm không cùng nằm trên một đường thẳng thì bao lồi của U là một đa giác lồi có các đỉnh là một số (hoặc có thể là tất cả) phần tử của tập U. Một kết quả quan trọng khác trong lý thuyết tập lồi đó là Định lý Helly.
Giả sử S là một hệ bất kì (hữu hạn hoặc vô hạn) các tập con lồi của một mặt phẳng cho trước sao cho ba tập hợp bất kì có ít nhất một điểm chung. Khi đó 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. Số đường chéo un của n-giác lồi M thỏa mãn n(n − 3) un =.
Thật vậy, n đỉnh của đa giác M được nối với nhau bởi 2 = 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ó n(n−1) n(n−3) un = 2 −n= 2. 5 Một cách tính khác: Mỗi đỉnh của đa giác M là điểm cuối của n − 3 đường chéo. Nếu chúng ta cộng tất cả n đỉnh của M thì các đường chéo này đã được đếm hai lần, chúng ta cũng có được un = n(n−3) 2.
Tổng Sn các góc trong một n-giác lồi thỏa mãn Sn = (n − 2) · 180◦. Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán học.1) là công thức đã biết về tổng các góc trong của một tam giác. Bây giờ chúng ta giả sử rằng công thức (1.1) đúng với i = n (n > 3), ta sẽ chứng minh (1. Ta chia nhỏ (n + 1)-giác lồi A1 A2.
An+1 theo đường chéo A1 A3 thành tam giác A1 A2 A3 và n-giác lồi A1 A3. Khi đó n-giác lồi A1 A3. An+1 có tổng các góc trong là Sn = (n − 2) · 180◦. Vì tổng Sn+1 các góc trong của đa giác A1 A2.
An+1 bằng tổng các góc trong của tam giác A1 A2 A3 cộng với tổng các góc trong của n-giác A1 A3. An+1 , suy ra Sn+1 = 180◦ + (n − 2) · 180◦ = (n − 1) · 180◦. Một cách tính khác: Đa giác M = A1 A2. An có thể chia bởi n − 3 cạnh A1 Ak (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 Sn. 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. Ta sẽ chứng minh bằng phương pháp quy nạp toán học theo n rằng tồn tại 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. Với n ≤ 5, n-giác lồi đang xét là n-giác lồi thông thường, do đó khẳng định của mệnh đề đã đưa ra là đúng.
Với n > 6 ta giả sử rằng n-giác lồi Mn = A1 A2. An 6 nội tiếp đường tròn C và không có ba đường chéo nào đồng quy. Ta xét tập hợp P gồm tất cả các đường thẳng nối các giao điểm của tất cả các đường chéo của đa giác Mn. Khi đó có hữu hạn đường thẳng thuộc P và cũng có hữu hạn giao điểm của các đường thẳng này với đường tròn C.
Do đó tồn tại một điểm An+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 P. Hơn nữa An+1 có thể được chọn nằm trên cung tròn giới hạn bởi A1 , An và không chứa A2 , A3 ,. An An+1 là một (n + 1)-giác lồi không có ba đường chéo nào đồng quy. Cho n (n ≥ 4) điểm nằm trên mặt phẳng sao cho không có ba điểm nào thẳng hàng và bốn điểm bất kì là đỉnh của một tứ giác lồi.
Khi đó n điểm đã cho là đỉnh của một n-giác lồi. Gọi S là tập hợp các điểm đã cho và giả sử bao lồi của S là k -giác M. Ta sẽ chứng minh mọi điểm X ∈ S là đỉnh của M. Phản chứng rằng 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 , khi đó k -giác M được chia thành k − 2 tam giác và đ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. Chọn một điểm P tùy ý nằm trong đa giác lồi M và dựng các hình chiếu vuông góc từ P lên các đường thẳng chứa cạnh của M. Khi đó có ít nhất một trong các hình chiếu này nằm trên cạnh của M.
Trong tất cả các đường thẳng chứa cạnh của M , ta chọn đường thẳng có khoảng cách đến P là nhỏ nhất, giả sử đường thẳng ấy là ` (Nếu có nhiều đường thẳng như vậy thì ta chọn một đường bất kì). Giả sử cạnh AB nằm 7 trên `, ta sẽ chứng minh hình chiếu vuông góc Q của P lên ` nằm trên đoạn thẳng AB. Giả sử Q ∈ ` \ AB (Hình 1.1), khi đó đoạn thẳng P Q nối một điểm trong với một điểm ngoài đa giác M , và giả sử P Q cắt CD tại R.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 `. 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. Từ Tính chất 1.4 ta được n(n − 3) n=9 (nhận) un = = 27 ⇔ n2 − 3n − 54 = 0 ⇔ 2 n = −6 (loại) Vậy n-giác đều cần tìm là 9-giác đều.2 Đế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ộ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. Ta xét một đoạn AB tùy ý thuộc đường gấp khúc.
Nó có thể có nhiều nhất 2n − 2 giao điểm, vì AB sẽ không bị cắt bởi hai đoạn kề của nó. Điều này đưa ra ước tính cho số k các giao điểm là: k ≤ (2n+1)(2n−2) 2 = (2n + 1)(n − 1). Ta có thể dựng một đường gấp khúc khép kín với chính xác (2n + 1)(n − 1) giao điểm: Xét đa giác A1 A2. A2n+1 trong đó không có ba đường chéo đồng quy bên trong đa giác.
Khi đó đường gấp khúc A1 An+1 A2n+1 An A2n An−1. A2 An+2 A1 là đường gấp khúc có chính xác (2n + 1)(n − 1) giao điểm. Cho n-giác lồi A1 A2. An 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 n(n − 1)(n − 2)(n − 3) =. Ta xét đường chéo cố định A1 Ak (k = 3, 4,. , n − 1) và xác định số giao điểm của đường chéo này với các đường chéo khác. Đường thẳng A1 Ak chia mặt phẳng thành hai nửa mặt phẳng, một nửa mặt phẳng chứa (k − 2) đỉnh của đa giác, nửa mặt phẳng còn lại chứa (n − k) đỉnh.
Do đó đường chéo A1 Ak cắt các đường chéo khác tại (n − k)(k − 2) điểm, và a1 (n) là số giao điểm trên tất cả các đường chéo xuất phát từ A1 thỏa mãn n−1 n−1 X X (n − 1)(n − 2)(n − 3) a1 (n) = (n − k)(k − 2) = [(n + 2)k − k 2 − 2n] =. 6 k=3 k=3 Nếu chúng ta cộng số này cho tất cả các đỉnh của đa giác thì chúng ta đã đếm mỗi giao điểm 4 lần. Do đó tổng số giao điểm A(n) của các đường chéo là 1 n(n − 1)(n − 2)(n − 3) n A(n) = · n · a1 (n) = =. 4 24 4 9 Một cách tính khác: Bất kì giao điểm nào của hai đường chéo cũng tương ứng với bốn đỉnh của n-giác.
Do đó số giao điểm của các đường chéo chính là số cách chọn bốn trong số n đỉnh của n-giác, tức là có n4 giao điểm. Cho năm điểm nằm trong mặt phẳng và trong số tất cả các đoạn thẳng nối hai điểm bất kì không có hai đoạn nào song song hoặc vuông góc với nhau. Từ mỗi điểm đã cho dựng đường vuông góc với tất cả các đoạn thẳng kể trên. Khi đó số giao điểm của hệ này không vượt quá 310.