Category: ProofWiki

A proof of Pick’s theorem


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 M và N 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) và (x_2;y_2) lần lượt là tọa độ của A và B.

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} và \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}. Vì \{\alpha\} và \{\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 và \beta là hai số nguyên.

Gọi \overrightarrow{i} và \overrightarrow{j} lần lượt là các vector đơn vị đặt trên Ox và Oy. Khi đó theo lập luận trên, tồn tại các cặp số nguyên (u,v) và (u',v') để \overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB} và \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} và \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} và \displaystyle v'=\frac{x_1}{D}, trong đó D=x_1y_2-x_2y_1\not =0 do O,A và B không thẳng hàng. Vì u, v, u' và v' là các số nguyên nên x_1,x_2,y_1 và y_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. Để ý thêm S_P=\dfrac{1}{2}N, ta có điều phải chứng minh.

A proof of Schonemann’s criterion


Các em học sinh nên xem lại hai bài sau:

[1] https://nttuan.org/2009/01/11/poly02/

[2] https://nttuan.org/2018/08/25/poly03/

Định lý (Schonemann, 1846). Cho số nguyên tố p, số nguyên dương n, và một đa thức f(x) với hệ số nguyên có dạng f(x)=(g(x))^n+ph(x). Trong đó g và h là các đa thức với hệ số nguyên thỏa mãn:

(a) hệ số cao nhất của g bằng 1 và g bất khả quy trong \mathbb{F}_p[x].

(b) \deg (h)<\deg (f) và (g,h)=1 trong \mathbb{F}_p[x].

Khi đó f bất khả quy trong \mathbb{Q}[x].

Chứng minh. Ta thấy hệ số cao nhất của f bằng 1 và \deg (f)=n\deg (g). Giả sử f khả quy trong \mathbb{Q}[x], suy ra f=f_1f_2, với f_1 và f_2 là các đa thức khác hằng với hệ số nguyên cùng có hệ số cao nhất là 1. Khi đó trong \mathbb{F}_p[x] ta có g^n=f_1f_2, mà hệ số cao nhất của g bằng 1 và g bất khả quy trong \mathbb{F}_p[x], suy ra trong \mathbb{Z}[x] thì f_1=g^r+pF_1 và f_2=g^{n-r}+pF_2, ở đây r là số nguyên dương bé hơn n, và F_1, F_2 là hai đa thức với hệ số nguyên. Do đó trong \mathbb{Z}[x] ta có đẳng thức

h=F_1g^{n-r}+F_2g^r+pF_1F_2,

suy ra g\mid h trong \mathbb{F}_p[x], điều này không thể xảy ra do (g,h)=1 trong \mathbb{F}_p[x]. \Box

Tiêu chuẩn này là một tổng quát của tiêu chuẩn Eisenstein.

Subconvex sequences


Trong bài này tôi sẽ giới thiệu một lớp dãy hay gặp trong các đề thi chọn học sinh giỏi các cấp. Chứng minh định lí chính trong bài là của Adrian Sandovichi. Để theo dõi cho dễ, các em học sinh nên đọc lại bài sau:

https://nttuan.org/2023/09/15/limit-of-a-sequence/

Định nghĩa. Cho dãy số thực không âm (x_n)_{n\geq 1} và số nguyên k>0. Dãy số (x_n)_{n\geq 1} được gọi là một dãy lồi dưới cấp k nếu có các số thực \alpha_1, \alpha_2,\ldots, \alpha_k sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) \alpha_i\in (0;1),\quad \forall i=\overline{1,k} và \alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.

(2) x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.

Mọi dãy lồi dưới cấp 1 đều có giới hạn bằng 0. Trong định nghĩa trên, nếu dãy số (x_n) có giới hạn hữu hạn và \sum\alpha_i<1 thì \lim x_n=0.

Định lí. Cho số nguyên dương k. Khi đó mọi dãy lồi dưới cấp k đều có giới hạn hữu hạn.

