Category: Mathematical Olympiad

Farey sequence

Trong mục này tôi sẽ trình bày về phân số Farey và một số vấn đề liên quan.

Các phân số trong bài được xem là có mẫu dương.

1) Định nghĩa và một số tính chất

Định nghĩa 1. Cho số nguyên dương $\displaystyle n$ . Phân số tối giản $\displaystyle \dfrac{p}{q}\in [0;1]$ được gọi là phân số Farey bậc $\displaystyle n$ nếu $\displaystyle q\leq n$ . Dãy tăng tất cả các phân số Farey bậc $\displaystyle n$ được gọi là dãy Farey bậc $\displaystyle n$ , ký hiệu là $\displaystyle F_n$ .

Ví dụ 1.

$\displaystyle F_1:\,\frac{0}{1};\frac{1}{1}$ .

$\displaystyle F_2:\,\frac{0}{1};\frac{1}{2};\frac{1}{1}$ .

$\displaystyle F_3:\,\frac{0}{1};\frac{1}{3};\frac{1}{2};\frac{2}{3};\frac{1}{1}.$

$\displaystyle F_4:\,\frac{0}{1};\frac{1}{4};\frac{1}{3};\frac{1}{2};\frac{2}{3};\frac{3}{4};\frac{1}{1}.$

Ví dụ 2. Với mỗi số nguyên dương $\displaystyle n$ , dãy $\displaystyle F_n$ có đúng $\displaystyle 1+\sum_{k=1}^n\varphi (k)$ số hạng.

Định lý 1. Cho các số tự nhiên $\displaystyle a,b,c$ và $\displaystyle d$ thỏa mãn $\displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1$ và $\displaystyle bc-ad=1$ . Khi đó $\displaystyle \frac{a}{b},\frac{c}{d}$ là hai số hạng liên tiếp của dãy $\displaystyle F_n$ , ở đây $\displaystyle n$ là số nguyên dương thỏa mãn $\displaystyle \max\{b,d\}\leq n\leq b+d-1.$

Chứng minh. Từ $\displaystyle bc-ad=1$ ta có $\displaystyle \frac{a}{b},\frac{c}{d}$ là hai phân số tối giản, mà $\displaystyle \max\{b,d\}\leq n$ , suy ra chúng là các số hạng của dãy $\displaystyle F_n$ . Nếu chúng không phải là hai số hạng liên tiếp của $\displaystyle F_n$ thì tồn tại phân số Farey bậc $\displaystyle n$ , ký hiệu $\displaystyle \dfrac{h}{k}$ thỏa mãn $\displaystyle \displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d}.$ Vì $\displaystyle ck-dh\geq 1$ và $\displaystyle bh-ak\geq 1$ nên

$\displaystyle b+d-1\geq n\geq k=(bc-ad)k=b(ck-dh)+d(bh-ak)\geq b+d,$ đây là điều không thể xảy ra. Định lý được chứng minh. $\Box$

Với các số tự nhiên $\displaystyle a,b,c$ và $\displaystyle d$ thỏa mãn $\displaystyle 0\leq \frac{a}{b}<\frac{c}{d},$ phân số $\dfrac{a+c}{b+d}$ được gọi là phân số trung gian của hai phân số $\displaystyle \dfrac{a}{b}$ và $\displaystyle \dfrac{c}{d}$ . Từ chứng minh trên ta có:

Định lý 2. Cho các số tự nhiên $\displaystyle a,b,c$ và $\displaystyle d$ thỏa mãn $\displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1$ và $\displaystyle bc-ad=1$ . Khi đó nếu $\displaystyle \dfrac{h}{k}$ là phân số trung gian của hai phân số $\displaystyle \dfrac{a}{b}$ , $\dfrac{c}{d}$ thì $\displaystyle \frac{a}{b}<\frac{h}{k}<\frac{c}{d}$ và $\displaystyle bh-ak=1,\quad ck-dh=1.$

Định lý 3. Với mọi số nguyên dương $\displaystyle n$ ta có

1) Dãy $\displaystyle F_{n+1}$ có được từ dãy $\displaystyle F_n$ bằng cách viết vào giữa hai số hạng liên tiếp của $\displaystyle F_n$ có tổng các mẫu không vượt quá $\displaystyle n+1$ phân số trung gian của chúng;

2) Nếu $\displaystyle \dfrac{a}{b}<\dfrac{c}{d}$ là hai số hạng liên tiếp của $\displaystyle F_n$ thì $\displaystyle bc-ad=1$ .

Chứng minh. Ta sẽ chứng minh bằng quy nạp theo $\displaystyle n$ .

Rõ ràng khẳng định đúng với $n=1$. Giả sử khẳng định đúng với các số nguyên dương bé hơn $\displaystyle n\, (n\geq 2)$ , ta sẽ chứng minh khẳng định đúng với $\displaystyle n$ .

Từ định lý 2 và giả thiết quy nạp ta có nếu $\displaystyle \dfrac{a}{b}<\dfrac{c}{d}$ là hai số hạng liên tiếp của $\displaystyle F_n$ thì $\displaystyle bc-ad=1$ .

