Home > Combinatorics > Từ công thức Picard đến công thức Euler

Từ công thức Picard đến công thức Euler


(Bài này phỏng dịch lại theo các bài viết trên tạp chí Kvant)

Lưới nguyên là tập hợp tất cả các điểm trên mặt phẳng tọa độ Đê-các vuông góc với tọa độ nguyên. Một đa giác gọi là nguyên nếu như tất cả các đỉnh của nó đều thuộc về lưới nguyên . Trong bài này chúng ta sẽ tiếp cận công thức Picard cho diện tích các đa giác nguyên và công thức Euler cũng như chỉ ra mối liên hệ giữa chúng.

I – Tam giác nguyên thủy

Một tam giác nguyên được gọi là nguyên thủy nếu như ngoại trừ các đỉnh của nó thì không có điểm nào nằm trong và trên cạnh tam giác có tọa độ nguyên

s152.photobucket.com/albums/s165/dumb_boy1988/fig001.png
Hình 1.

Định lý 1. Tam giác nguyên là nguyên thủy khi và chỉ khi có có diện tích bằng

Chứng minh.

Cho tam giác nguyên thủy , xét hình chữ nhật nguyên nhỏ nhất với các cạnh song song với các trục tọa độ, chứa tam giác

Tất cả các trường hợp có thể xảy ra biểu diễn như trên hình 2.

s152.photobucket.com/albums/s165/dumb_boy1988/fig002.png
Hình 2.