Chứng minh. Gọi (x_n) là một dãy lồi dưới cấp k. Khi đó tồn tại các số thực \alpha_1, \alpha_2,\ldots, \alpha_k sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) \alpha_i\in (0;1),\quad \forall i=\overline{1,k} và \alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.

(2) x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.

Xét dãy số (y_n)_{n\geq 1} xác định bởi \displaystyle y_n=\max_{0\leq i\leq k-1}x_{n+i} với mọi số nguyên n>0. Ta thấy (y_n)_{n\geq 1} là một dãy số không tăng và bị chặn dưới bởi 0 nên nó có giới hạn hữu hạn không âm, đặt L=\lim y_n. Ta sẽ chứng minh (x_n) có giới hạn hữu hạn và L=\lim x_n.

Với mọi số thực dương \epsilon, cố định nó.

Đặt \displaystyle t=\min\left\{1;\frac{\alpha_1^k}{2^k(1-\alpha_1)}\right\}. Vì t>0 và L là giới hạn của dãy số không tăng (y_n) nên tồn tại số nguyên dương n_{\epsilon} để

x_n\leq y_n<L+t\epsilon\leq L+\epsilon,\quad \forall n\geq n_{\epsilon}.\quad (*)

Bây giờ ta chứng minh x_m>L-\epsilon,\quad \forall m\geq k+n_{\epsilon}.\quad (**)

Giả sử tồn tại số nguyên dương m\geq k+n_{\epsilon} sao cho x_m\leq L-\epsilon.

Mệnh đề. \displaystyle x_{m+p}\leq L-\epsilon\left(\frac{\alpha_1}{2}\right)^p,\quad \forall p=\overline{1,k-1}.

Chứng minh. Ta chứng minh bằng quy nạp theo p. Với p=1, từ (*) và cách chọn t ta có

x_{m+1} \leq \alpha_1x_m+\alpha_2x_{m-1}+\cdots+\alpha_kx_{m-k+1}

\leq\alpha_1x_m+(\alpha_2+\cdots+\alpha_k)(L+t\epsilon)

\leq\alpha_1(L-\epsilon)+(1-\alpha_1)(L+t\epsilon)

\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^k\epsilon

\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^1\epsilon

=L-\epsilon\left(\frac{\alpha_1}{2}\right).

Suy ra khẳng định đúng với p=1. Giả sử khẳng định đúng đến p<k-1, ta chứng minh nó đúng với p+1. Theo giả thiết quy nạp, (*) và cách chọn t ta có

x_{m+p+1} \leq \alpha_1x_{m+p}+\alpha_2x_{m+p-1}+\cdots+\alpha_kx_{m+p-k+1}

\leq\alpha_1\left(L-\epsilon\left(\frac{\alpha_1}{2}\right)^p\right)+(1-\alpha_1)(L+t\epsilon)

=L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p+(1-\alpha_1)t\epsilon

\leq L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p+\left(\frac{\alpha_1}{2}\right)^k\epsilon

\leq L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p +\left(\frac{\alpha_1}{2}\right)^{p+1}\epsilon

=L-\epsilon\left(\frac{\alpha_1}{2}\right)^{p+1}.

Suy ra khẳng định đúng với p+1. Theo nguyên lý quy nạp toán học, mệnh đề là đúng. \Box

Continue reading “Subconvex sequences” →

A proof of Cauchy–Davenport theorem


Trong bài này tôi sẽ giới thiệu một chứng minh của định lí Cauchy-Davenport.

Định lí Cauchy – Davenport. Cho số nguyên tố p và hai tập con khác rỗng A,B của \mathbb{Z}/p\mathbb{Z}. Khi đó

|A+B|\geq\min (p,|A|+|B|-1).

Chứng minh. Ta chứng minh khẳng định bằng quy nạp theo |B|. Khi |B|=1 ta có