Sau khi viết vào giữa hai số hạng liên tiếp của $\displaystyle F_n$ có tổng các mẫu không vượt quá $\displaystyle n+1$ phân số trung gian của chúng ta thu được dãy con $\displaystyle F'_n$ của $\displaystyle F_{n+1}$ . Nếu trong $\displaystyle F_{n+1}$ có phân số $\displaystyle \dfrac{h}{k}$ không thuộc $\displaystyle F'_n$ thì tồn tại hai số hạng liên tiếp $\displaystyle \dfrac{a}{b}<\dfrac{c}{d}$ của $\displaystyle F'_n$ sao cho $\displaystyle \dfrac{a}{b}<\dfrac{h}{k}<\dfrac{c}{d}$ . Vì $\displaystyle \dfrac{h}{k}$ không thuộc $\displaystyle F'_n$ nên nó cũng không thuộc $\displaystyle F_n$ , suy ra $\displaystyle k>n$ , kết hợp với $\displaystyle k\leq n+1$ ta có $\displaystyle k=n+1$ .

Từ chứng minh của định lý 1 suy ra $\displaystyle k=n+1\geq b+d\Rightarrow$ $\displaystyle \dfrac{a}{b}<\dfrac{c}{d}$ là hai phân số liên tiếp của $\displaystyle F_n$ , mà $\displaystyle b+d\leq n+1$ , suy ra chúng không thể là hai số hạng liên tiếp của $\displaystyle F'_n$ , vô lý. $\displaystyle \Box$

Chú ý 1. Dùng định lý Pick (bạn đọc có thể xem thêm về định lý Pick ở địa chỉ https://nttuan.org/2017/03/18/topic-872/) ta có một chứng minh khác của 2).

Trong mặt phẳng tọa độ $\displaystyle Oxy$ , xét các điểm $\displaystyle M(1;0)$ và $\displaystyle N(1;1)$ . Mỗi số hạng $\displaystyle \dfrac{h}{k}$ của $\displaystyle F_n$ ta cho tương ứng với điểm nguyên có tọa độ $\displaystyle (k;h)$ . Khi quay tia $\displaystyle OM$ ngược chiều kim đồng hồ đến tia $\displaystyle ON$ ta “gặp” mỗi điểm nguyên không quá một lần và không gặp đồng thời hai điểm nguyên (ta quan tâm đến các điểm nguyên tương ứng với các số hạng của $\displaystyle F_n$ ). Xét hai số hạng liên tiếp $\displaystyle \dfrac{a}{b}<\dfrac{c}{d}$ của $\displaystyle F_n$ và hai điểm $\displaystyle X(b;a),Y(d;c)$ lần lượt tương ứng với chúng. Theo trên ta thấy tam giác $\displaystyle OXY$ không chứa điểm nguyên nào bên trong cũng như trên biên trừ ba đỉnh của nó, suy ra $\displaystyle S_{OXY}=\dfrac{1}{2}\Rightarrow bc-ad=1$ . $\displaystyle \Box$

Tags Pell, Phân số Farey, Pick's theorem, Xấp xỉ Diophantine, Đường tròn Ford

College Math Combinatorics Geometry Mathematical Olympiad Number theory

Định lí Pick

Trong bài này tôi sẽ giới thiệu một số chứng minh của định lí Pick và áp dụng định lí Pick vào việc tính số Frobenius của một tập có hai phần tử. Phần cuối của bài là một số bài thi chọn học sinh giỏi liên quan.

1. Định lí và các chứng minh

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. Trong mặt phẳng tọa độ, điểm $A(x_0,y_0)$ được gọi là điểm nguyên nếu $x_0$ và $y_0$ là các số nguyên. Với mỗi đa giác đơn $P$ , kí hiệu $S_P$ là diện tích của nó. Định lí Pick cho một mối liên hệ giữa diện tích và diện tích rời rạc (số điểm nguyên nằm trong đa giác) của một đa giác đơn.

Đị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 thứ nhất. Dùng một đường gấp khúc $l$ nối hai đỉnh không kề nhau của $P$ để cắt $P$ thành hai đa giác đơn $\Delta$ và $P'$ . Ta thấy nếu công thức Pick đúng với $\Delta$ và $P'$ thì nó cũng đúng với $P$ . Thật vậy, ta có

$\displaystyle I=I_{\Delta}+I_{P'}+x-2,\quad B=B_{\Delta}+B_{P'}-2x+2,$

ở đây $x$ là số điểm nguyên trên $l$ , suy ra

$\displaystyle S_P=S_{\Delta}+S_{P'}=I_{\Delta}+\frac{1}{2}B_{\Delta}-1+I_{P'}+\frac{1}{2}B_{P'}-1=I+\frac{1}{2}B-1.$

Vậy công thức Pick đúng với $P$ . Hơn nữa, nếu công thức Pick đúng với hai trong ba đa giác $\Delta$ , $P$ , $P'$ thì nó cũng đúng với đa giác còn lại. Do đó ta chỉ cần chứng minh định lí Pick cho các tam giác là xong.

Vì từ một tam giác bất kì ta luôn có thể ghép thêm vào các tam giác vuông có các cạnh góc vuông cùng phương với các trục tọa độ để tạo thành một hình chữ nhật có các cạnh cùng phương với các trục tọa độ nên ta chỉ cần chứng minh định lí cho các tam giác vuông có các cạnh góc vuông cùng phương với các trục tọa độ và các hình chữ nhật có các cạnh cùng phương với các trục tọa độ. Điều này là đơn giản. $\Box$

Một tam giác cơ bản là một tam giác 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. Ta có kết quả sau:

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

Chứng minh. Xét một tam giác cơ bản bất kì. Lấy một hình chữ nhật có các cạnh cùng phương với các trục tọa độ sao cho nó chứa tam giác và mỗi cạnh chứa ít nhất một đỉnh của tam giác. Vì hình chữ nhật có $4$ cạnh và tam giác có $3$ đỉnh nên có ít nhất một đỉnh của tam giác là đỉnh của hình chữ nhật, mà tam giác là cơ bản nên chỉ xảy ra tình huống ở hình H3 (bỏ qua các trường hợp tầm thường), tình huống mà một cạnh của tam giác là đường chéo của hình chữ nhật (trường hợp H1 có điểm nguyên $L$ , H2 có điểm nguyên $K$ ).

pick1

Trong hình H3, tam giác cơ bản đang xét là $OAB$ . Không mất tính tổng quát ta giả sử $M=(0;m),$ $P=(p;0),$ $B=(b_1;b_2),$ ở đây $m,p,b_1,b_2$ là các số nguyên dương thỏa mãn $p> b_1$ , và $m> b_2$ .

Số điểm nguyên nằm trong hình chữ nhật $OMAP$ bằng $(m-1)(p-1)$ , mà không có điểm nguyên nào trong số các điểm này nằm trên $OA$ , suy ra số điểm nguyên nằm trong tam giác $OAP$ bằng $\dfrac{(m-1)(p-1)}{2}.$ Tính toán tương tự ta có số điểm nguyên nằm trong tam giác $OBR$ bằng $\dfrac{(b_1-1)(b_2-1)}{2}$ , nằm trong tam giác $BAS$ bằng $\dfrac{(p-b_1-1)(m-b_2-1)}{2}$ .

Nhưng số điểm nguyên nằm trong tam giác $OAP$ bằng $1$ (điểm $B$ ) $+$ $0$ (số điểm nguyên trong tam giác $OAB$ ) $+$ số điểm nguyên nằm trong tam giác $OBR$ $+$ số điểm nguyên nằm trong tam giác $BAS$ $+$ số điểm nguyên nằm trong hình chữ nhật $BSPR$ $+$ số điểm nguyên nằm trên đoạn thẳng $BS$ khác $B$ và $S$ $+$ số điểm nguyên nằm trên đoạn thẳng $BR$ khác $B$ và $R$ , suy ra

$\displaystyle \frac{(m-1)(p-1))}{2}=1+\frac{(b_1-1)(b_2-1)}{2}+\frac{(p-b_1-1)(m-b_2-1)}{2}$

$+(b_2-1)(p-b_1-1)+p-b_1-1+b_2-1,$ do đó $mb_1-b_2p=1$ , bằng cộng trừ diện tích ta có $S_{OAB}=\dfrac{1}{2}$ . $\Box$

Chú ý. Trong chứng minh trên ta có thể tính diện tích tam giác $OAB$ bằng cách dùng công thức sau:

Công thức dây giày. Cho đa giác đơn $A_0A_1\ldots A_{n-1}$ . Khi đó nếu $A_i$ có tọa độ $(x_i;y_i)$ thì diện tích của đa giác $A_0A_1\ldots A_{n-1}$ bằng $\displaystyle\frac{1}{2}\left|\sum_{i=0}^{n-1}\begin{vmatrix} x_i & x_{i+1} \\ y_i & y_{i+1} \end{vmatrix}\right|,$

ở đây $x_n=x_0$ và $y_n=y_0$ .

Bây giờ chúng tôi sẽ tiếp tục giới thiệu các chứng minh khác của định lí Pick.

Chứng minh thứ hai. 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\quad (1).$

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\quad (2)$ .

Từ $(1)$ và $(2)$ ta có $N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2$ , mà $S=\dfrac{1}{2}N$ , suy ra định lí được chứng minh. $\Box$

Một graph được gọi là graph phẳng nếu nó có thể nhúng vào một mặt phẳng, nghĩa là ta có thể vẽ nó trên một mặt phẳng sao cho hai cạnh bất kì không có điểm trong chung. Trong chứng minh tiếp theo ta sẽ dùng kết quả sau:

Công thức Euler. Cho $G$ là một graph phẳng, hữu hạn và liên thông. Giả sử sau khi vẽ $G$ trên một mặt phẳng sao cho hai cạnh bất kì không có điểm trong chung, số đỉnh của $G$ bằng $v$ , số cạnh bằng $e$ và số mặt (miền giới hạn bởi các cạnh, kể cả miền vô hạn bên ngoài) bằng $f$ . Khi đó ta có đẳng thức $v-e+f=2$ .

Chứng minh thứ ba. Đầu tiên, như chứng minh trên ta chia đa giác $P$ thành các tam giác cơ bản. Xét graph $G$ có đỉnh là các điểm nguyên nằm bên trong hay trên biên của $P$ , các cạnh là cạnh của các tam giác cơ bản trong phép chia đang xét. Dễ thấy $G$ là một graph phẳng, hữu hạn và liên thông.

Gọi $f$ là số mặt, $e_i$ là số cạnh trong (cạnh chung của hai tam giác cơ bản), $e_b$ là số cạnh biên (cạnh nằm trên cạnh của $P$ ) của $G$ .

Vì diện tích của tam giác cơ bản bằng $\dfrac{1}{2}$ nên $S_P=\dfrac{1}{2}(f-1)\quad (1)$ .

Do mỗi cạnh trong là cạnh chung của đúng hai tam giác cơ bản và mỗi cạnh biên là cạnh của đúng một tam giác cơ bản nên $3(f-1)=2e_i+e_b\quad (2).$

Số đỉnh của $G$ bằng $I+B$ , số cạnh bằng $e_i+e_b$ và số mặt bằng $f$ nên theo công thức Euler ta có $I+B-(e_i+e_b)+f=2\quad (3).$

Từ $(1), (2)$ và $(3)$ với chú ý $B=e_b$ ta có $S_P=I+\dfrac{1}{2}B-1.\Box$

Chứng minh sau tương tự chứng minh thứ hai.

Chứng minh thứ tư. Với mỗi điểm nguyên $M$ nằm trên biên hay trong $P$ , gọi $\alpha_M$ là góc mà từ $M$ nhìn thấy được $P$ . Như vậy $\alpha_M=2\pi$ khi $M$ nằm trong $P$ và $\alpha_M=\pi$ khi $M$ nằm trên biên của $P$ nhưng khác đỉnh. Với mỗi điểm nguyên $M$ nằm trên biên hay trong $P$ , đặt $t_{M}=\dfrac{\alpha_M}{2\pi}$ .

Xét tổng $\displaystyle T_P=\sum_{M}t_M$ . Ta cần bổ đề sau:

Bổ đề 2. $T_P=S_P$ .

Chứng minh. Ta thấy cả $T$ và $S$ đều cộng tính, nghĩa là khi chia $P$ thành hai đa giác đơn $P_1,P_2$ bởi một đường chéo thì

$T_{P}=T_{P_1}+T_{P_2},\quad S_{P}=S_{P_1}+S_{P_2}.$

Bởi thế nên như chứng minh thứ nhất, ta chỉ cần chứng minh đẳng thức cho hình chữ nhật có các cạnh cùng phương với trục và các tam giác vuông có các cạnh góc vuông cùng phương với trục. Việc này là đơn giản.

Trở lại việc chứng minh định lí.

Vì tổng của các $\alpha_M$ với $M$ nằm trên biên của $P$ bằng $(B-2)\pi$ nên theo bổ đề ta có $S_P=T_P=$ (tổng của các $t_M$ với $M$ nằm trong $P$ ) $+$ (tổng của các $t_M$ với $M$ nằm trên biên của $P$ ) $=$ $\displaystyle I+\frac{(B-2)\pi}{2\pi}=I=\frac{1}{2}B-1.$ $\Box$

2. Áp dụng vào bài toán Frobenius

Giả sử ở ngân hàng chỉ còn hai loại tiền $3$ đồng và $5$ đồng. Tôi có một tờ $n\, (n\in\mathbb{N}^*)$ đồng. Liệu tôi có thể đem tờ $n$ đồng đó đến ngân hàng để đổi lấy các tờ $3$ hay $5$ đồng được không? Rõ ràng không phải lúc nào cũng đổi được (chẳng hạn $n=4$ ) và với $n$ đủ lớn ta luôn đổi được. Một câu hỏi tự nhiên là: $n$ lớn nhất bằng bao nhiêu để không đổi được? (Câu hỏi này lần đầu tiên được đặt ra bởi Frobenius).

Một cách toán học, ta có bài toán sau:

Bài toán Frobenius. Cho tập $A=\{a_1,a_2,\ldots,a_d\}$ gồm $d>1$ số nguyên dương lớn hơn $1$ sao cho $\gcd (a_1,a_2,\ldots,a_d)=1$ . Một số tự nhiên $n$ được gọi là biểu diễn được theo tập $A$ nếu tồn tại các số tự nhiên $m_1,m_2,\ldots,m_d$ sao cho $\displaystyle n=\sum_{i=1}^d m_ia_i$ . Tìm số tự nhiên lớn nhất không biểu diễn được theo tập $A$ .

Kết quả của bài toán này được gọi là số Frobenius của $A$ và được ký hiệu bởi $g(a_1,a_2,\ldots,a_d)$ . Định lí sau chứng tỏ các số này tồn tại.

Định lí 1. Tồn tại số nguyên $N$ sao cho mọi số nguyên $s\geq N$ đều biểu diễn được theo $A$ .

Chứng minh. Ta sẽ chứng minh bằng quy nạp theo $d$ .

Do định lí 1 nên khẳng định đúng với $d=2$ .

Giả sử khẳng định đúng với $d=k-1\,(k>2,k\in\mathbb{Z})$ . Ta đi chứng minh khẳng định đúng với $d=k$ .

Đặt $x=\gcd (a_1,a_2,\ldots,a_{k-1})$ và $a'_i=a_i/x$ . Vì $\gcd (a'_1,a'_2,\ldots,a'_{k-1})=1$ nên theo giả thiết quy nạp, tồn tại số nguyên $\alpha$ sao cho mọi số nguyên $y\geq\alpha$ đều biểu diễn được theo $A'=\{a'_i\}$ .