Trường hợp a., b. rõ ràng tam giác không phải là nguyên thủy vì điểm trên hình vẽ có tọa độ nguyên. Trường hợp bao hàm cả trường hợp c., nếu như giả sử đỉnh có thể nằm trên (trường hợp đặc biệt có thể trùng với . Như vậy ta chỉ cần xét trường hợp , một cách không mất tính tổng quát, xem .

Kí hiệu là số các điểm nguyên nằm bên trong nhưng không nằm trên cạnh của đa giác . Khi đó dễ thấy

Vì trong đoạn không chứa điểm nguyên nên

Tương tự

Tam giác không chứa trong nó điểm nguyên nào nên

ở đây đúng bằng số điểm nguyên nằm trong , và các điểm nguyên nằm trên cạnh , trừ điểm .

Từ đó suy ra

rút gọn ta được

Kí hiệu là diện tích của hình phẳng , thế thì

Như vậy ta đã chứng minh chiều thuận của định lý. Ngược lại, giả sử tồn tại một tam giác nguyên với diện tích bằng mà không nguyên thủy. Khi đó ta cần chứng minh rằng tam giác nguyên luôn có thể phân hoạch thành các tam giác nguyên thủy.

s152.photobucket.com/albums/s165/dumb_boy1988/fig003.png
Hình 3.

Giả sử tam giác nguyên không nguyên thủy chỉ có các điểm nằm trên cạnh là nguyên. Khi đó tồn tại một cạnh chứa trong nó các điểm nguyên, ta nối các điểm này với đỉnh (hình [3]), trong các cạnh nối này không có chứa điểm nguyên nên các tam giác được chia ra, ngoại trừ nhiều nhất hai tam giác chứa cạnh (trong trường hợp trong các cạnh chứa điểm nguyên), đều là nguyên thủy. Kí hiệu hai tam giác không nguyên thủy này là , khi đó từ ta nối tương ứng với các điểm nguyên nằm trên cạnh . Khi đó toàn bộ các tam giác được chia ra đều là nguyên thủy.

s152.photobucket.com/albums/s165/dumb_boy1988/fig004.png
Hình 4.

Giả sử tam giác chứa trong nó một số điểm nguyên nào đó (hình [4]). Ta chọn ra một điểm và nối chúng với các đỉnh , thu được 3 tam giác nhỏ hơn. Ta tiếp tục quá trình chọn và phân hoạch tam giác đối với 3 tam giác nhỏ này. Vì số điểm nguyên nằm bên trong tam giác là hữu hạn nên đến một thời điểm thì quá trình này dừng và thu được các tam giác nguyên bên trong không chứa điểm nguyên nào, có thể trên cạnh có chứa điểm nguyên, và ta tiếp tục áp dụng cách phân hoạch như đã chỉ ra ở phần trên để thu được tất các các tam giác được phân hoạch đều là nguyên thủy.

Như vậy tam giác nguyên không nguyên thủy có thể phân hoạch ít nhất là 2 tam giác nguyên thủy, mà mỗi tam giác này có diện tích là 1/2 như đã chỉ ra ở phần thuận của định lý, từ đó , mâu thuẫn này cho ta chứng minh của phần đảo.

Bài tập 1. Chứng minh rằng với bất kì số luôn tồn tại tam giác nguyên thủy mà các chiều dài cạnh của nó đều lớn hơn .

II – Công thức Picard

Trong phần này khi nhắc đến đa giác, chúng ta xem chúng như là đa giác đơn, nghĩa là đa giác bị chặn và biên của nó là đường gấp khúc không tự cắt. Hình [5] là thí dụ về đa giác không đơn

s152.photobucket.com/albums/s165/dumb_boy1988/fig005.png
Hình 5.

Định lý 2. (Picard) Với đa giác nguyên thì diện tích của nó được tính theo công thức

trong đó là số điểm nguyên nằm trong, và là số điểm nguyên nằm trên cạnh của đa giác ngoại trừ các đỉnh của nó.

s152.photobucket.com/albums/s165/dumb_boy1988/fig006.png
Hình 6.

Thí dụ, như hình [6], ta có , áp dụng công thức Picard, thế thì diện tích đa giác nguyên này là

Chứng minh.

Trước hết bạn đọc hãy tự làm bài tập nhỏ sau

Bài tập 2. Bất kì một đa giác đơn có số đỉnh lớn hơn 4 đều tồn tại một đường chéo nằm hoàn toàn trong đa giác đó.

Từ đó bằng quy nạp dễ dàng chứng minh -giác có thể phân hoạch thành tam giác mà các đỉnh của chúng là các đỉnh của đa giác ban đầu. Do đó tổng các góc trong của một giác đơn đúng bằng .

Mỗi tam giác nhận được từ cách phân hoạch giác nguyên như trên ta có thể tiếp tục chia nhỏ chúng thành các tam giác nguyên thủy như cách đã trình bày ở định lý 1. Diện tích của mỗi tam giác nguyên thủy bằng , do đó số tam giác nguyên thủy được chia ra đúng bằng và do đó không phụ thuộc vào cách chia.

Và điều ta cần chứng minh tương đương với

s152.photobucket.com/albums/s165/dumb_boy1988/fig007.png
Hình 7.

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh là đỉnh của -giác bằng tổng các góc trong của đa giác này, và bằng (hình [7a]).

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh nằm trên cạnh và không trùng với đỉnh của giác đúng bằng (hình [7b]).

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh nằm bên trong đa giác đúng bằng (hình [7c]).

Mặc khác tổng tất cả các góc của tất cả các tam giác nguyên thủy được chia ra đúng bằng . Do dó

hay , là điều cần phải chứng minh.

Chú ý. Giả sử mặt phẳng được phân hoạch thành các hình bình hành bằng nhau bởi hai họ đường thẳng song song cắt nhau. Khi đó các đỉnh của các hình bình hành này lập thành một tập hợp gọi là lưới . Lưới nguyên là một trường hợp riêng khi mà hai họ đường thẳng song song vuông góc nhau, và mỗi hình bình hành trở thành hình vuông.

Giả sử đa giác với các đỉnh nằm trên lưới thỏa mãn công thức Picard mở rộng

Trong đó là diện tích của mỗi hình bình hành trong lưới .

III – Phân tích logic của lời giải

Chúng ta phát biểu lại một lần nữa ba khẳng định mà đã chứng minh ở phần trên

1. Với mỗi đa giác nguyên , ta có công thức Picard

2. Diện tích của mỗi tam giác nguyên thủy bằng .

3. Với bất kì sự phân hoạch đa ngác nguyên thành tam giác nguyên thủy, thế thì

Chúng ta có các lược đồ logic của chứng minh như trên hình 8.

s152.photobucket.com/albums/s165/dumb_boy1988/fig008.png
Hình 8.

Trong hình a, ta chứng minh được công thức Picard 1. một cách độc lập với 2. và 3., từ 1. suy ra 2. thì tầm thường và 3. suy ra từ 1. và 2. (xem bài tập 3)

Trong hình b, đó chính là lược đồ mà chúng ta đã chứng minh. Đầu tiên chứng minh 2. một cách độc lập, rồi từ đó nhận được 3., và công thức Picard là hệ quả của 2. và 3.

Chúng ta sẽ xem xét hai lược đồ chứng minh đáng chú ý còn lại.

Chúng ta có thể chỉ ra 3. suy ra 2. Thật vậy, chú ý rằng diện tích của bất kì tam giác nguyên luôn có dạng . Để làm rõ điều này, chúng ta ngoại tiếp tam giác nguyên này bằng hình chữ nhật nguyên nhỏ nhất có canh song song với hai trục tọa độ. Cũng như ở phần đầu, có tất cả các vị trí mô tả bằng hình [2]. Hình chữ nhật ngoại tiếp có diện tích là số nguyên và các tam giác bổ sung cũng có diện tích dạng một nửa số nguyên hoặc số nguyên, từ đó diện tích tam giác nguyên có dạng số nguyên hoặc nửa số nguyên, và rõ ràng luôn không bé hơn .

Bây giờ xét tam giác nguyên thủy , và là hình chữ nhật nhỏ nhất ngoại tiếp nó, chúng ta chia các phần bổ sung bên ngoài thành để thành thành các tam giác nguyên thủy. Đây la một sự phân hoạch thành các tam giác nguyên thủy , trong đó chứa cả .

Chúng ta cũng có thể phân hoạch thành các tam giác nguyên thủy theo một cách khác: chia đôi theo đường chéo các ô vuông đơn vị cấu thành nên . Giả sử diện tích của thì có tất cả tam giác nguyên thủy, và số tam giác nguyên thủy này là phụ thuộc vào cách phân hoạch. Quay lại các chia đầu tiên, chúng ta có

Lại có với mỗi , suy ra , và đặc biệt .

Bây giờ xem xét sự suy ra 1. từ 2. Xét hàm sau

xác định trên các đa giác nguyên (đơn).

s152.photobucket.com/albums/s165/dumb_boy1988/fig009.png
Hình 9.

Nếu phân hoạch một đa giác nguyên bởi một đường gấp khúc bên trong nó mà các đỉnh của đường gấp khúc là điểm nguyên thanh hai đa giác nguyên , chúng ta viết , xem hình [9]. Dễ dàng kiểm tra sự cộng tính của hàm

và diện tích cũng thỏa mãn sự cộng tính

Do đó nếu công thức Picard đúng cho các các đa giác nguyên thì cũng đúng cho cả . Và như đã biết, đa giác nguyên luôn phân hoạch được thành các tam giác nguyên thủy, trong khi 2. chính là trường hợp đặc biệt công thức Picard cho tam giác nguyên thủy.

Bài tập 3. Sử dụng các ngoại tiếp hình chữ nhật như đã nêu ở định lý 1. và hàm cộng tính để chứng minh 1. một cách độc lập với 2. và 3.

IV – Công thức Euler

Chúng ta gọi một bản đồ đa giác là “đúng” nếu đó là sự phân hoạch đa giác đơn thành các các đa khác đơn khác sao cho bất kì hai đa giác nào được chia ra hoặc là có một cạnh chung hoặc chỉ có một đỉnh chung, hoặc là không có điểm chung nào.

Bản đồ đa giác đúng có thể xem như là một trường hợp riêng của đồ thị phẳng. Ta gọi các đa giác trong phân hoạch là các diện, và các cạnh của các đa giác đó là cạnh của bản đồ.

Đối với đồ thị phẳng (với trường hợp riêng là bản đồ đa giác) chúng ta có công thức Euler quen thuộc liên hệ giữa số đỉnh , số cạnh và số diện

Có thể xem một ví dụ trong hình dưới

s152.photobucket.com/albums/s165/dumb_boy1988/fig010.png
Hình 10.

Từ “bản đồ” nhấn mạnh rằng công thức Euler nói chung đúng cho các phân hoạch cong (xem hình [11]), mà dạng của đường là không quan trọng mà là cách nối giữa các điểm với thỏa mãn điều kiện “đúng”, (Thí dụ, sự phân hoạch ngũ giác thành các tam giác và tứ giác như ở hình 10, ta thay thế các đoạn thẳng bằng các đoạn cong để nhận được bẳng đồ cong “đúng”).

s152.photobucket.com/albums/s165/dumb_boy1988/fig011.png
Hình 11.

Trong trường hợp các diện của bản đồ đa giác đúng đều là tam giác thì ta gọi đây là bản đồ tam giác. Hiển nhiên rằng, với một đa giác đơn trên mặt phẳng có vô hạn cách phân hoạch nó thành bản đồ tam giác. Đồng thời số các diện tam giác luôn thỏa mãn công thức (không chỉ riêng trên lưới nguyên

ở đây lần lượt là số đỉnh của bản đồ nằm trong là số đỉnh nằm trên cạnh của nó. (bạn đọc tự chứng minh công thức này)

Mặc khác, chú ý rằng là số đỉnh của bản đồ nằm trên cạnh của , nên là số cạnh hoàn toàn trong đa giác , và mỗi cạnh này là cạnh chung của hai tam giác. Tổng số cạnh của tất cả các diện tam giác của bản đồ bằng

Từ đây suy ra

Định lý 3. (Euler) Với bất kì bản đồ đa giác “đúng”, ta có đẳng thức sau

Chứng minh

s152.photobucket.com/albums/s165/dumb_boy1988/fig012.png
Hình 12.

Giả sử có bản đồ đa giác với số đỉnh , số cạnh , số diện . Chúng ta đặt trong mỗi diện của bản đồ một điểm, nối mỗi điểm đó với các đỉnh của diện chứa nó. Khi đó thu được bản đồ tam giác (xem hình [12]) với số tam giác được phân hoạch là , số đỉnh nằm trên biên của đa giác ban đầu là , số đỉnh nằm trong đa giác này là , số cạnh là . Do cách bổ sung các đỉnh nên ta có tổng số các đỉnh của

Mỗi diện của bản đồ cũ được phân hoạch thành các diện con, mà số lượng bằng số các cạnh mới được nối nằm trong diện này, do vậy số các cạnh của bản đồ mới là

Sử dụng công thức (*) ứng với bản đồ : , từ đó

Như vậy ta thu được điều phải chứng minh.

Bài tập 4. Kiểm chứng chiều đảo, có nghĩa là từ công thức suy ra đẳng thức .

Bài tập 5. Chứng minh công thức Euler một cách độc lập với công thức .

Như vậy trong bài viết chúng ta đã trình bày mỗi liên hệ logic giữa hai công thức đẹp Euler và Picard, chúng có thể được hiểu như là tương đương nhau.

s152.photobucket.com/albums/s165/dumb_boy1988/fig013.png
Hình 13.

Chúng ta có thể mở rộng hai công thức nà trong trường hợp bản đồ đúng với các “lỗ khoét”, mà mỗi lỗ khoét có dạng đa giác đơn (phần tô đậm trong hình trên)

Định lý 4. Với đa giác nguyên với “lỗ khoét” cũng là những đa giác nguyên có diện tích là

trong đó, là số đỉnh nằm bên trong đa giác và không nằm cạnh của đa giác và trên cạnh của các lỗ khoét, là số đỉnh nằm trên cạnh của đa giác và trên cạnh của các lỗ khoét.

Định lý 5. Với mỗi bản đồ đa giác với lỗ khoét thế thì

Bạn đọc hãy tự chứng minh hai định lý này xem như bài tập.

Bài tập bổ sung.

6. Xét tam giác nguyên sao cho trên cạnh của nó không chứa các điểm nguyên nào khác các đỉnh. Chứng minh rằng nếu một tam giác như vậy chứa trong nó đúng một điểm nguyên thì điểm này chính là trọng tâm của tam giác.

7. Giả sử một -giác nguyên lồi sao cho bên trong và cạnh của nó không chứa một điểm nguyên nào khác các đỉnh, chứng tỏ .

8. Chứng minh rằng với bất kì hai điểm nguyên sao cho giữa đoạn nối chúng không chứa điểm nguyên nào khác, tìm được điểm sao cho tam giác là nguyên thủy. Khoảng cách từ đến bằng bao nhiêu nếu biết độ dài .

9. Xét điểm nguyên ()sao cho bất kì ba điểm nào giữa chúng đều lập thành được tam giác mà các trung tuyến của nó không cắt một điểm nguyên nào khác. Tìm số lớn nhất có thể được.

10. Chứng mình rằng mỗi hình vuông có cạnh bằng nằm trong mặt phẳng chứa không nhiều hơn điểm nguyên.

11. Trong mỗi trường hợp trong hình [14], tính diện tích của các hình bình hành được tô đậm, trong đó cạnh của hình bình hành được chia tương ứng ra thành phần bằng nhau, và biết .

s152.photobucket.com/albums/s165/dumb_boy1988/fig015.png
Hình 14.

13. Mỗi cạnh của tam giác được chia thành ba phần bằng nhau, trên mỗi cạnh nối một điểm chia với đỉnh của tam giác đối diện với nó, như là đã chỉ ra trên hình [15]. So sánh, diện tích tam tô đậm với tam giác .

s152.photobucket.com/albums/s165/dumb_boy1988/fig016.png
Hình 15.

14. Từ trung điểm của mỗi cạnh hình vuông nối với hai đỉnh còn lại của hình vuôn đối diện với nó, như là đã chỉ ra trên hình [16], tính tỉ lệ diện tích giữa hình bát giác được tô đậm với hình vuông này.

s152.photobucket.com/albums/s165/dumb_boy1988/fig017.png
Hình 16.

15. Đặt


với là các hằng số nào đó. Giả sử hàm số này xác định trên các đa giác nguyên và thỏa mãn , nếu như được phân hoạch ra thành hai đa giác nguyên bởi một đường gấp khúc với các đỉnh nguyên. Chứng tỏ rằng .

16. Chứng minh rằng với bất kì đa giác nguyên ta luôn có đẳng thức

ở đây là kí hiệu số tất cả các điểm nằm bên trong cũng như trên các cạnh của đa giác , và là đa giác nhận từ bằng cách phóng to lên hai lần với gốc tọa độ.

17. Hãy chỉ ra trên mặt phẳng 1000 điểm sao cho không có 3 điểm nào trong chúng thẳng hàng và khoảng cách giữa hai điểm bất kì là một số vô tỉ, còn diện tích của một tam giác bất kì, mà 3 đỉnh của nó được chọn ra từ các điểm nói trên, là một số hữu tỉ.

Categories: Combinatorics
  1. January 6, 2014 at 9:19 am

    hay

  2. su-tu
    September 23, 2016 at 7:26 am

    Bài rất hay mà sao các công thức không hiện ra vậy. Mong bạn chuyển sang file pdf cho dễ xem nhé. Xin cám ơn !

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: