Ví dụ về định lý Pick
Định lý Pick cung cấp một phương pháp hiệu quả để tính diện tích của đa giác đơn giản, với các đỉnh nằm trên lưới điểm có tọa độ nguyên trong mặt phẳng x−y Khái niệm "đơn giản" ở đây chỉ ra rằng đa giác không có lỗ thủng và các cạnh không cắt nhau Mặc dù các đa giác trong Hình 1.1 đều là đa giác đơn giản, thuật ngữ "đơn giản" chỉ mang ý nghĩa nhất định, vì một đa giác đơn giản về mặt kỹ thuật có thể có tới một triệu cạnh.
Để xác định rõ ràng một đa giác với một miền trong lớn, số lượng điểm lưới bên trong miền này sẽ được sử dụng để xấp xỉ Chúng ta có thể cải thiện độ chính xác của xấp xỉ bằng cách thêm khoảng một nửa số điểm lưới nằm trên "biên", vì chúng nằm ở vị trí nửa trong và nửa ngoài của đa giác Hãy xem xét một vài ví dụ trong Hình 1.1, trong đó I đại diện cho số điểm trong miền và B là số điểm nằm trên biên.
Hình 1.1: Ví dụ về định lý Pick’s
Để ước tính diện tích của đa giác E và F, cần một cách tiếp cận phức tạp hơn Đa giác E có thể được chia thành một hình chữ nhật có kích thước 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:
Tính diện tích cho trường hợp này thực sự phức tạp hơn, nhưng sau khi điều chỉnh và loại bỏ một số phần, chúng ta đã nhận ra kết quả rõ ràng hơn.
2 = 22. Đ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
2 luôn luôn đạt được một kết quả chính xác đó là diện tích cộng thêm
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
2 −1 với IP là số điểm lưới nằm hoàn toàn bên trongP 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.
Định lý Pick cho hình chữ nhật
Thay vì nỗ lực chứng minh tổng quát ngay từ đầu, chúng ta nên kiểm tra tính đúng đắn của Định lý Pick qua một số trường hợp đơn giản Trường hợp đơn giản nhất để nghiên cứu 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), đ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ệ
Đối với hình chữ nhật có kích thước m×n với các đỉnh trên lưới nguyên và các cạnh song song với trục Ox, Oy, định lý Pick vẫn đúng Diện tích của hình chữ nhật này là m×n, và số điểm trong hình chữ nhật được tính là I = (m − 1) × (n − 1) Số điểm biên của hình chữ nhật là B = 2m + 2n Như vậy, với hình chữ nhật kích thước m×n, chúng ta có công thức xác định số điểm trong và biên một cách rõ ràng.
= (mn−m−n+ 1) + (m+ n)−1 =mn, đó chính là công thức I + B
Tam giác vuông canh bên phải
Việc xác định công thức cho các tam giác vuông canh bên phải, nơi hai cạnh góc vuông nằm dọc theo các đường lưới, có thể gặp một số khó khăn Để làm rõ điều này, ta có thể chọn một tam giác làm nửa của một hình chữ nhật và thêm một đường chéo, như minh họa trong Hình 1.3.
Xét một hình tam giác vuông T với hai cạnh góc vuông dài m và n, diện tích của tam giác này được tính bằng A(T) = mn/2 Để xác định số điểm trong và điểm biên của tam giác, chúng ta có thể đếm các điểm biên dọc theo hai cạnh Tuy nhiên, một số điểm lưới có thể không nằm trên đường chéo của tam giác, nhưng điều này không ảnh hưởng đến kết quả Đối với tam giác vuông với cạnh góc vuông dài m và n, giả sử có k điểm trên đường chéo (không tính hai điểm ở đỉnh), ta có thể dễ dàng tính toán số lượng các điểm trong và biên của tam giác.
Định lý Pick cho tam giác vuông với cạnh bên phải điểm biên là m + n + 1 + k Số lượng điểm bên trong tam giác dễ dàng tính toán: với hình chữ nhật có độ dài cạnh m và n, sẽ có (m−1)(n−1) điểm bên trong Sau khi trừ đi k điểm nằm trên đường chéo, số điểm còn lại là (m−1)(n−1)−k, gấp đôi số điểm bên trong của tam giác Do đó, số điểm bên trong của tam giác được tính là I = (m−1)(n−1)−k.
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:
Như vậy định lý Pick đúng trong trường hợp này.
Định lý Pick cho tam giác bất kỳ
Giả sử Định lý Pick áp dụng cho tam giác vuông và hình chữ nhật có cạnh song song với trục, ta có thể chứng minh rằng định lý này cũng đúng cho bất kỳ tam giác nào Nhiều trường hợp khác nhau có thể được xem xét, nhưng tất cả đều tương tự như hình 1.4, nơi một tam giác tùy ý T có thể được mở rộng thành hình chữ nhật bằng cách thêm vào một số tam giác vuông Trong ví dụ này, ba tam giác A, B và C được bổ sung để đạt được yêu cầu.
Hình 1.4: Định lý Pick cho tam giác bất kỳ
Giả sử tam giác A có I A điểm miền trong và B A điểm trên biên; tam giác B có I B điểm miền trong và B B điểm trên biên; tương tự cho tam giác C Hình chữ nhật được xây dựng từ các tam giác này sẽ được xác định theo các thông số trên.
R, và giả sử R có số điểm miền trong là I R và số các điểm trên biên là B R
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 ta có:
Ta muốn chỉ ra rằng A(T) = I T + B T
2 −1. Nhìn vào hình vẽ ta biết rằng
Giả sử hình chữ nhật R có kích thước m×n, diện tích A(R) được tính bằng mn, chu vi B R là 2m + 2n, và số điểm biên I R là (m−1)(n−1) Khi tính toán điểm biên một cách chính xác, ta có công thức BA + BBb + BC = BR + BT.
Để tính toán, cần lưu ý rằng 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 Do đó, việc đếm số điểm bên trong hình chữ nhật là một bước quan trọng trong quá trình này.
Để hoàn thiện phương trình, cần có số -3 ở cuối vì các góc của tam giác được tính hai lần Thay thế giá trị B R từ công thức (3) vào phương trình (4) sẽ cho ra kết quả mong muốn.
I R = I A +I B +I C + I T +B T −3 (5)Bây giờ ta thay thế các giá trị của B R và I R từ phương trình (3) và (5) vào phương trình (2), và sau khi rút gọn, ta thu được kết quả:
= (IA +IB +IC +IT + BT −3)−IA −IB −IC
2 −1. Đó là chính xác những gì ta muốn trình bày.
Nếu bạn muốn áp dụng công thức đã nêu với các ví dụ trong Hình 1.4, bảng dưới đây cung cấp các giá trị cho cả bốn hình tam giác và hình chữ nhật.
Định lý Pick cho trường hợp tổng quát
Tổng quan về chứng minh
Theo trực giác, mọi đa giác đơn có thể được tạo thành từ các đa giác nhỏ hơn, điều này đã được chứng minh qua lý thuyết Pick Chúng ta đã chỉ ra rằng mọi đa giác lưới ba cạnh đều thỏa mãn định lý Pick Tiếp theo, chúng ta chứng minh rằng nếu định lý này đúng cho tất cả các đa giác ba cạnh, thì nó cũng đúng cho các đa giác bốn cạnh Cuối cùng, chúng ta tiếp tục chứng minh rằng nếu định lý Pick đúng cho tất cả các đa giác ba và bốn cạnh
Các quy tắc áp dụng cho đa giác 4 cạnh cũng đúng cho tất cả các đa giác 5 cạnh Nếu điều này đúng cho các đa giác 3, 4 và 5 cạnh, thì nó cũng sẽ đúng cho tất cả các đa giác 6 cạnh và tiếp tục cho các đa giác có nhiều cạnh hơn.
Kỹ thuật quy nạp toán học tổng quát đã chính thức được công nhận Trong thực tế, quá trình chứng minh không cần thực hiện vô hạn các bước, mà chỉ cần một số bước hữu hạn Chúng ta sẽ chứng minh qua hai bước, trong đó bước đầu tiên đã được xác nhận.
• 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.
Phần thứ hai của chứng minh áp dụng cho bất kỳ k cạnh nào, do đó, nó có hiệu lực cho tất cả các bước vô hạn được liệt kê trong hai đoạn trước.
Một ví dụ cụ thể về ý tưởng tổng quát được minh họa trong Hình 1.5 là một đa giác 23 cạnh, ABC W Chúng ta sẽ chứng minh rằng mọi đa giác có hơn ba cạnh đều có ít nhất một đường chéo bên trong, như đường chéo OW trong hình Đường chéo này sẽ chia đa giác thành hai đa giác nhỏ hơn: một đa giác có 16 cạnh (ABC MNOW) và một đa giác có 9 cạnh (OPQ W) Theo giả thiết quy nạp, định lý Pick đã được chứng minh đúng cho tất cả các đa giác có từ ba cạnh trở lên.
Định lý Pick áp dụng cho các đa giác có từ 3 đến 22 cạnh, và trong trường hợp cụ thể này, nó đúng cho các đa giác có 16 và 9 cạnh Hơn nữa, nếu hai đa giác thỏa mãn định lý Pick và được gắn với nhau qua một cạnh chung, thì đa giác kết quả cũng sẽ thỏa mãn định lý Pick.
Nếu hai đa giác đều thỏa mãn định lý Pick, thì phần ghép lại của chúng cũng sẽ thỏa mãn định lý này.
Hình 1.5: Định lý Pick cho trường hợp tổng quát
Ghép nối hai đa giác lưới
Giả sử có hai đa giác phụ P1 và P2 của đa giác P ban đầu, trong đó P1 chứa I1 điểm bên trong và các điểm trên biên là B1, còn P2 có I2 điểm bên trong và các điểm trên biên là B2 Đường chéo chung của đa giác P ngăn giữa P1 và P2 chứa điểm m Tổng số điểm bên trong của đa giác P là I.
Vì mọi điểm trong P1 và P2 đều thuộc miền P, và m−2 điểm biên chung của P1 và P2 cũng nằm trong miền P, ta có I = I1 + I2 + m−2 Tương tự, ta có B = B1 + B2 − 2(m−2) − 2.
Các đường chéo bên trong
Để chứng minh Định lý Pick, cần xác minh rằng mọi đa giác đơn đều có ít nhất một đường chéo nằm hoàn toàn bên trong nó, nối hai đỉnh của đa giác Đường chéo này phải hoàn toàn nằm trong đa giác được tạo thành bởi hai đỉnh mà nó kết nối.
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, trước tiên cầ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 180 độ Có hai trường hợp cần xem xét: Trường hợp 1, nếu đoạn AC nằm hoàn toàn trong đa giác, thì AC chính là đường chéo bên trong Trường hợp 2, nếu một số phần của đa giác như GJ KL nằm trong tam giác ABC, chỉ có hữu hạn đỉnh của đa giác nằm trong miền của tam giác này Từ mỗi đỉnh đó, ta dựng một đường thẳng vuông góc với đường phân giác của góc ABC, và đường thẳng nối B với đỉnh gần nhất sẽ hoàn toàn nằm bên trong đa giác, điều này không mâu thuẫn với giả thiết ban đầu.
Lưu ý rằng chúng ta không thể sử dụng các đỉnh gần nhất với B TrongHình 1.6, J là điểm gần B nhất nhưng rõ ràng đoạn J B cắt đoạn KL.
Đa giác có lỗ thủng
Cho đến nay, tất cả các đa giác đơn mà chúng ta đã xem xét đều không có lỗ thủng Hình 1.7 minh họa năm ví dụ về đa giác có lỗ thủng, cho thấy sự đa dạng và tính phức tạp của các hình dạng này.
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
Bảng trên trình bày số lượng diện tích thực tế và diện tích dự đoán cho đa giác không có lỗ thủng Khi có một lỗ thủng, số lỗi là 1; với hai lỗ thủng, số lỗi tăng lên 2 Thực tế cho thấy, nếu thử nghiệm với nhiều ví dụ có một, hai hoặc nhiều lỗ thủng và bổ sung thêm các mục vào bảng, ta sẽ nhận thấy diện tích được tính toán theo công thức sau đây.
2 −1 +n trong đó n là số lỗ thủng.
Chúng ta có thể áp dụng công thức tính diện tích cho các đa giác không có lỗ thủng để tìm ra diện tích của đa giác có lỗ thủng Đầu tiên, cần xác định công thức cho đa giác có một lỗ thủng, sau đó mở rộng để tính cho trường hợp tổng quát với n lỗ thủng.
Đối với trường hợp có một lỗ thủng duy nhất, diện tích của đa giác được tính theo công thức A(X) = I(X) + B/2 - 1 Giả sử các đa giác bên ngoài có diện tích A(X)o, với I(X)o điểm bên trong và B(X)o điểm biên Các đa giác tạo thành lỗ thủng có diện tích A(X)h, với I(X)h điểm bên trong và B(X)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+
2 −1 và A(X) h = (I X ) h + (B X 2 ) h −1 Vì A(X) = A(X) o −A(X) h , nên ta có A(X) = (I X ) o −(I X ) h + (B X ) o −(B 2 X ) h
Nếu I X và B X 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ó
I X = (I X ) o −(I X ) h −(B X ) h và B X = (B X ) o + (B X ) 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
2 = A(X), đây chính xác là những gì chúng ta cố gắng chứng minh.
Trong trường hợp tổng quát, đa giác có thể có n lỗ thủng, và các phép tính tương tự có thể áp dụng cho bất kỳ đa giác nào với số lượng lỗ thủng tùy ý.
Diện tích A(X) của đa giác có n lỗ thủng, với mỗi lỗ thủng có diện tích A_i (1 ≤ i ≤ n) và I_i, B_i là số điểm trong và điểm biên tương ứng, được xác định dựa trên các điểm trong và điểm biên của đa giác.
Vì A(X) o = (I X ) o + (B X 2 ) o −1 và A i = I i + B 2 i −1, nên chúng ta có
Ta dễ nhận thấy rằng I X = (I X ) o − P n i−1 (I i + B i ) và có B X = (B X ) o +
2 )−1 +n = A(X). Đó chính là những gì chúng ta đang cố gắng để chứng minh.
Dãy Farey đã thu hút sự chú ý của nhiều nhà toán học trong thế kỷ trước, và với sự phát triển của các thuật toán mới, nhiều nghiên cứu thú vị về dãy Farey đã được công bố gần đây Chương này sẽ đề cập đến việc tìm kiếm một phân số bất kỳ trong dãy Farey và mối liên hệ của vấn đề này với quá trình xử lý hình ảnh.
Chúng tôi đề xuất một thuật toán mới để tìm phân số gần nhất trong dãy Farey F_n với một phân số tùy ý p/q (với 0 < p < q) bằng cách sử dụng phương pháp Regula Falsi và khái niệm Bảng Farey Tất cả các phép toán được thực hiện trong tập hợp các số nguyên, mang lại nhiều thuận lợi Bên cạnh đó, chúng tôi cũng khám phá một số ứng dụng của dãy Farey trong xử lý ảnh khi có điều kiện thích hợp và trình bày một số kết quả thử nghiệm để minh họa tính hiệu quả và khả quan của phương pháp này.
Khái niệm và tính chất
Vào năm 1816, John Farey đã phát minh ra dãy Farey, một quy luật tạo ra các phân số thực sự trong khoảng [0,1] Dãy Farey thứ n, ký hiệu F n, bao gồm các phân số tối giản trong khoảng [0,1] với mẫu số nhỏ hơn hoặc bằng n, được sắp xếp theo thứ tự tăng dần.
Mỗi dãy Farey bắt đầu với giá trị 0 (0/1) và kết thúc với giá trị 1 (1/1) Đặc biệt, dãy F_n được tạo ra từ dãy F_{n-1} bằng cách chèn phân số trung gian a+a b+b 0 0 giữa các cặp phân số liên tiếp của F_{n-1}, đồng thời loại bỏ các phân số tối giản có mẫu lớn hơn n Ngoài ra, mỗi dãy (trừ F_1) có số lượng hạng tử lẻ và luôn có hạng tử ở giữa là 1/2.
Trong dãy Farey, một phân số \( \frac{p}{q} \) thuộc \( F_n \) được gọi là có hạng \( r \) nếu tồn tại chính xác \( r - 1 \) phân số trong \( F_n \) nhỏ hơn \( \frac{p}{q} \).
Hình 2.1: Một dãy Farey F n có f max phân số với hạng lần lượt là 1, 2, , f max
Trong nghiên cứu về dãy Farey, có hai vấn đề chính cần giải quyết Thứ nhất là bài toán xác định hạng của một phân số p/q trong dãy Fn Thứ hai là bài toán thống kê thứ tự, trong đó cho trước hai số nguyên dương n và k, mục tiêu là tìm phần tử có hạng k trong dãy Fn.
Tiếp theo ta xét một số tính chất của dãy Farey, liên quan đến vấn đề ta quan tâm.
Mệnh đề 2.1.1 Cho hai phân số a b < d c là hai phân số liên tiếp nhau trong dãy Fn khi đó bc−ad = 1 và b+d ≥n+ 1.
Trong bài viết này, chúng ta chứng minh rằng đối với hai phân số liên tiếp a/b và d/c trong dãy F_n, ta có bc - ad = 1 Cụ thể, đẳng thức 1.1 - 0.0 = 1 đúng với F_1, và bất đẳng thức 1 + 1 ≥ 1 + 1 cũng đúng với F_1 Giả sử kết quả đúng với các phân số liên tiếp a/b và d/c của F_n, trong đó F_n chứa các phân số a/b, d/c Nếu b + d < n + 1, thì phân số a+c/b+d đã xuất hiện trong F_n, dẫn đến mâu thuẫn với tính chất liên tiếp của a/b và d/c Do đó, ta kết luận rằng chỉ có thể xảy ra trường hợp b + d ≥ n + 1.
(a+ c)b−a(b+d) = bc−ad = 1 và c(b+ d)−(a+c)d= bc−ad = 1 đồng thời b+b+ d ≥b+n+ 1≥ n+ 2 và b+d+d ≥ n+ 1 +d ≥ n+ 2.
Do đó kết quả đúng cho Fn+1.
Mệnh đề 2.1.2 Nếu a b < d c , thì phân số trung gian a+c b+d thỏa mãn a b < a+c b+d < c d. Chứng minh Bởi vì a+c b+d − a b = b(b+d) bc−ad > 0 và d c − a+c b+d = d(b+d) bc−ad > 0.
Mệnh đề 2.1.3 Cho số thực x tùy ý thuộc [0,1], khi đó có một phân số a/b trong F n thỏa mãn a b gần nhất x sao cho |x− a b | ≤ b(n+1) 1
Bằng cách áp dụng thuật toán tìm kiếm nhị phân, chúng ta có thể giả định rằng x nằm giữa hai phân số liên tiếp a/b và c/d trong dãy Farey F_n Theo tính chất này, ta có bc - ad = 1 với b ≤ n và d ≤ n Hơn nữa, ta biết rằng a/b < x < (a+c)/(b+d) Nếu a/b < x < (a+c)/(b+d), thì x - a/b < (a+c)/(b+d) - a/b, từ đó suy ra x - a/b < (b(b+d))/b(b+d) = 1 Điều này cho thấy b + d ≥ n + 1.
Trường hợp a+c b+d < x < c d , lập luận tương tự ta suy ra c d −x < 1 b(n+ 1).
Với giá trị n lớn, số lượng phân số trong F n, hay hạng lớn nhất của F n, có thể được ước lượng bằng công thức xấp xỉ 3n²/π², tương đương với 0,304n², và được ký hiệu là O(n²).
Chứng minh Ta sử dụng hàm Eurlerϕ(n) đếm số các số tự nhiênkthỏa mãn
Khi 1 ≤ k ≤ n và gcd(k, n) = 1, theo công thức Euler, nếu n được phân tích thành n = p α 1 1 p α t t, thì ϕ(n) = n(1− 1/p 1) (1− 1/p t) = n[p 1 − 1/p 1] [p t − 1/p t] ≤ cn, với c thỏa mãn 0 ≤ c ≤ 1 Dãy Farey F n bao gồm tất cả các phân số tối giản có mẫu số nhỏ hơn hoặc bằng n Để tạo ra Fn+1, ta cần thêm tất cả các phân số tối giản mới có mẫu số là n+1 và tử số nguyên tố cùng nhau với n+1 Do đó, |F n+1| = |F n| + ϕ(n+1) với n ≥ 2 Khi n = 1, ta có kết quả tương ứng.
F 1 = 1 +ϕ(1) Từ đó ta tính được công thức
2 = O(n 2 ). Định nghĩa 2.1.3 Một bảng Farey T n của dãy F n là một ma trận cỡ
Trong biểu thức (n+1)×n, mỗi dòng i (0≤ i ≤ n) đại diện cho một tử số, trong khi mỗi cột j (1≤ j ≤ n) biểu diễn một mẫu số Hạng của phân số j i trong F n được ký hiệu là T n (i, j) Đối với một phân số j i 0 0 được rút gọn về j i, ta có T n (i 0 , j 0 ) = T n (i, j) Do F n chỉ chứa các phân số thực sự trong khoảng [0,1], nên chúng ta không xem xét T n (i, j) trong các trường hợp i > j.
Bảng Farey có một số tính chất khá hay có liên quan đến bài toán của ta như sau.
Hình 2.2: Minh họa cho bảng Farey T 4 của dãy F 4 Ta có T 4 = { p q | 0 ≤ p ≤ q ≤ 4}={ 0 1 , 1 4 , 1 3 , 1 2 , 2 3 , 3 4 , 1 1 }
Nếu x và y là hai phân số của F n cách đều điểm giữa (tức là điểm 1/2), thì tổng x và y sẽ bằng 1 Đồng thời, tổng hạng của x và y sẽ là fn + 1, trong đó fn là hạng lớn nhất của các phần tử trong dãy F n.
Trong bảng Farey T n, các phân số được sắp xếp theo thứ tự giảm dần từ trái sang phải trong cùng một hàng, ngoại trừ hàng đầu tiên, nơi tất cả các phân số đều có hạng là 1.
(iii) Trong một bảng Farey T n , các hạng ở các cột thì tăng từ trên xuống.
Cặp phân số x và y được xác định cách đều hai bên điểm giữa, với x = j i và y = 1− j i = j−i j, dẫn đến tổng x+y = 1 Nếu x được biểu diễn là ax, thì hạng của y sẽ là fn + 1−ax Do đó, tổng hạng của x và y là fn + 1.
Trên cùng một hàng, tất cả các phân số có tử số là i và mẫu số là i, i+1, i+2, cho đến n, từ trái sang phải Do đó, đối với bất kỳ hai phân số j và i, ta có thể so sánh chúng một cách dễ dàng.
2; do đó T n (i, j 1 ) > T n (i, j 2 ). (iii) Chứng minh tương tự.
Mệnh đề 2.1.6 cho thấy rằng độ khác biệt giữa các hạng liên tiếp trong cùng một cột j của Tn có tính chất đối xứng, với hướng lên tương ứng với hướng xuống, và được tính từ điểm giữa cột trong Tn, như minh họa trong Hình 2.2.
Chứng minh Quan sát thấy rằng i+1 j + j−i−1 j = j i + j−i j = 1 Do đó từ Mệnh đề 2.1.5 (i), ta có
Công thức Tn(i+1, j) + Tn(j−i−1, j) = Tn(i, j) + Tn(j−i, j) = fmax + 1 thể hiện mối quan hệ giữa các phân số trong dãy F n, trong đó fmax là số lượng phân số trong dãy này Đặc biệt, mỗi cặp phân số đối xứng qua điểm giữa của dãy F n có tổng hạng là fmax + 1.
Tìm kiếm phân số gần nhất trong dãy Farey F n
Thuật toán tìm kiếm cải tiến
Trong một số trường hợp, các điểm "zero-crossing" có thể nằm gần các điểm biên f1 hoặc f2, khiến thuật toán tìm kiếm nhị phân mất thời gian O(logn) để tìm kết quả Các hình ảnh trong Hình 2.4, 2.5, và 2.6 cho thấy tính chất tuyến tính thuần túy của vấn đề, do đó, phương pháp Regula Falsi được áp dụng để tìm nghiệm của hàm liên tục là một lựa chọn hiệu quả hơn Với tính chất tuyến tính của đường cong, điểm giao nhau tìm được gần với nghiệm của hàm số, dẫn đến việc thuật toán mới (xem Hình 2.7) tìm thấy điểm nghiệm nhanh hơn Ví dụ, với n = 55 và phân số chìa khóa p/q = 341/556, thuật toán xác định phân số gần nhất là 27/44, với hạng của phân số này trong F 55 là f = 577.
Phân tích hiệu suất
Để so sánh hiệu suất của hai thuật toán, chúng tôi đã chọn một tập ngẫu nhiên các phân số thực trong khoảng [0,1] và thực hiện nhiều lần tính toán với các giá trị n trong khoảng 50 đến 400 Kết quả thực nghiệm cho thấy thuật toán cải tiến FindClosestFast vượt trội hơn hẳn so với thuật toán tìm kiếm nhị phân truyền thống Đặc biệt, hiệu suất của FindClosestFast càng tốt hơn khi n tăng, với khoảng cách giữa hai đường cong ngày càng mở rộng.
Một số ứng dụng có liên quan đến hình ảnh
Đa giác mô phỏng gần đúng
Để mô tả đường biên của hình, chúng ta sử dụng chuỗi đoạn thẳng, giúp biểu diễn đa giác một cách thuận tiện Để đạt được sự mô phỏng hiệu quả và gần chính xác, các cạnh liên tiếp cần được chú ý.
Thuật toán cải tiến tìm phân số p/q (với 0 < p < q) trong dãy F_n gần như "thẳng hàng" và sáp nhập được trình bày trong Hình 2.7 Trong không gian kỹ thuật số, mỗi điểm tương ứng với một pixel, trong đó hai điểm đầu cuối của một đoạn thẳng có tọa độ nguyên Độ dốc của đoạn thẳng được xác định bởi ∆y và ∆x, với ∆y là sự chênh lệch nguyên giữa các tung độ y, và ∆x là sự chênh lệch nguyên giữa các hoành độ x của hai điểm đầu mút.
Nếu độ chênh lệch giữa các hạng của độ dốc hai đường thẳng nhỏ hơn ngưỡng ∆f (tùy thuộc vào bậc n của dãy F n), thì
Hình 2.8: So sánh 2 thuật toán dựa trên số lần lặp lại trung bình v s trong dãy F n
Đoạn AC sẽ được xem xét cho việc sáp nhập với đoạn kế tiếp trong lần tiếp theo Khi ngưỡng ∆f tăng lên, độ chính xác của mô phỏng hình xấp xỉ sẽ giảm (xem Hình 2.9).
Hình 2.9: Hình mô phỏng xấp xỉ ứng với các giá trị khác nhau của ngưỡng 4f với n = 200.
Hình ảnh ứng với 4f = 200 thể hiện sự chân thực hơn so với hình ảnh ứng với 4f = 800 Để phân tích độ dốc trong bảng Farey T n bậc n, chỉ những phân số thực sự và dương mới được xem xét từ đầu Ví dụ, với n = 10, bảng khởi đầu của T n bao gồm các hạng độ dốc hoặc các phân số trong tập hợp này.
Chúng ta thực hiện một số phép đối xứng trong bảng T n, bằng cách hoán đổi tử số và mẫu số, tạo ra tập hợp {p q | −n ≤ p, q ≤ n} Từ đó, chúng ta xác định các chỉ số tương ứng của chúng từ các phân số trong dãy F n.
Ta thu được một ma trận mới cỡ (2n+ 1)×(2n+ 1) (các phần tử của chúng được xác định theo công thức trên).
Phân tích hình ảnh
Mô tả hình ảnh đối tượng là một lĩnh vực nghiên cứu phức tạp, mặc dù đã có nhiều tài liệu cung cấp các phương pháp khác nhau Những mô tả này rất quan trọng cho việc nhận dạng tự động các đối tượng kỹ thuật số Hình dạng có thể được biểu diễn dưới dạng dãy số, giúp dễ dàng phân tích và xử lý Các dãy số này thường đại diện cho các góc trong đa giác và độ lệch của độ dốc giữa các đường thẳng Phương pháp này giữ tính ổn định khi quay hình ảnh và giảm thời gian xử lý, nhờ vào việc chỉ sử dụng bộ nhớ truy cập và phép trừ, cho phép áp dụng nhiều thuật toán liên quan đến hình dạng.
Hình 2.10 minh họa các phần tại các góc của đa giác mô phỏng gần đúng Khi đối tượng trong hình xám được quay, đa giác mô phỏng gần như không bị lệch Sau khi tính toán lại từ đa giác mô phỏng mới, các phần trong của các góc được đánh giá bằng các hạng của dãy Farey và độ sai khác của chúng trong việc nắm bắt các đặc tính hình dạng Ví dụ, v 1 trong Hình ?? có độ sai lệch hạng f 1 0 = 24650, và sau khi tính toán lại, giá trị này trở thành f 1 0 = 24739 Với n = 200, có 97856 phần tử trong ma trận Tn, do đó, f 1 0 = 24650 tương ứng với.
97856 ×360 o = 90,68 o và f 1 0 = 24739 với 24739 97856 ×360 o = 90,01 o ; tổng số lỗi là ít hơn 0,50 o , đó là một con số khá nhỏ.
Hình 2.10: Bất biến của đặc điểm hình dạng (độ sai khác của các hạng trong T n ) qua phép quay
Chương này nhấn mạnh rằng hạng của các phân số trong dãy Farey có thể cung cấp ước lượng hữu ích về giá trị tương đối của chúng Việc tìm kiếm phân số trong dãy Farey được cải thiện nhờ vào bảng Farey, và các thuật toán tìm phân số gần nhất với một phân số bất kỳ trong dãy Farey cũng được trình bày Tất cả các thuật toán này không sử dụng thao tác của các điểm nổi, giúp tiết kiệm thời gian cho các chức năng cơ bản Bảng Farey có nhiều ứng dụng trong xử lý hình ảnh kỹ thuật số và phân tích hình dạng, đồng thời đặt ra những vấn đề quan trọng như nén bảng bằng cách loại bỏ các cột có sai lệch hạng lớn nhất Những kết quả này sẽ tiếp tục được nghiên cứu trong tương lai gần.
Vòng tròn Ford và liên hệ với định lý Pick, dãy Farey
Lester R Ford (1886-1964) là một nhà toán học nổi bật người Mỹ, nhận bằng tiến sĩ từ Đại học Harvard năm 1917 Ông nổi tiếng với khái niệm "vòng tròn Ford", được giới thiệu trong bài báo năm 1938 mang tên "Phân số" Ford từng là biên tập viên của tạp chí toán học hàng tháng của Mỹ từ 1942 đến 1946 và giữ chức Chủ tịch Hiệp hội Toán học Hoa Kỳ từ 1947 đến 1948 Để ghi nhận những đóng góp của ông cho lĩnh vực toán học, Hiệp hội Toán học Hoa Kỳ đã thiết lập "giải thưởng Lester R Ford" vào năm 1964, nhằm vinh danh các tác giả công bố kết quả nghiên cứu trong tạp chí "The American Mathematical Monthly".
Giới thiệu vòng tròn Ford
Vòng tròn Ford là một hình học dùng để minh họa các phân số, thể hiện rằng có thể tìm thấy một phân số giữa hai phân số a/b và c/d bằng cách xác định phân số trung gian a+b/c+d Để biểu diễn hình học của các phân số này, chúng ta vẽ các điểm trên trục Ox trong mặt phẳng tọa độ xOy, với x = a/b, trong đó a và b là các số nguyên và phân số ở dạng tối giản Từ đó, ta xây dựng một vòng tròn có bán kính 2b + 1/2, với tâm tại điểm a/b, tiếp xúc với trục Ox trong góc phần tư thứ nhất của mặt phẳng tọa độ.
Vòng tròn L 1 2 1 8 Vòng tròn M 2 3 18 1 Vòng tròn N 3 4 32 1 Vòng tròn O 4 3 18 1
Việc biểu diễn các phân số dưới dạng vòng tròn giúp Ford khẳng định định lý đầu tiên của ông về các phân số này Định lý 3.1.1 (Ford, 1938) nêu rõ rằng hai vòng tròn đại diện cho hai phân số riêng biệt sẽ tiếp xúc nhau hoặc hoàn toàn nằm ngoài nhau.
Để chứng minh định lý, chúng ta cần xem xét khoảng cách giữa các tâm của hai vòng tròn được tạo ra từ các phân số tối giản a/b và c/d Khoảng cách này được biểu diễn bằng đoạn thẳng (P Q), nối từ điểm có tung độ (2b + 1/2) đến điểm có tung độ (2d + 1/2).
| sẽ tạo ra một đường thẳng (P R) song song với trục Ox Hai đường thẳng
P Q và P R sẽ tạo thành một tam giác vuông với cạnh góc vuông QR có độ dài là | 2d 1 2 − 2b 1 2|.
Sử dụng định lý Pitago ta được:
Nếu |bc−ad| > 1, thì PQ lớn hơn PS + TQ, cho thấy hai vòng tròn nằm bên ngoài nhau Khi |bc−ad| = 1, PQ bằng PS + TQ, nghĩa là hai vòng tròn tiếp xúc nhau Ngược lại, nếu |bc−ad| < 1, thì
|bc−ad| = 0 (vì là số nguyên) nên a b = c d điều này là không thể; vậy không thể xảy ra trường hợp |bc−ad| < 1|.
Khi |bc−ad| = 1, ta có P Q = P S + T Q, và hai vòng tròn sẽ tiếp xúc với nhau Mối quan hệ giữa hai vòng tròn tiếp xúc cho phép chúng ta xây dựng một vòng tròn nhỏ hơn, tiếp xúc với cả hai vòng tròn ban đầu và tiếp xúc trên trục Ox.
Vòng tròn Ford đặc biệt
Hình ảnh hai vòng tròn tiếp xúc cho phép chúng ta khám phá mối quan hệ giữa vòng tròn lớn hơn (1 1, 1 2) và vòng tròn nhỏ.
Bán kính của vòng tròn lớn gấp bốn lần bán kính của vòng tròn nhỏ, với bán kính nhỏ bằng 1/4 bán kính lớn Điều này đặt ra câu hỏi về tỷ số bán kính của vòng tiếp xúc khác Để xác minh, chúng ta sẽ tìm một vòng tròn nhỏ khác tiếp xúc với các vòng tròn hiện có.
Chúng ta có thể xác định một vòng tròn nhỏ hơn tiếp xúc với hai vòng tròn ban đầu tại các điểm trên trục Ox có giá trị 1 2 và 1 1 Bằng cách tính toán phân số trung gian giữa các bán kính hiện tại, ta có được phân số mới là (1+1)(2+1) = 2/3, điểm này nằm trên trục Ox và tạo ra vòng tròn mới Giá trị y của vòng tròn mới được tính là 2.(3 1/2) = 18 1.
Với ba vòng tròn kết nối, chúng ta quan sát xem bán kính của vòng tròn mới có bằng 1/4 giá trị của một trong hai vòng tròn hiện có hay không Vòng tròn mới tại tọa độ (2/3, 18/1) có bán kính bằng 1/9 lần bán kính của vòng tròn lớn nhất và bằng 4/9 lần bán kính của vòng tròn thứ hai Do đó, 1/4 không phải là một hằng số tỉ lệ.
Bằng cách tìm các phân số trung gian cho một số hạng mục tiếp theo, chúng ta có thể tạo ra các phân số liền kề mới và khám phá mối quan hệ giữa các tỉ lệ của các vòng tròn Bảng dưới đây minh họa các vòng tròn được hình thành từ các phân số liền kề và so sánh tỉ lệ bán kính của chúng.
Trường hợp x, y( a b , 2b 1 2) của vòng tròn mới
Bảng quan sát cho thấy rằng bán kính của các phân số trung gian bắt đầu từ cặp vòng tròn tại (1/1, 1/2) và (1/2, 1/8) Qua đó, chúng ta có thể phân tích tỷ lệ giữa các bán kính này.
Tỉ lệ giữa bán kính của vòng tròn lớn nhất và bán kính của vòng tròn mới nhất luôn là một số chính phương hoàn hảo, như 4/1, 9/1, 16/1, 25/1, và n²/1 Khi xây dựng bảng với các nhãn cho các vòng tròn như là các hạng mục, ta nhận thấy rằng các số chính phương liên tiếp có mối liên hệ với số lượng vòng tròn mới Đối với vòng tròn thứ n, tỷ lệ giữa vòng tròn lớn ban đầu và vòng tròn thứ n sẽ là n².
Chúng ta thậm chí có thể viết một công thức để vẽ ra vòng tròn thứ n này, biết rằng nó sẽ được đặt tại ( n−1 n , 2(n 1 2 )).
Có một vòng tròn Ford liên kết với mọi số hữu tỉ Hơn nữa, đường thẳng y = 1 có thể được coi là một vòng tròn Ford.
L.R Ford đã phát triển khái niệm về phân số, đặc biệt là mối liên hệ giữa phân số và bán kính của chúng Các vòng tròn Ford cung cấp một cách trực quan để hiểu về phân số trung gian và các mẫu liên kết với phân số Farey.
Mối liên hệ giữa định lý Pick và dãy Farey
Có một mối quan hệ giữa định lý Pick và ý tưởng toán học của dãy Farey.
Dãy Farey F_N cấp N là tập hợp các phân số tối giản m/n trong khoảng [0,1], với điều kiện mẫu số không vượt quá N Một phân số m/n thuộc về F_N khi và chỉ khi 0 ≤ m ≤ n ≤ N và gcd(m, n) = 1.
Mối quan hệ giữa định lý Pick và dãy Farey rất đơn giản: Khi vẽ hai cặp phân số liên tiếp từ dãy Farey trên lưới, sử dụng mẫu số và tử số như một cặp sắp thứ tự (m, n) và kết nối với điểm gốc (0,0), diện tích tam giác kết quả luôn là 1/2 Diện tích này không bao giờ chứa các điểm bên trong lưới, do đó, theo công thức Pick, diện tích A được tính bằng A = I + B/2 - 1 = 0 + 3/2 - 1 (với I = 0, B = 3) Điều này có thể được sử dụng như một minh chứng cho sự liên hệ giữa Định lý Pick và dãy Farey, với một số ví dụ được mô tả dưới đây.
Mối liên hệ giữa dãy Farey và vòng tròn Ford
Hai vòng tròn Ford C1 và C2 có các tâm là các phân số Farey liên tiếp, do đó chúng tiếp xúc với nhau Để chứng minh điều này, cần chỉ ra rằng các tâm của C1 và C2 là các phân số Farey liên tiếp a/b và c/d, với điều kiện a/b < c/d, dẫn đến tính chất bd - ac = 1 Tâm của C1 là a/b với bán kính 2√b, và tâm của C2 là c/d với bán kính 2√d.
4d 2 b 2 = c 2 d 2 − 2ac bd + a 2 b 2 download by : skknchat@gmail.com⇔
Đẳng thức cuối cùng được xác nhận đúng bởi vì c d và a b là các phân số Farey liên tiếp Điều này chứng tỏ đẳng thức ban đầu P Q = 2b 1 2 + 2d 1 2 cũng đúng, tức là tổng của hai bán kính C 1 và C 2 Do đó, C 1 tiếp xúc với C 2.
Vì vậy, các vòng tròn Ford có tâm được chỉ ra bởi các phân số Farey liên tiếp là các đường tròn tiếp xúc nhau.
Kết luận, luận văn này đã khám phá định lý Pick, phân số Farey và vòng tròn Ford, cho thấy sự ứng dụng của chúng trong nhiều lĩnh vực Đặc biệt, phân số Farey được sử dụng trong thiết kế thiết bị âm thanh nổi trong lý thuyết toán học về fractal và "hỗn loạn" Nghiên cứu này nhấn mạnh mối liên hệ chặt chẽ giữa toán học và thực tiễn ngay từ những khái niệm ban đầu.
Trong luận văn này, chúng tôi khẳng định rằng các chủ đề hình học và đại số có thể liên kết chặt chẽ với nhau Định lý Pick được sử dụng để chuyển từ những ý tưởng cơ bản đến lý luận toán học nâng cao thông qua dãy Farey và vòng tròn Ford Nhiều chương trình đào tạo thường khám phá các chủ đề này một cách riêng biệt, nhưng nghiên cứu của chúng tôi đã chỉ ra sự liên quan giữa chúng Những kết nối này không chỉ giúp hiểu sâu hơn về toán học mà còn thúc đẩy học sinh trong quá trình học tập.
Luận văn trình bày được các vấn đề sau đây:
1 Định lý Pick về tính diện tích 1 đa giác đơn.
2 Dãy Farey, vòng tròn Ford.
3 Mối liên hệ giữa các kiến thức trên.