Chọn $N=\alpha x+(x-1)a_k$ và cố định một số nguyên $s\geq N$ .

Do $\gcd (a_1,a_2,\ldots,a_k)=1$ nên $\gcd (x,a_k)=1$ , suy ra tồn tại số tự nhiên $x_k<x$ sao cho $s\equiv a_kx_k\pmod{x}$ . Ta thấy $\dfrac{s-a_kx_k}{x}$ là số nguyên không bé hơn $\displaystyle \frac{\alpha x+(x-1)a_k-a_kx_k}{x}=\alpha+\frac{a_k(x-1-x_k)}{x}\geq\alpha$ suy ra tồn tại các số tự nhiên $x_1,x_2,\ldots,x_{k-1}$ để $\displaystyle \frac{s-a_kx_k}{x}=a'_1x_1+a'_2x_2+\cdots+a'_{k-1}x_{k-1},$ do đó $s=a_1x_1+a_2x_2+\cdots+a_kx_k$ . Vậy khẳng định đúng với $d=k$ và bởi thế nó đúng với mọi số nguyên $d>1$ . $\Box$

Không có công thức tính các số Frobenius với $d>2$ trong trường hợp tổng quát. Khi $d=2$ ta có.

Định lí 2. Nếu $p,q>1$ là hai số nguyên dương nguyên tố cùng nhau thì

