Một chứng minh của định lí Pick


Hình tạo bởi một đường gấp khúc đóng và không tự cắt được gọi là đa giác đơn. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ có các đỉnh là các điểm nguyên đồng thời trên biên và phần trong của nó không còn điểm nguyên nào khác. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.

Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.

Định lí 1. Trong mặt phẳng tọa độ Oxy, cho tam giác ABC. Khi đó diện tích của tam giác ABC bằng \displaystyle \frac{1}{2}\left|(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\right|. Nói riêng, với mỗi hai điểm MN ta có diện tích của tam giác OMN bằng \dfrac{1}{2}\mid x_My_N-y_Mx_N\mid.

Định lí 2. Mọi tam giác cơ bản đều có diện tích bằng \dfrac{1}{2}.

Chứng minh. Giả sử TAB là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem T trùng với gốc tọa độ O. Ta cần chứng minh \mid x_1y_2-x_2y_1\mid =1, với (x_1;y_1)(x_2;y_2) lần lượt là tọa độ của AB.

Gọi K là điểm sao cho OAKB là hình bình hành. Giả sử M là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho M khác các đỉnh. Khi đó M thuộc tam giác ABK và điểm N đối xứng với M qua tâm hình bình hành là điểm nguyên thuộc tam giác OAB nhưng khác các đỉnh, không thể xảy ra điều này do OAB là một tam giác cơ bản. Như vậy hình bình hành OAKB không chứa điểm nguyên nào khác bốn đỉnh của nó.

Giả sử P là một điểm nguyên bất kỳ. Vì \overrightarrow{OA}\overrightarrow{OB} là hai vector không cùng phương nên tồn tại cặp số thực (\alpha,\beta) để \overrightarrow{OP}=\alpha \overrightarrow{OA}+\beta \overrightarrow{OB}. Gọi P' là điểm xác định bởi \overrightarrow{OP'}=\{\alpha\} \overrightarrow{OA}+\{\beta\} \overrightarrow{OB}.\{\alpha\}\{\beta\} thuộc [0;1) nên P' thuộc hình bình hành OAKB, nhưng P' lại là một điểm nguyên, suy ra P' phải là một trong bốn đỉnh của hình bình hành. Dễ thấy P'\equiv O và do đó \alpha\beta là hai số nguyên.

Gọi \overrightarrow{i}\overrightarrow{j} lần lượt là các vector đơn vị đặt trên OxOy. Khi đó theo lập luận trên, tồn tại các cặp số nguyên (u,v)(u',v') để \overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB}\overrightarrow{j}=u' \overrightarrow{OA}+v' \overrightarrow{OB}. Từ hai đẳng thức này ta có \begin{cases} 1=ux_1+vx_2\\ 0=uy_1+vy_2\end{cases}\begin{cases}0=u'x_1+v'x_2\\ 1=u'y_1+v'y_2,\end{cases} suy ra \displaystyle u=\frac{y_2}{D},v=-\frac{y_1}{D},u'=-\frac{x_2}{D}\displaystyle v'=\frac{x_1}{D}, trong đó D=x_1y_2-x_2y_1\not =0 do O,AB không thẳng hàng. Vì u, v, u'v' là các số nguyên nên x_1,x_2,y_1y_2 đều là bội của D, do đó D^2\mid D và bởi thế, D=\pm 1.

Định lí Pick. Cho P là một đa giác đơn có các đỉnh là các điểm nguyên, I là số điểm nguyên nằm trong và B là số điểm nguyên nằm trên biên của P. Khi đó ta có đẳng thức \displaystyle S_P=I+\frac{1}{2}B-1.

Chứng minh. Chia P thành N tam giác cơ bản. Gọi S là tổng các góc trong của tất cả các tam giác cơ bản đó. Ta sẽ tính S theo hai cách. Vì số tam giác là N nên S=N\pi.