|A+B|=|A|=\min (p,|A|)=\min (p,|A|+|B|-1). Suy ra khẳng định đúng khi |B|=1. Khi |B|=2 ta viết B=\{b_1,b_2\} và A=\{a_1,a_2,\ldots,a_m\}, ta có ngay |A+B|\geq m.

Nếu |A+B|= m thì \{b_1+a_1,\ldots,b_1+a_m\}=\{b_2+a_1,\ldots,b_2+a_m\}, suy ra mb_1\equiv mb_2\pmod{p}, hay m=p. Khi đó |A+B|=p\geq\min (p,|A|+|B|-1).

Nếu |A+B|>m thì |A+B|\geq m+1\geq\min (p,m+1)=\min (p,|A|+|B|-1).

Vậy khẳng định đúng khi |B|=2. Giả sử khẳng định đúng với mỗi tập B thỏa mãn |B|<n, trong đó n\geq 3. Ta sẽ chứng minh khẳng định đúng với mọi tập B có |B|=n. Xét một tập B thỏa mãn |B|=n. Đặt |A+B|=l,|A|=m và viết B=\{b_1,b_2,\ldots,b_n\}. Xét ba trường hợp

Trường hợp 1. l\geq p.

Ta có |A+B|=l\geq p\geq\min (p,|A|+|B|-1).

Trường hợp 2. m+n>p.

Ta có A+B=\{0,1,2,\ldots,p-1\}, thật vậy với mỗi g\in \{0,1,2,\ldots,p-1\}, hai tập g-A và B có giao khác rỗng vì chúng là các tập con của tập \{0,1,2,\ldots,p-1\} và có tổng số phần tử lớn hơn p. Lấy h\in g-A\cap B ta có ngay g=b=g-a\,\, (a\in A,b\in B), suy ra g=a+b\in A+B. Từ đây ta có |A+B|=p\geq\min (p,|A|+|B|-1).

Trường hợp 3. l<p và m+n\leq p.

Ở trường hợp này thì \min (p,|A|+|B|-1)=\min (p,m+n-1)=m+n-1. Áp dụng giả thiết quy nạp cho hai tập C=A+B và \{b_1,b_n\} ta có |C+\{b_1,b_n\}|\geq\min (p,|C|+|\{b_1,b_n\}|-1)=\min (p,l+1)=l+1, suy ra C+b_1\not = C+b_n, do đó tồn tại số nguyên x sao cho x-b_1\in A+B và x-b_n\not\in A+B. Từ đây ta thấy tồn tại số nguyên dương r<n sao cho x-b_i\in A+B,\,\forall i=\overline{1,r} và x-b_i\not\in A+B,\,\forall i=\overline{r+1,n}. Áp dụng giả thiết quy nạp cho hai tập A và B^{\prime}=\{b_{r+1},b_{r+2},\ldots,b_n\} ta có

|A+B^{\prime}|\geq \min (p,|A|+|B^{\prime}|-1)=\min (p,m+n-r-1)=m+n-r-1. Ta có x-b_i\not\in A+B^{\prime},\,\forall i=\overline{1,r}, vì nếu chẳng hạn x-b_1\in A+B^{\prime} thì

x-b_1= a+b_{s}\Rightarrow x-b_s\in A+B, điều này trái với cách chọn r. Vậy |A+B|\geq r+|A+B^{\prime}|\geq r+m+n-r-1=m+n-1, và định lí được chứng minh. \Box

Bằng quy nạp ta chứng minh được kết quả sau.

Hệ quả. Cho số nguyên dương h>1, số nguyên tố p và h tập con khác rỗng A_1, A_2,\ldots, A_h của \mathbb{Z}/p\mathbb{Z}. Khi đó \displaystyle \mid A_1+A_2+\cdots+A_h\mid \geq \min \left(p,\sum_{i=1}^h\mid A_i\mid-h+1\right).