$g(p,q)=pq-p-q.$

Chứng minh.

Trong hình trên, tứ giác $ABCD$ không chứa điểm nguyên nào trên biên ngoài $A,B,C,D$ . Bởi công thức dây giầy ta có $S_{ABCD}=p+q$ , áp dụng định lí Pick ta thấy số điểm nguyên nằm trong $ABCD$ là $p+q-1$ , dễ thấy các điểm này đều nằm trong góc phần tư thứ nhất.

Mỗi một trong $p+q-1$ đường thẳng $px+qy=pq=p-q+i,\quad i=1,2,\cdots,p+q-1$ chứa nhiều nhất một điểm nguyên nằm trong $ABCD$ , kết hợp với phần trên, mỗi đường thẳng này đều chứa đúng một điểm nguyên nằm trong $ABCD$ .

Mà dễ thấy mỗi đường thẳng $px+qy=m,\quad m=pq+1,pq+2,\cdots$ đều chứa ít nhất một điểm nguyên nằm trong góc phần tư thứ nhất, suy ra điều phải chứng minh. $\Box$

Các bạn có thể tìm hiểu thêm về bài toán Frobenius tại địa chỉ

https://nttuan.org/2017/02/18/topic-863/

3. Ví dụ

Ví dụ 1. Cho tam giác $ABC$ trong mặt phẳng tọa độ sao cho các đỉnh của nó là các điểm nguyên. Giả sử tồn tại đúng một điểm nguyên $G$ nằm trong tam giác và không có điểm nguyên nằm trên các cạnh của tam giác ngoài $A,B,C$ . Chứng minh rằng $G$ là trọng tâm của tam giác $ABC$ .

Lời giải. Theo định lí Pick, ba tam giác $ABG$ , $BCG$ và $CAG$ có diện tích bằng nhau và bằng $\dfrac{1}{2}$ . Suy ra $G$ là trọng tâm của tam giác $ABC$ . $\Box$

Ví dụ 2. Các đỉnh của một ngũ giác lồi là các điểm nguyên. Chứng minh rằng diện tích của ngũ giác đó không bé hơn $\dfrac{5}{2}$ .

Lời giải. Đầu tiên ta giả sử rằng trên biên của ngũ giác không có điểm nguyên khác các đỉnh. Vì số xâu nhị phân độ dài $2$ bằng $4$ nên tồn tại hai đỉnh của ngũ giác sao cho hai hoành độ và hai tung độ của chúng có cùng tính chẵn – lẻ, trung điểm của đoạn thẳng nối hai điểm này là một điểm nguyên nằm trong hoặc trên biên của ngũ giác, do ta đang xét trường hợp trên biên của ngũ giác không có điểm nguyên khác các đỉnh nên điểm nguyên này nằm trong ngũ giác. Như vậy là bên trong ngũ giác có ít nhất một điểm nguyên, theo định lí Pick, diện tích của nó không bé hơn $1+\dfrac{5}{2}-1=\dfrac{5}{2}$ .

Nếu trên trên biên của ngũ giác có điểm nguyên khác các đỉnh thì ta bỏ một trong hai đầu mút của cạnh chứa điểm nguyên, thay vào điểm nguyên đó và thu được một ngũ giác có diện tích bé hơn ngũ giác ban đầu. Làm như vậy hữu hạn lần ta sẽ có một ngũ giác mà trên biên của nó không có điểm nguyên khác các đỉnh. $\Box$

Trong các ví dụ dưới đây ta chỉ cần dùng công thức dây giầy là đủ, dùng công thức này ta có diện tích của các đa giác đơn với các đỉnh có tọa độ hữu tỷ là số hữu tỷ.

Ví dụ 3. Tìm tất cả các số nguyên dương $n$ sao cho tồn tại $n-$ giác đều có các đỉnh là các điểm nguyên.

Lời giải 1. Giả sử tồn tại $n-$ giác đều $A_1A_2\ldots A_n$ sao cho các đỉnh của nó là các điểm nguyên. Theo định lí Pick, diện tích của tam giác $A_1A_2A_3$ là một số hữu tỷ, suy ra

$\displaystyle A_1A_3.A_1A_2\sin \widehat{A_2A_1A_3}\in\mathbb{Q}\Rightarrow \sin^2\dfrac{\pi}{n}\in\mathbb{Q}\Rightarrow 2\cos \dfrac{2\pi}{n}\in\mathbb{Q}.\quad (1)$