Tổng tất cả các góc có đỉnh là một điểm nguyên nằm trong P bằng 2\pi, tổng tất cả các góc có đỉnh là một điểm nguyên nằm trên biên của P nhưng không phải đỉnh của P bằng \pi và tổng của tất cả các góc có đỉnh là đỉnh của P bằng (n-2)\pi, ở đây n là số đỉnh của P. Do đó S=2\pi I+\pi B-2\pi.

Suy ra N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2, mà S_P=\dfrac{1}{2}N, suy ra điều phải chứng minh.

Công thức Popoviciu


Trong  bài này chúng tôi sẽ giới thiệu một công thức tính số nghiệm tự nhiên của phương trình ax+by=n, ở đây a,b là các số nguyên dương thỏa mãn (a,b)=1n là số tự nhiên.

Định lí. (Công thức Popoviciu)  Gọi N(a,b;n) là số các cặp số tự nhiên (x,y) sao cho ax+by=n, ở đây a,b là các số nguyên dương thỏa mãn (a,b)=1n là số tự nhiên. Khi đó

\displaystyle N(a,b;n)=\frac{n}{ab}-\left\{\frac{a^{-1}n}{b}\right\}-\left\{\frac{b^{-1}n}{a}\right\}+1, với a^{-1} là nghịch đảo modulo b của ab^{-1} là nghịch đảo modulo a của b.

Chứng minh. Gọi \displaystyle F(z)=\sum_{n=0}^{+\infty}N(a,b;n)z^n là hàm sinh của dãy số \{N(a,b;n)\}_{n\geq 0}. Ta có

\displaystyle F(z)=\sum_{k\in\mathbb{N}}\sum_{l\in\mathbb{N}}z^{ak}z^{bl}=\frac{1}{(1-z^a)(1-z^b)}.\quad (1)

(a,b)=1 nên đa thức (1-z^a)(1-z^b) có nghiệm là 1 với bội 2 và các nghiệm đơn \xi_a^k (k=1,2,\ldots,a-1), \xi_b^l (l=1,2,\ldots,b-1), ở đây \xi_a=\cos\dfrac{2\pi}{a}+i\sin \dfrac{2\pi}{a}\xi_b=\cos\dfrac{2\pi}{b}+i\sin \dfrac{2\pi}{b}. Kết hợp với (1) ta có tồn tại các số phức C_1,C_2; A_i; B_i sao cho

\displaystyle F(z)=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (2)

Để ý đến hệ số của z^n, từ (2) ta có

\displaystyle N(a,b;n)=C_1+C_2(n+1)+\sum_{k=1}^{a-1}A_k\xi_a^{-nk}+\sum_{l=1}^{b-1}B_l\xi_b^{-nl}.\quad (3)

Bây giờ ta sẽ đi tìm các số phức C_1,C_2; A_i; B_i từ đẳng thức

\displaystyle \frac{1}{(1-z^a)(1-z^b)}=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (4)

Nhân hai vế của (4) với (1-z)^2 và cho z\to 1 ta có C_2=\dfrac{1}{ab}, sau đó nhân hai vế của (4) với 1-z, để C_1 một bên và cho z\to 1 ta được C_1=\dfrac{a+b-2}{2ab}. Theo cùng một cách ta có

\displaystyle A_k=\frac{1}{a(1-\xi_a^{kb})},\quad B_l=\frac{1}{b(1-\xi_b^{la})}.

Thay vào (3) ta được

\displaystyle N(a,b;n)=\frac{n}{ab}+\frac{a+b}{2ab}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}+\frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}.\quad (5)

Từ (5) ta có \displaystyle N(a,1;n)=\frac{n}{a}+\frac{a+1}{2a}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}, mà \displaystyle N(a,1;n)=\left[\frac{n}{a}\right]+1, suy ra

\displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{n}{a}\right\}-\frac{1}{2a},

do đó \displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}=\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nb^{-1}k}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{nb^{-1}}{a}\right\}-\frac{1}{2a},

chứng minh tương tự ta được

\displaystyle \frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}=\frac{1}{2}-\left\{\frac{na^{-1}}{b}\right\}-\frac{1}{2b},

thay hai đẳng thức cuối cùng vào (5) ta có điều cần chứng minh. \Box