Category: Algebra

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

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

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).

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