Xét dãy đa thức $\{F_n\}_{n\geq 1}$ xác định bởi $F_1(x)=x,F_2(x)=x^2-2$ và $F_{n+2}(x)=xF_{n+1}(x)-F_n(x),\quad n\geq 1.$ Dễ thấy với mỗi $n$ , $F_n$ là monic, có bậc $n$ , có hệ số nguyên và $F_n(2\cos t)=2\cos nt,\quad\forall t\in\mathbb{R}.$

Ta có $F_n\left(2\cos \dfrac{2\pi}{n}\right)=2$ , suy ra $2\cos \dfrac{2\pi}{n}$ là một nghiệm của đa thức $F_n-2. \quad (2)$

Từ $(1)$ và $(2)$ suy ra $\displaystyle 2\cos \dfrac{2\pi}{n}\in\mathbb{Z}\Rightarrow 2\cos \dfrac{2\pi}{n}\in\{\pm 1;0;\pm 2\}.$ Do đó $n\in\{3;4;6\}$ .

Tiếp theo ta sẽ chứng minh rằng không tồn tại tam giác đều có các đỉnh là các điểm nguyên, và do đó $n=4$ .

Giả sử ngược lại, tồn tại tam giác đều $ABC$ với các đỉnh có tọa độ nguyên. Theo định lí Pick, $2S_{ABC}$ là số nguyên, suy ra $AB.AC\sin \dfrac{\pi}{3}\in\mathbb{Z}$ , do đó tồn tại các số tự nhiên $x,y,z$ và $w$ sao cho $3(x^2+y^2)(z^2+w^2)$ là số chính phương dương, mà $v_3(u^2+v^2)$ là số chẵn khi $u,v$ là các số tự nhiên không đồng thời bằng $0$ , suy ra mẫu thuẫn.

Ngược lại, dễ thấy tồn tại hình vuông có các đỉnh là các điểm nguyên. Suy ra chỉ có $n=4$ thỏa mãn điều kiện của bài toán. $\Box$

Ví dụ 4. Cho $n\ge 3$ là một số nguyên. Chứng minh rằng tồn tại $n$ điểm trong mặt phẳng sao cho khoảng cách giữa hai điểm bất kì là số vô tỷ, và mỗi ba điểm là các đỉnh của một tam giác không suy biến với diện tích là số hữu tỷ.

Lời giải 1. Lấy $n$ điểm nguyên $(i;i^2)$ trên parabol $y=x^2\quad (i=1,2,\cdots)$ . Bởi định lí Pick, ba điểm bất kì là ba đỉnh của một tam giác không suy biến có diện tích hữu tỷ. Bình phương khoảng cách giữa hai điểm $(a,a^2)$ và $(b,b^2)$ bằng $(a - b)^2 + (a^2 - b^2)^2 = (a - b)^2(1 + (a + b)^2),$ và không phải số chính phương. $\Box$

Lời giải 2. Chọn $C$ là một bội nguyên dương đủ lớn của $n!$ . Xét $n$ điểm nguyên

$A_1=(C+1,C^{C+1}),A_2=(C+2,C^{C+2}),..,A_n=(C+n,C^{C+n}).$

Với hai điểm khác nhau $A_i,A_j$ ta có $A_i,A_j^2=(i-j)^2+(C^{C+i}-C^{C+j})^2$ không là số chính phương. Thật vậy, nếu ngược lại ta sẽ có số nguyên dương $D$ thỏa mãn

$(i-j)^2+(C^{C+i}-C^{C+j})^2=D^2,$ từ đẳng thức này ta có $D$ chia hết cho $i-j$ và $\displaystyle 1+\left(\dfrac{C^{C+i}-C^{C+j}}{i-j}\right)^2=\left(\dfrac{D}{i-j}\right)^2,$ không thể xảy ra điều này.

Ba điểm bất kì trong $n$ điểm đã chọn không thẳng hàng vì chúng thuộc đồ thị của hàm số mũ $y=C^{C+x}$ . Theo định Pick, ba điểm bất kì là ba đỉnh của một tam giác có diện tích hữu tỷ. $\Box$

Lời giải 3. Bằng quy nạp, ta sẽ xây dựng dãy điểm nguyên $\{A_n=(x_n,y_n)\}_{n\geq 1}$ sao cho với mọi $n\geq 3$ , dãy điểm $A_1,A_2,\ldots,A_n$ thỏa mãn các điều kiện của bài toán và các hoành độ cũng như các tung độ đôi một khác nhau. Theo định Pick, ba điểm bất kì là ba đỉnh của một tam giác (có thể suy biến) có diện tích hữu tỷ, do đó ta chỉ cần xây dựng dãy trên sao cho không có ba điểm nào thẳng hàng và khoảng cách giữa hai điểm bất kỳ là số vô tỷ.

Đầu tiên ta thấy $A_1=(0,0),\ A_2=(1,1),\ A_3=(3,2)$ thỏa mãn. Giả sử rằng với $n\ge 4$ nào đấy ta đã có dãy điểm nguyên $A_1,A_2,\ldots,A_{n-1}$ thỏa mãn. Với mỗi $i=\overline{1,n-1}$ lấy các số nguyên tố $p_i$ sao cho $p_i\equiv 1\pmod 4$ , và các số nguyên $a_i,b_i$ thỏa mãn $p_i\not|a_i,b_i$ và $p_i|a_i^2+b_i^2$ .

