Luận văn Thạc sĩ Toán học: Định lý Pick, dãy Farey, vòng tròn Ford và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

21
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chúng ta đã biết trong đề tài này các chủ đề gồm định lý Pick, dãy Farey, vòng tròn Ford được sử dụng để kết nối các ý tưởng từ khía cạnh trực quan của hình học đến bản chất trừu tượng của đại số. Việc sử dụng định lý Pick lấy ý tưởng từ các kiến thức bậc trung học cơ sở và dần chuyển lên cấp độ sử dụng lập luận toán học cao hơn thông qua việc sử dụng dãy Farey và vòng tròn Ford.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Định lý Pick, dãy Farey, vòng tròn Ford và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LẠI THẾ HANH ĐỊNH LÝ PICK, DÃY FAREY, VÒNG TRÒN FORD VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LẠI THẾ HANH ĐỊNH LÝ PICK, DÃY FAREY, VÒNG TRÒN FORD VÀ ỨNG DỤNG 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 TS. Nguyễn Văn Hoàng THÁI NGUYÊN - NĂM 2017
i Mục lục Lời mở đầu 1 1 Định lý Pick 3 1.1 Ví dụ về định lý Pick . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Định lý Pick cho hình chữ nhật . . . . . . . . . . . . . . . . . 5 1.3 Tam giác vuông canh bên phải . . . . . . . . . . . . . . . . . 6 1.4 Định lý Pick cho tam giác bất kỳ . . . . . . . . . . . . . . . . 8 1.5 Định lý Pick cho trường hợp tổng quát . . . . . . . . . . . . . 10 1.5.1 Tổng quan về chứng minh . . . . . . . . . . . . . . . . 10 1.5.2 Ghép nối hai đa giác lưới . . . . . . . . . . . . . . . . . 12 1.5.3 Các đường chéo bên trong . . . . . . . . . . . . . . . . 13 1.5.4 Đa giác có lỗ thủng . . . . . . . . . . . . . . . . . . . . 14 2 Dãy Farey 17 2.1 Khái niệm và tính chất . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Tìm kiếm phân số gần nhất trong dãy Farey Fn . . . . . . . . 22 2.2.1 Thuật toán tìm kiếm cải tiến . . . . . . . . . . . . . . 26 2.2.2 Phân tích hiệu suất . . . . . . . . . . . . . . . . . . . . 26 2.3 Một số ứng dụng có liên quan đến hình ảnh . . . . . . . . . . . 26 2.3.1 Đa giác mô phỏng gần đúng . . . . . . . . . . . . . . . 26 2.3.2 Phân tích hình ảnh . . . . . . . . . . . . . . . . . . . . 29 3 Vòng tròn Ford và liên hệ với định lý Pick, dãy Farey 32 3.1 Giới thiệu vòng tròn Ford . . . . . . . . . . . . . . . . . . . . 32 3.2 Mối liên hệ giữa định lý Pick và dãy Farey . . . . . . . . . . . 38 3.3 Mối liên hệ giữa dãy Farey và vòng tròn Ford . . . . . . . . . . 39 Kết luận 42 Tài liệu tham khảo 43
ii Danh sách các kí hiệu Kí hiệu Tên
1 Lời mở đầu Chúng ta đã biết trong đề tài này các chủ đề gồm định lý Pick, dãy Farey, vòng tròn Ford được sử dụng để kết nối các ý tưởng từ khía cạnh trực quan của hình học đến bản chất trừu tượng của đại số. Việc sử dụng định lý Pick lấy ý tưởng từ các kiến thức bậc trung học cơ sở và dần chuyển lên cấp độ sử dụng lập luận toán học cao hơn thông qua việc sử dụng dãy Farey và vòng tròn Ford. Trong 1 số chương trình giảng dạy về toán học thì các kiến thức này được đưa ra một cách riêng biệt. Qua luận văn này tôi muốn trình bày mối liên hệ giữa các kiến thức đó, những mối liên hệ này rất quan trọng vì nó giúp chúng ta có thể hiểu sâu hơn về toán học. Với mong muốn tìm hiểu sâu hơn một số kiến thức về hình học hình ảnh, một vài dãy số có tính chất đặc biệt, đồng thời nâng cao thêm các kiến thức đã học trong chương trình đại học và cao học, tôi chọn đề tài Định lý Pick, dãy Farey, vòng tròn Ford và ứng dụng làm luận văn cao học của mình. Cấu trúc luận văn được chia thành 03 chương: Chương 1 là định lý Pick trình bày chứng minh một phương pháp để tính diện tích các đa giác đơn có đỉnh nằm trên lưới điểm có tọa độ nguyên trong mặt phẳng xOy . Từ “đơn” trong “đa giác đơn” chỉ có nghĩa là đa giác không có lỗ thủng và các cạnh của nó không cắt nhau. Chương 2 trình bày lại phát minh của Farey về một quy trình để tạo ra các phân số thích hợp nằm trong đoạn [0, 1], nó được gọi là dãy Farey. Một cách chính xác, dãy Farey Fn (với chỉ số n) là dãy các phân số tối giản, thực sự, dương, có mẫu số nhỏ hơn hoặc bằng n, và được sắp xếp theo thứ tự tăng dần theo các giá trị của chúng. Chương 3 trình bày định lý Ford về sự biểu diễn hình học của 1 phân số.
2 a c Ford mong muốn minh họa các phân số đặc biệt ví dụ như và bởi các b d vòng tròn (gọi là vòng tròn Ford) và nêu các mối liên hệ giữa định lý Pick với dãy Farey, giữa dãy Farey với vòng tròn Ford. Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên dưới sự hướng dẫn của TS. Nguyễn Văn Hoàng. Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Nguyễn Văn Hoàng, thầy đã định hướng chọn đề tài và tận tình hướng dẫn, giảng giải để tôi có thể hoàn thành luận văn này. Qua đây tôi xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo dạy cao học chuyên ngành Phương pháp toán sơ cấp, trường Đại học Khoa học, Đại học Thái Nguyên đã trang bị kiến thức, giúp đỡ tôi trong suốt quá trình học tập và thực hiện luận văn. Tôi cũng xin gửi lời cảm ơn sâu sắc tới Trung tâm nghiên cứu và phát triển giáo dục Hải Phòng đã giúp đỡ, tạo mọi điều kiện thuận lợi giúp tôi có thể hoàn thành luận văn này. Nhân dịp này tôi cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn động viên, cổ vũ, giúp đỡ tôi trong quá trình học tập và hoàn thành luận văn. Thái Nguyên, tháng 9 năm 2017 Tác giả Lại Thế Hanh
3 Chương 1 Định lý Pick Trong chương này chúng tôi trình bày và chứng minh định lý của Pick về công thức tính diện tích của một đa giác đơn từ đơn giản đến tổng quát thông qua lưới điểm có tọa độ nguyên ở miền trong và trên biên của đa giác. Các kết quả của chương này chủ yếu được tham khảo từ các tài liệu [1], [5], [7]. 1.1 Ví dụ về định lý Pick Định lý Pick cung cấp cho chúng ta một phương pháp để tính diện tích của đa giác đơn giản mà đỉnh của nó nằm trên lưới điểm - điểm với tọa độ nguyên trong mặt phẳng x − y . Từ "đơn giản" trong "đa giác đơn giản" chỉ có nghĩa là đa giác không có lỗ thủng và các cạnh của nó không cắt nhau. Các đa giác trong Hình 1.1 là các đa giác đơn giản, nhưng ta nên hiểu rằng từ "đơn giản" chỉ có thể áp dụng trong một ý nghĩa nhất định - một đa giác đơn giản về mặt kỹ thuật có thể có một triệu cạnh. Rõ ràng cho đa giác với một miền trong lớn, miền này sẽ là khoảng xấp xỉ bởi số lượng các điểm lưới ở trong nó. Ta có thể đoán rằng một chút xấp xỉ tốt hơn có thể nhận được bằng cách thêm khoảng một nửa các điểm lưới trên “biên” vì chúng là loại nửa trong và nửa ngoài đa giác. Nhưng chúng ta hãy nhìn vào một vài ví dụ trong Hình 1.1. Đối với các ví dụ dưới đây, ta sẽ cho I là số điểm của miền trong, và B là số điểm ở trên biên. Ta sử dụng ký hiệu A(P ) để chỉ diện tích đa giác P .
4 Hình 1.1: Ví dụ về định lý Pick’s B • A : I = 0, B = 4, A(A) = 1, I + = 2. 2 1 B 3 • B : I = 0, B = 3, A(B) = , I + = . 2 2 2 B • C : I = 28, B = 26, A(C) = 40, I + = 41. 2 B • D : I = 7, B = 12, A(D) = 12, I + = 13. 2 E : Có một chút phức tạp hơn để ước tính diện tích của đa giác E và F . E có thể bị chia thành một hình chữ nhật 6 x 3 và hai tam giác vuông với đáy 3 và chiều cao 5, vì vậy ta nhận được: B • I = 22, B = 24, A(E) = 33, I + = 34. 2 F : Nó thậm chí còn khó hơn khi tính diện tích cho trường hợp này, nhưng sau khi bổ sung và loại bỏ một số phần diện tích, chúng ta nhận ra rằng: B • I = 9, B = 26, A(F ) = 21, I + = 22. 2
5 Điều bất ngờ là nếu nhìn vào tất cả sáu ví dụ trên, ta thấy rằng ước tính B I+ luôn luôn đạt được một kết quả chính xác đó là diện tích cộng thêm 2 1. Dường như đối với bất kỳ lưới đa giác P nào, thì công thức tính diện tích sau đây là đúng BP A(P ) = IP + −1 2 với IP là số điểm lưới nằm hoàn toàn bên trong P và BP là số các điểm nằm trên biên của P . Đây được gọi là Định lý Pick. Ta hãy thử một vài ví dụ khác nữa trước khi tiếp tục. 1.2 Định lý Pick cho hình chữ nhật Thay vì cố gắng tìm cách chứng minh tổng quát ngay từ đầu, chúng ta hãy kiểm chứng tính đúng đắn của Định lý Pick đối với một số trường hợp đơn giản hơn. Trường hợp đơn giản nhất để xem xét đó là “lưới” hình chữ nhật. Hình 1.2: Định lý Pick cho hình chữ nhật Hình chữ nhật đặc biệt trong Hình 1.2 là lưới 14×11 (m = 14 và n = 11), vì vậy nó có diện tích là A = 14 × 11 = 154. Và thật dễ dàng để tính số
6 điểm trong và điểm biên: miền trong có I = 13 × 10 = 130 điểm, và nó có B = 50 điểm trên biên. Khi đó ta có liên hệ B 50 I+ − 1 = 130 + − 1 = 154 = A. 2 2 Vì vậy đối với hình chữ nhật đặc biệt này thì định lý Pick chắc chắn là đúng. Nhưng khi xét một hình chữ nhật có kích thước m × n (với các đỉnh nằm trên lưới nguyên, và có các cạnh song song với các trục Ox, Oy ) thì điều gì sẽ xảy ra? Diện tích lúc này hiển nhiên là m × n. Lúc này dễ dàng thấy rằng số các điểm trong là I = (m − 1) × (n − 1) (ta có thể tự kiểm chứng bằng cách xét một vài ví dụ nếu cần thiết). Ta cũng thấy rằng số điểm biên của hình chữ nhật đó là B = 2m + 2n (bởi vì B = 2(m + 1) + 2(n + 1) − 4). Vì vậy khi cho một hình chữ nhật có kích thước m × n, ta luôn có công thức B (2m + 2n) I+ − 1 = (m − 1) × (n − 1) + −1 2 2 = (mn − m − n + 1) + (m + n) − 1 = mn, B đó chính là công thức I + − 1 = A. 2 1.3 Tam giác vuông canh bên phải Có một chút khó khăn hơn để chỉ ra rằng các công thức đúng cho các tam giác vuông canh bên phải, nơi hai cạnh góc vuông của tam giác nằm dọc theo các đường lưới. Cách dễ nhất để làm rõ điều này là ta chọn một tam giác như là một nửa của một trong các hình chữ nhật ở phần trước, khi đó có một đường chéo được thêm vào, như Hình 1.3. Ta sẽ xét một hình tam giác T như vậy với 2 cạnh góc vuông có độ dài m và n. Khi đó tam giác này có diện tích là A(T ) = mn 2 , nhưng liệu nó có bao nhiêu điểm trong và bao nhiêu điểm biên nữa? Quan sát Hình 1.3, ta có thể dễ dàng đếm được các điểm biên dọc theo 2 cạnh, nhưng ta thấy đôi khi một số điểm lưới không nằm trên các đường chéo của tam giác. Nhưng điều đó không quan trọng. Đối với một tam giác vuông tùy ý với cạnh góc vuông dài m và n và có diện tích A(T ) = mn2 , giả sử có k điểm trên đường chéo, không kể những điểm ở hai đầu (đỉnh tam giác). Khi đó dễ thấy số lượng các
7 Hình 1.3: Định lý Pick cho tam giác vuông canh bên phải điểm biên là m + n + 1 + k . Số lượng các điểm bên trong cũng rất dễ dàng tính toán được. Hình chữ nhật cạnh độ dài là m và n sẽ có (m − 1)(n − 1) điểm trong. Sau khi trừ đi k điểm trong nằm trên đường chéo, số còn lại là (m − 1)(n − 1) − k , số này gấp đôi số điểm trong của tam giác. Vậy số điểm trong của tam giác là I = (m−1)(n−1)−k 2 . Bây giờ ta kiểm tra Định lý Pick đối với một tam giác vuông canh bên phải, ta nhận được: B (m − 1)(n − 1) − k m + n + 1 − k I+ −1= + −1 2 2 2 mn m n 1 k m n 1 k = − − + − + + + + −1 2 2 2 2 2 2 2 2 2 mn = 2 = A(T ). Như vậy định lý Pick đúng trong trường hợp này.
8 1.4 Định lý Pick cho tam giác bất kỳ Giả sử rằng Định lý Pick đã đúng cho các tam giác vuông canh bên phải và hình chữ nhật có các cạnh song song với các trục. Khi đó ta có thể chứng minh rằng định lý Pick cũng đúng cho một tam giác tùy ý. Trong thực tế có rất nhiều trường hợp khác nhau để xem xét, nhưng tất cả các tam giác này đều ít nhiều giống như các biến thể của Hình 1.4, ở đó là một tam giác T tùy ý có thể được mở rộng đến một hình chữ nhật bằng cách bổ sung thêm của một vài tam giác vuông. Trong trường hợp của hình vẽ này, ba hình tam giác khác được bổ sung thêm vào để được như yêu cầu chẳng hạn là A, B , và C . Hình 1.4: Định lý Pick cho tam giác bất kỳ Giả sử rằng tam giác A có số các điểm miền trong là IA và số các điểm trên biên là BA , tam giác B có các điểm miền trong là IB và các điểm trên biên là BB , tương tự cho C . Gọi hình chữ nhật được xây dựng như trên là R, và giả sử R có số điểm miền trong là IR và số các điểm trên biên là BR . Vì ta đã biết công thức của Pick cho tam giác vuông và hình chữ nhật nên
9 ta có: BA A(A) = IA + −1 2 BB A(B) = IB + −1 2 BC A(C) = IC + −1 2 BR A(R) = IR + − 1. 2 BT Ta muốn chỉ ra rằng A(T ) = IT + − 1. 2 Nhìn vào hình vẽ ta biết rằng A(T ) = A(R) − A(A) − A(B) − A(C) (1) BR − BA − BB − BC = IR − IA − IB − IC + + 2. (2) 2 Giả sử hình chữ nhật R có kích thước m × n, vì vậy nó có diện tích A(R) = mn, có BR = 2m + 2n và có IR = (m − 1)(n − 1). Nếu chúng ta tính điểm biên một cách cẩn thận, chúng ta thu được BA + BB b + BC = BR + BT hay BR = BA + BB + BC − BT (3) (vì các đỉnh góc nhọn của các tam giác xung quanh được tính hai lần ở cả hai vế của phương trình). Đếm các điểm bên trong của hình chữ nhật ta được IR = IA + IB + IC + IT + (BA + BB + BC + BR ) − 3 (4) (ở đây ta cần có số −3 ở cuối của phương trình trên bởi vì các góc của tam giác thực sự bị tính hai lần). Thay thế giá trị BR trong công thức (3) vào phương trình (4) ta được IR = IA + IB + IC + IT + BT − 3. (5) Bây giờ ta thay thế các giá trị của BR và IR từ phương trình (3) và (5) vào
10 phương trình (2), và sau khi rút gọn, ta thu được kết quả: BR − BA − BB − BC A(T ) = IR − IA − IB − IC + +2 2 = (IA + IB + IC + IT + BT − 3) − IA − IB − IC (BA + BB + BC − BT ) − BA − BB − BC + +2 2 BT BT = IT + BT − 3 − + 2 = IT + − 1. 2 2 Đó là chính xác những gì ta muốn trình bày. Nếu bạn muốn kiểm tra công thức trên với các ví dụ trong Hình 1.4, thì bảng dưới đây là các giá trị cho tất cả bốn hình tam giác và hình chữ nhật. BX X IX BX A(X) = IX + 2 −1 A 10 18 18 = 10 + 18 2 −1 20 B 16 20 25 = 16 + 2 − 1 C 15 16 22 = 15 + 16 2 −1 T 40 12 45 = 40 + 12 2 −1 T 90 42 110 = 90 + 422 −1 1.5 Định lý Pick cho trường hợp tổng quát Bây giờ ta biết rằng Định lý Pick đã đúng đối với tam giác tùy ý với đỉnh của nó nằm trên lưới điểm. (Vì chúng ta đã làm, đã kiểm tra tra một số trường hợp khác tương tự những trường hơp mà đã xuất hiện trong phần trước.) Vậy làm thế nào để chúng ta chỉ ra rằng nó là đúng đối với một đa giác đơn P tùy ý với các đỉnh nằm trên lưới điểm? 1.5.1 Tổng quan về chứng minh Bằng trực giác, những gì chúng ta nhận thấy là mọi đa giác đơn như đã đề cập ở trên có thể được xây dựng bằng cách ghép từ các đa giác nhỏ hơn, nơi mà ta đã chứng minh được lý Pick là đúng. Ta sẽ mô phỏng về chứng minh này như sau. Ta đã chỉ ra rằng mọi đa giác lưới 3 cạnh thỏa mãn định lý Pick. Tiếp theo, chúng ta chứng minh rằng nếu nó đúng cho tất cả các
11 đa giác 3 cạnh, thì nó cũng đúng đối với tất cả các đa giác 4 cạnh. Sau đó, chúng ta chứng minh rằng nếu định lý Pick đúng cho tất cả các đa giác 3 và 4 cạnh thì nó cũng đúng cho tất cả các đa giác 5 cạnh. Sau đó, chúng ta chỉ ra rằng, nếu đó là đúng cho tất cả các đa giác có 3, 4, và 5 cạnh thì nó cũng đúng cho tất cả các đa giác có 6 cạnh,... tiếp tục quá trình. Kĩ thuật này đã chính thức được công nhận và nó được gọi là quy nạp toán học tổng quát. Trên thực tế, trong thực hành, ta sẽ không làm vô hạn các bước chứng minh như ta vừa mô tả ở đoạn trên, mà chúng ta chỉ làm với một số hữu hạn các bước mà thôi. Chúng ta sẽ chứng minh nó qua hai bước sau đây (trong đó bước thứ nhất đã được chứng minh): • 1. Chứng minh rằng định lý là đúng cho mỗi đa giác lưới có 3 cạnh. • 2. Chứng minh rằng nếu định lý là đúng cho mọi đa giác lưới có 3 hoặc 4 hoặc 5 hoặc . . . hoặc k − 1 cạnh, thì nó cũng đúng cho mọi lưới đa giác có k cạnh. Vì phần thứ hai của chứng minh áp dụng đối với k cạnh bất kỳ, nên nó có hiệu lực cho tất cả vô hạn bước đã liệt kê ở hai đoạn trên. Một ví dụ cụ thể về ý tưởng tổng quát như đã mô phỏng được minh họa trong Hình 1.5. Chúng ta có một đa giác 23 cạnh: ABC . . . W . Ta sẽ chứng minh rằng mọi đa giác như vậy với hơn ba cạnh phải đều có một đường chéo bên trong (có rất nhiều đường như vậy trong Hình 1.5, nhưng ta chọn đường chéo OW làm một ví dụ), và một đường chéo như vậy sẽ chia đa giác thành một cặp đa giác nhỏ hơn. Trong trường hợp này, chia thành đa giác ABC . . . M N OW có 16 cạnh và đa giác OP Q . . . W có 9 cạnh. Vì theo giả thiết quy nạp ta đã biết rằng định lý Pick đúng cho tất cả các đa giác có từ 3 đến 22 cạnh, do đó trong cụ thể của ta thì định lý Pick là đúng cho các đa giác có 16 và 9 cạnh. Sau đó ta sẽ chỉ ra rằng nếu hai đa giác thỏa mãn định lý Pick mà chúng được gắn với nhau ở một cạnh chung thì đa giác kết quả cũng sẽ thỏa mãn định lý Pick. Mục tiếp theo, chúng ta sẽ chỉ ra phần thứ hai đầu tiên rằng nếu hai đa giác cùng thoả mãn định lý Pick thì kết quả phần ghép lại của chúng cũng thỏa mãn nội dung định lý.
12 Hình 1.5: Định lý Pick cho trường hợp tổng quát 1.5.2 Ghép nối hai đa giác lưới Giả sử hai đa giác phụ của đa giác P ban đầu là P1 và P2 , với P1 có I1 điểm bên trong và các điểm trên biên là B1 ; P2 có I2 điểm bên trong và các điểm trên biên là B2 . Ta cũng giả định rằng đường chéo chung của đa giác ban đầu ngăn giữa P1 và P2 có chứa điểm m. Cho P có I điểm bên trong và B điểm biên, khi đó: B1 B2 A(P ) = A(P1 ) + A(P2 ) = (I1 + − 1) + (I2 + − 1). 2 2 Vì bất kỳ nào nằm bên trong P1 hoặc P2 đều nằm trong P , và vì m − 2 điểm biên chung của P1 và P2 cũng là điểm thuộc miền trong của P , nên I = I1 +I2 +m−2. Lập luận tương tự ta cũng thu được B = B1 +B2 −2(m−2)−2. Do đó B B1 + B2 − 2(m − 2) − 2 I + − 1 = (I1 + I2 + m − 2) + −1 2 2 B1 B2 = (I1 + − 1) + (I2 + − 1) 2 2 = A(P ).
13 1.5.3 Các đường chéo bên trong Để hoàn thành chứng minh Định lý Pick ta phải chứng minh rằng mọi đa giác đơn có một đường chéo bên trong (tức là một đường chéo nằm trong hoàn toàn đa giác mà nó nối hai điểm là các đỉnh của đa giác) thì đường chéo này hoàn toàn nằm trong đa giác tạo thành bởi hai của đỉnh của nó. Ví dụ sau cho ta thấy sự tồn tại một đường chéo bên trong đa giác. Hình 1.6: Sự tồn tại của đường chéo bên trong Chứng minh sự tồn tại của đường chéo bên trong ở ví dụ hình trên được mô tả qua từng bước như sau: Trước tiên tìm một góc ABC sao cho miền trong của đa giác nằm ở phía bên của góc nhỏ hơn 180o . Sau đó ta chia ra làm hai trường hợp. Trường hợp 1, đoạn AC nằm hoàn toàn trong đa giác, trường hợp này ta có đường chéo bên trong là AC ; trường hợp 2, một số phần của đa giác (như GJKL trong Hình 1.6) đi vào bên trong tam giác ABC . Khi đó chỉ có hữu hạn đỉnh của đa giác ở miền trong của tam giác ABC ; qua mỗi điểm đó, ta dựng một đường thẳng vuông góc với đường phân giác của góc ABC . Rõ ràng đường thẳng nối B với đỉnh nằm trên đường vuông gần nhất với điểm B sẽ nằm hoàn toàn bên trong đa giác (nếu không thì nó sẽ cắt một cạnh khác của đa giác, và tại một đầu của cạnh đó sẽ có một đường vuông góc với đường phân giác của góc ABC mà nó gần với B hơn,
14 đó là điều mâu thuẫn). Lưu ý rằng chúng ta không thể sử dụng các đỉnh gần nhất với B . Trong Hình 1.6, J là điểm gần B nhất nhưng rõ ràng đoạn JB cắt đoạn KL. 1.5.4 Đa giác có lỗ thủng Cho đến nay, tất cả các đa giác đơn chúng ta đã xem xét, chúng đều không có lỗ thủng. Trong Hình 1.7 là năm ví dụ về đa giác có lỗ thủng. Đa giác A, B và C có một lỗ thủng, trong khi đa giác D và E đều có hai lỗ thủng. Những ví dụ đơn giản này đủ thấy rằng không khó để tính toán các diện tích các phần đa giác mà nó nằm ngoài 1 lỗ thủng hoặc ngoài nhiều lỗ thủng. Hình 1.7: Đa giác có lỗ thủng BX X IX BX AX IX + −1 2 A 0 16 8 7 B 8 30 23 22 C 6 19 15,5 14,5 D 8 40 29 27 E 3 52 30 28
15 Bảng trên cho thấy số lượng, bao gồm cả diện tích thực tế và diện tích được dự đoán bởi công thức mà tính toán cho đa giác không có lỗ thủng. Trong trường hợp có một lỗ thủng, ta có một lỗi là 1; trường hợp có hai lỗ thủng, số lỗi này là 2. Trong thực tế, nếu ta thử thêm một vài ví dụ nữa với một, hai, hoặc nhiều lỗ thủng và thêm các mục bổ sung vào bảng trên đây, thì ta sẽ nhận ra rằng diện tích này dường như được cho bởi công thức sau đây BX A(X) = IX + − 1 + n trong đó n là số lỗ thủng. 2 Vì chúng ta đã biết công thức tính diện tích cho các đa giác không có lỗ thủng, nên ta có thể sử dụng thông tin kết quả này để tìm ra công thức tính diện tích của một đa giác có các lỗ thủng. Đầu tiên, ta sẽ tìm công thức tính diện tích đa giác có một lỗ thủng và sau đó chúng ta sẽ mở rộng công thức tính cho trường hợp tổng quát có n lỗ thủng. • Đối với trường hợp có một lỗ thủng duy nhất, ta cần chỉ ra rằng diện tích của đa giác được cho bởi công thức A(X) = IX + B2X − 1 + 1 = IX + B2X . Giả sử các đa giác bên ngoài có diện tích A(X)o , có (IX )o điểm bên trong và có số điểm biên là (BX )o . Các đa giác tạo nên các lỗ thủng có diện tích A(X)h và có (IX )h điểm bên trong và (BX )h điểm biên. Từ những gì ta đã trình bày từ lúc trước, ta biết rằng A(X)o = (IX )o + (BX )o 2 − 1 và A(X)h = (IX )h + (BX2 )h − 1. Vì A(X) = A(X)o − A(X)h , nên ta có A(X) = (IX )o − (IX )h + (BX )o −(B 2 X )h . Nếu IX và BX là số lượng các điểm ở miền trong và điểm biên của toàn bộ đa giác đó bao gồm cả các lỗ thủng, thì ta có IX = (IX )o − (IX )h − (BX )h và BX = (BX )o + (BX )h . Sử dụng các công thức này và một chút biến đổi số học ta thu được BX (BX )o − (BX )h IX + = IX − (IX )h + = A(X), 2 2 đây chính xác là những gì chúng ta cố gắng chứng minh. • Trường hợp tổng quát - Đa giác có n lỗ thủng. Tính toán tương tự có thể được thực hiện cho đa giác tùy ý với số lượng lỗ thủng bất kỳ. Tương tự như trước đây, ta ký hiệu A(X)o là diện tích của đa giác bên ngoài (với
16 (IX )o và (BX )o các điểm trong và các điểm biên) có n lỗ thủng với diện tích là Ai , với 1 ≤ i ≤ n và có Ii và Bi điểm trong và điểm biên. Diện tích A(X) của đa giác có lỗ thủng (có IX điểm trong và BX điểm biên) được cho bởi: n X A(X) = A(X)o − Ai . i=1 (BX )o Bi Vì A(X)o = (IX )o + 2 − 1 và Ai = Ii + 2 − 1, nên chúng ta có n (BX )o X Bi A(X) = (IX )o + −1− (Ii + − 1) 2 i=1 2 n Bo X Bi = (IX )o + −1+n− (Ii + ) 2 i−1 2 Pn Ta dễ nhận thấy rằng IX = (IX )o − i−1 (Ii + Bi ) và có BX = (BX )o + Pn i−1 Bi . Do đó n BX (BX )o X Bi IX + − 1 + n = (IX )o + − (Ii + ) − 1 + n = A(X). 2 2 i−1 2 Đó chính là những gì chúng ta đang cố gắng để chứng minh.