Chọn số nguyên $k_i$ để $v_{p_i}[(a_i+k_ip_i)^2+b_i^2]=1$ . Theo định lí phần dư Trung Hoa, tồn tại các số nguyên $x_n\not= x_i,y_n\not=y_i$ sao cho $x_n-x_i\equiv a_i+k_ip_i\pmod{p_i^2}$ , $x_n-x_i\equiv 0\pmod{p}$ và $\ y_n-y_i\equiv b_i\pmod{p_i^2},\ \forall i\in\overline{1,n-1}$ . Ở đây $p$ là số nguyên tố khác tất cả $p_i$ và không chia hết $\displaystyle \prod_{i\not=j}(x_i-x_j)(y_i-y_j)$ và $\displaystyle\prod (y_n-y_i)$ , tất nhiên là ta chọn $y_n$ trước và $x_n$ sau. Ta có $v_{p_i}[(x_n-x_i)^2+(y_n-y_i)^2]=1$ , suy ra $A_nA_i$ là các số vô tỷ với $\ i=\overline{1,n-1}$ . Do $\dfrac{y_n-y_i}{x_n-x_i}\ne\dfrac{y_i-y_j}{x_i-x_j},\ \forall i\ne j\in\overline{1,n-1}$ nên $A_n,A_i$ và $A_j$ không thẳng hàng. $\Box$

4. Bài tập

Bài 1. Cho đa giác đơn $P$ . Chứng minh rằng tồn tại một đường chéo của $P$ nằm trong nó.

Bài 2. Chứng minh định lí Pick khi $P$ là hình chữ nhật có các cạnh cùng phương với các trục tọa độ hoặc là tam giác vuông có các cạnh góc vuông cùng phương với các trục tọa độ.

Bài 3. Cho $n-$ giác đều $P$ . Chứng minh rằng nếu $3$ trong các đỉnh của $P$ là điểm nguyên và hai trong chúng là kề nhau thì $P$ là hình vuông.

Bài 4. Biết rằng có tồn tại một $n-$ giác đơn có các đỉnh nguyên sao cho trên biên của nó có đúng $n$ điểm nguyên và không có điểm nguyên nào nằm trong nó. Chứng minh rằng $n\leq 4$ .

Bài 5. Chứng minh rằng với mỗi số nguyên dương $n$ ta có $\displaystyle\sum_{i=1}^{n^2} \lfloor \frac{i}{3} \rfloor= \frac{n^2(n^2-1)}{6}.$

Bài 6. Cho $m,n\in\mathbb{Z^{+}}$ , chứng minh rằng mọi hình chữ nhật kích thước $m\times n$ phủ nhiều nhất $(m+1)(n+1)$ điểm nguyên.

Bài 7. Cho ngũ giác lồi $P$ có các đỉnh là các điểm nguyên. Các đường chéo của $P$ tạo thành một ngũ giác lồi $Q$ nằm trong $P$ . Chứng minh rằng trong hoặc trên biên của $Q$ có ít nhất một điểm nguyên.

Bài 8. Đặt $V_n=\sqrt{F_n^2+F_{n+2}^2}$ , ở đây $F_n$ là số Fibonacci thứ $n$ . Chứng minh rằng với mỗi số nguyên dương $n$ , tồn tại tam giác cơ bản với độ dài ba cạnh bằng $V_n, V_{n+1}, V_{n+2}$ .

Bài 9. Cho số nguyên tố $p$ và một hình vuông có các đỉnh có tọa độ nguyên. Biết độ dài cạnh hình vuông là $\sqrt{p}$ , tìm số điểm nguyên nằm trong hình vuông.

Tags IMO, imo 2017, Pick's theorem, TST, Vietnam TST, Vietnam TST 2017, vmo, điểm nguyên

Algebra Combinatorics Geometry Mathematical Olympiad Number theory

Số nghiệm của phương trình ax+by=n

Post author By Nguyen Trung Tuan
Post date February 18, 2017
1 Comment on Số nghiệm của phương trình ax+by=n

Bài viết 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$ và áp dụng công thức đó vào giải bài toán Frobenius với một tập có hai phần tử. Ở cuối bài viết chúng tôi cũng giới thiệu một số bài toán thi chọn học sinh giỏi liên quan.

1. Công thức Popoviciu

Trong mục 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 $\gcd (a,b)=1$ và $n$ là số tự nhiên.

Định lí 1. (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 $\gcd (a,b)=1$ và $n$ 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 $a$ và $b^{-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)$

Vì $\gcd (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}$ và $\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$

2. Áp dụng vào bài toán Frobenius

Tags hình học của số, lưới nguyên, điểm nguyên

Algebra Combinatorics Contests Geometry Grade 8, 9 Mathematical Olympiad Number theory

Một số trang về Olympic Toán

Post author By Nguyen Trung Tuan
Post date December 4, 2016
4 Comments on Một số trang về Olympic Toán

Tôi có post một số trang về Olympic Toán trên facebook nhưng nó cứ chìm xuống khi đăng một bài khác, vì thế nên tôi lập topic này để lưu các link đó lại.

P. S. Hãy góp link bằng cách comment các bạn nhé! 🙂

Algebra Combinatorics Mathematical Olympiad Number theory

Một chứng minh của định lý Cauchy – Davenport

Post author By Nguyen Trung Tuan
Post date November 30, 2015
No Comments on 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 khác rỗng các số nguyên $A,B$ . Với mỗi tập $X$ các số nguyên, ký hiệu $(X)_p$ là tập tất cả các số tự nhiên $r<p$ sao cho tồn tại $x\in X$ thỏa mãn $x\equiv r\pmod{p}$ . Khi đó ta có $|(A+B)_p|\geq\min (p,|(A)_p|+|(B)_p|-1).$

Tags Cauchy, Davenport, dư, lớp

College Math Combinatorics Mathematical Olympiad

Bổ đề Burnside và áp dụng của nó vào bài toán đếm

Post author By Nguyen Trung Tuan
Post date March 25, 2010
3 Comments on Bổ đề Burnside và áp dụng của nó vào bài toán đếm

Cho $X$ là một tập hợp và $G$ là một nhóm. Ta nói $G$ tác động trên $X$ , hay $X$ là một $G-$ tập, nếu có hàm $G\times X\to X$ , $(g,x)\mapsto gx$ thoả mãn $ex=x\forall x\in X$ và $g_1(g_2x)=(g_1g_2)x\forall x\in X\forall g_1,g_2\in G$ , ở đây $e$ là phần tử đơn vị của $G$ .

Gìơ ta xét một $G-$ tập $X$ , với mỗi $x\in X$ , ta gọi quỹ đạo của $x$ là tập $\{gx|g\in G\}$ . Các quỹ đạo khác nhau của các phần tử trong $X$ làm thành một phân hoạch của $X$ , thật vậy, quan hệ $xRy$ nếu có $g\in G$ để $x=gy$ là một quan hệ tương đương trên $X$ . Khi $X$ và $G$ là các tập hữu hạn thì ta có thể tính số khối của phân hoạch này theo bổ đề sau đây.

Bổ đề Burnside. Nếu $X$ là một $G-$ tập hữu hạn (nghĩa là $X$ và $G$ là các tập hữu hạn và $X$ là một $G-$ tập) và $N$ là số các quỹ đạo khác nhau của các phần tử trong $X$ thì $N=\dfrac{1}{|G|}\sum_{g\in G}F(g)$ , trong đó với mỗi $g\in G$ , $F(g)$ là số phần tử của tập $\{x\in X|gx=x\}$ .

Tôi sẽ không đưa ra chứng minh nào của bổ đề này ở đây, các bạn có thể tìm một chứng minh trong sách Tổ hợp của Ngô Đắc Tân hay sách về lý thuyết nhóm của Rotman. Gìơ ta đi xét các áp dụng của bổ đề này vào giải các bài toán đếm, các bài tập này đều có trong sách của Rotman.

Bài 1. Cho $n$ và $q$ là các số nguyên dương. Hỏi có bao nhiêu lá cờ gồm $n$ mảnh sao cho mỗi mảnh mang một trong $q$ màu cho trước?(Ví dụ một lá cờ như vậy là cờ của Pháp gồm $3$ mảnh).

Lời giải. Vì khi ta tô màu một mặt của lá cờ thì mặt sau sẽ được xác định hoàn toàn màu. Nên số lá cờ bằng số cách tô bảng $1\times n$ bởi $q$ màu, hai cách tô là như nhau nếu nó ở dạng như hình dưới đây.

(Trong hình trên các $c_i$ là các màu.)

Gọi $X$ là tập các bộ $(c_1,c_2,\cdots,c_n)$ với $c_i$ là một trong $q$ màu đã cho với mỗi $i$ . Ký hiệu $S_n$ là nhóm các hoán vị trên $\{1,2,\cdots,n\}$ , $G$ là nhóm con cyclic sinh bởi hoán vị $f$ của $S_n$ , ở đây $f(i)=n+1-i\forall i$ . Ta cho $G$ tác động trên $X$ theo luật $f(c_1,c_2,\cdots,c_n)=(c_n,c_{n-1},\cdots,c_1)$ . Như trên đã phân tích, ta chỉ cần đếm số $N$ các quỹ đạo của các phần tử của $x$ theo tác động này là xong. Theo bổ đề Burnside, ta chỉ cần tính $F(id)$ và $F(f)$ . Dễ thấy $F(id)=|X|=q^n$ theo quy tắc nhân. Để tính $F(f)$ , ta chú ý rằng $(c_1,c_2,\cdots,c_n)\in X$ không thay đổi khi tác động $f$ nếu và chỉ nếu $c_1=c_n,c_2=c_{n-1},\cdots$ , vậy cùng theo quy tắc nhân ta có $F(f)=q^{[\dfrac{n+1}{2}]}$ . Như thế đáp số của bài toán là $\dfrac{1}{2}(q^n+q^{[\dfrac{n+1}{2}]}).$

Bài 2. Cho $n$ và $q$ là các số nguyên dương. Chứng minh rằng có

$\dfrac{1}{4}(q^{n^2}+2q^{[\dfrac{n^2+3}{4}]}+q^{[\dfrac{n^2+1}{2}]})$ cách tô màu bảng vuông $n\times n$ bởi $q$ màu.

Lời giải sơ lược. Lời giải y hệt như trường hợp trên. Ta đánh số các ô của bảng theo kiểu xoáy ốc, chia hai trường hợp $n$ chẵn, lẻ cho dễ đánh số. Tập $X$ bây giờ là tập tất cả các bộ $(c_1,c_2,\cdots,c_{n^2})$ , nhóm $G$ bây giờ là nhóm con cyclic cấp $4$ sinh bởi phép quay $+90^0$ của $S_{n^2}$ .

Chú ý. Khi $n=3,q=n$ ta có bài số 5 trong VMO 2010.