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\displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1\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}.\displaystyle ck-dh\geq 1\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\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}\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\displaystyle d thỏa mãn \displaystyle 0\leq \frac{a}{b}<\frac{c}{d}\leq 1\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}\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)\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 Continue reading “Farey sequence”

Góc trong mặt phẳng tọa độ (1)


Bài 1. Cho d:2x+3y+1=0,M(1;1). Viết phương trình đường thẳng qua M và tạo với d góc 45^0.

Đáp số. 5x+y-6=0,x-5y-4=0.

Bài 2. Viết phương trình của phân giác của góc nhọn tạo bởi d_1:x-2y-5=0d_2:2x-y+2=0.

Bài 3. Viết phương trình phân giác trong và ngoài xuất phát từ đỉnh A của tam giác ABC với A(1;1),B(10;13)C(13;6).

Bài 4. \Delta ABC cân tại A với AB:x+2y-1=0,BC:3x-y+5=0. Viết phương trình đường thẳng chứa cạnh AC nếu nó đi qua M(1;-3).

Bài 5. Hình vuông ABCD có đường chéo AC:x+y-10=0. Tìm B biết CD qua M(6;2)AB qua N(5;8).

Đáp số. (8;8),(5;4).

Bài 6. Cho tam giác ABC vuông cân tại A, cạnh huyền nằm trên d:x+7y-31=0, AC đi qua N(1;5/2), AB qua M(2;-3). Tìm các đỉnh.

Bài 7. d_1:2x-y+5=0;\quad d_2:3x+6y-7=0. Lập phương trình đường thẳng qua A(2;-1) và tạo với d_1,d_2 một tam giác cân.

Đáp số. 3x+y-5=0;\quad x-3y-5=0. Continue reading “Góc trong mặt phẳng tọa độ (1)”

Khoảng cách trong mặt phẳng tọa độ (1)


Bài 1. Tam giác ABCAB:x-y+4=0,BC:3x+5y+4=0CA:7x+y-12=0. Hỏi O nằm trong hay ngoài tam giác?

Bài 2. Cho M(1;4),N(6;2). Lập phương trình đường thẳng qua M sao cho khoảng cách từ N đến nó bằng 5.

Bài 3. Cho A(1;2),B(5;-1). Viết phương trình đường thẳng qua (3;5) và cách đều A,B.

Bài 4. Cho A(1;1),B(4;-3). Tìm C thuộc d:x-2y-1=0 sao cho d(C,AB)=6.

Bài 5. Cho d_1:x+y+3=0,d_2:x-y-4=0;d_3:x-2y=0. Tìm M\in d_3 để d(M,d_1)=2d(M,d_2). Continue reading “Khoảng cách trong mặt phẳng tọa độ (1)”

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)=1n 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)=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)

\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}\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). Continue reading “Số nghiệm của phương trình ax+by=n”

Một số kết quả trong Hình học phẳng


Tài liệu có một số kết quả hay dùng trong Hình học giải tích phẳng.

Continue reading “Một số kết quả trong Hình học phẳng”

Điểm và đường thẳng trong Oxy (1)


Bài 1. Cho A(-1;1)B(2;3).

a) Chứng minh rằng O,A,B không thẳng hàng. Viết phương trình các cạnh của \Delta AOB;

b) Viết phương trình đường cao qua A, phân giác trong qua A của \Delta AOB;

c) Tìm tọa độ trực tâm, tâm đường tròn ngoại tiếp, nội tiếp của \Delta AOB;

d) Tìm tọa độ A' đối xứng với A qua BO;

e) Viết phương trình đường thẳng qua A và song song với BO;

f) Viết phương trình đường thẳng qua A tạo với BO góc $60^{\circ}$.

Bài 2. Cho tam giác ABCM(2;1)  là trung điểm cạnh AC, điểm H(0;-3) là chân đường cao kẻ từ A, điểm E(23;-2) thuộc đường thẳng chứa trung tuyến kẻ từ C. Tìm tọa độ điểm B biết điểm A thuộc đường thẳng d:2x+3y-5=0  và điểm C có hoành độ dương.

Bài 3.  Cho tam giác ABC có đỉnh A(3;3) tâm đường tròn ngoại tiếp I(2;1) phương trình đường phân giác trong góc \widehat{BAC}x-y=0. Tìm tọa độ các đỉnh B, C biết rằng BC=8/\sqrt{5} và góc \widehat{BAC} nhọn.

Bài 4.  Cho tam giác ABC có phương trình đường thẳng chứa đường cao kẻ từ Bx+3y-18=0, phương trình đường thẳng trung trực của đoạn thẳng BC3x+19y-279=0, đỉnh C thuộc đường thẳng d:2x-y+5=0. Tìm tọa độ đỉnh A biết rằng \widehat{BAC}=135^{\circ}.

Bài 5. Cho hình vuông ABCD. Gọi M là trung điểm của BC, N nằm trên cạnh CD sao cho CN=2ND. Biết M=(11/2;1/2) và $AN$ có phương trình 2x-y-3=0. Tìm A.

Bài 6.  Cho tam giác ABC có đường cao AH:3x+4y+10=0, phân giác trong BE:x-y+1=0. Điểm M(0;2)\in AB và cách C một khoảng \sqrt{2}. Tính S_{ABC}.

Bài 7.  Cho hình chữ nhật ABCDS=12, tâm I(9/2;3/2), trung điểm của BCM(3;0)x_B>x_C. Xác định tọa độ các đỉnh của nó.

Bài 8.  \Delta ABC có tâm đường tròn ngoại tiếp I(4;-1), đường cao và trung tuyến qua A có phương trình lần lượt là d_1:x+y-1=0,d_2:x+2y-1=0. Viết phương trình các đường thẳng chứa các cạnh của nó.

Bài 9.  Cho hình chữ nhật ABCD trong mặt phẳng tọa độ Oxy. Cạnh AB có phương trình là x-y+3=0. I(0;1) là giao điểm của ACBD. Tìm tọa độ các đỉnh A, B, C, D nếu AB=3AD và điểm A có hoành độ lớn hơn hoành độ của điểm B.

Bài 10.  Cho hình vuông MNPQ. Biết MN,NP,PQ,QM lần lượt đi qua các điểm A(10;3),B(7;-2),C(-3;4),D(4;-7). Lập phương trình MN. Continue reading “Điểm và đường thẳng trong Oxy (1)”

Một bài mở đầu về Hình học giải tích phẳng


Bài toán. Cho hai điểm A(1;0)B(2;3).
1) Chứng minh rằng O,A,B không thẳng hàng. Viết phương trình đường thẳng chứa cạnh AB của OAB;
2) Viết phương trình đường thẳng qua A và song song với OB;
3) Viết phương trình đường thẳng chứa đường cao qua O của tam giác OAB;
4) Tìm tọa độ hình chiếu vuông góc của O trên đường thẳng AB;
5) Tìm tọa độ của điểm O' đối xứng với O qua AB. Continue reading “Một bài mở đầu về Hình học giải tích phẳng”

Bài tập Đại số và Hình học (Ôn tập tháng 12)


Bài 1. Cho tam giác ABC với ba đỉnh A(2;5),B(4;-3)C(-1;6).

a) Xác định toạ độ điểm I sao cho \overrightarrow{IA}+3\overrightarrow{IB}-2\overrightarrow{IC}=\overrightarrow{0};

b) Xác định toạ độ của điểm D sao cho 3\overrightarrow{DB}-2\overrightarrow{CD}=\overrightarrow{0};

c) Chứng minh A,B,C không thẳng hàng và A,I,D thẳng hàng;

d) Gọi E là trung điểm của ABN là điểm sao cho \overrightarrow{AN}=k\overrightarrow{AC}. Tìm k để AD,EN,BC đồng quy;

e) Tìm tập các điểm M trong mặt phẳng sao cho

|\overrightarrow{MA}+3\overrightarrow{MB}-2\overrightarrow{MC}|=|2\overrightarrow{MA}-\overrightarrow{MB}-\overrightarrow{MC}|.

Bài 2. Cho tam giác ABC có toạ độ ba đỉnh là A(0;6),B(-2;0),C(2;0). Gọi G là trọng tâm của tam giác ACM, trong đó M là trung điểm của AB.

a) Tìm toạ độ của G;

b) Tìm toạ độ tâm I của đường tròn ngoại tiếp tam giác ABC;

c) Chứng minh GI vuông góc với CM.

Bài 3. Cho tam giác ABC với A(0;-4),B(-5;6),C(3;2).

a) Tìm toạ độ chân đường cao hạ từ A của tam giác;

b) Tìm toạ độ trực tâm của tam giác;

c) Tìm toạ độ tâm đường tròn ngoại tiếp của tam giác;

d) Tìm toạ độ chân các đường phân giác trong và ngoài của góc A;

e) Tìm toạ độ tâm đường tròn nội tiếp của tam giác.

Bài 4. a) Cho hai điểm A(-3;2),B(4;3). Tìm M trên trục hoành để tam giác MAB vuông tại M;

b) Cho tam giác ABC với A(1;-1),B(5;-3) và đỉnh C trên Oy. Ngoài ra trọng tâm G của tam giác ABC nằm trên Ox. Tìm toạ độ đỉnh C và trọng tâm G.

Bài 5. Cho bốn điểm A(-1;3),B(0;4),C(3;5)D(8;0). Chứng minh rằng bốn điểm này nằm trên một đường tròn.

Bài 6. Tìm tập xác định của các hàm số

a) y=\dfrac{1}{\sqrt{(x+1)^2}}; b) y=\sqrt{2+x}+\sqrt{2-x};

c) y=\sqrt{x+\sqrt{x^2-x+1}}; d) y=\sqrt{1-x}-\dfrac{1}{x\sqrt{1+x}};

e) y=\sqrt{x^2+3x-4}+\dfrac{1}{\sqrt{x^2-4}}; f) y=\sqrt{\dfrac{1+x}{1-x}}+\sqrt{\dfrac{1-x}{1+x}};

g) y=\sqrt{1-2|x|}; h) y=\dfrac{3x-1}{\sqrt{x|x|-4}}.

Bài 7. Tìm các giá trị của m để các hàm số sau xác định với mỗi x>0

a)     y=\sqrt{x+m}-\sqrt{2x-m+1}; b) y=\sqrt{2x-3m+4}-\dfrac{x-m}{x+m-1}.

Bài 8. Tìm m để hàm số sau xác định trên khoảng (-1;0)

y=\dfrac{1}{\sqrt{x+m}}-\sqrt{-x-2m+6}.

Bài 9. Xét tính chẵn lẻ của các hàm số sau

a) y=\dfrac{x^2|x-1|}{\sqrt{(x-1)^2}}; b) y=\dfrac{|x-1|-|x+1|}{|x-1|+|x+1|};

c) y=x\sqrt{x^2}; d) y=\sqrt{x^2-6x+9}+|x+3|; e) y=x^2-3x+2.

Bài 10. Cho hàm số f(x)=\dfrac{x}{\sqrt{1+x^2}} xác định trên \mathbb{R}. Tính f(f(x)),f(f(f(x)))f(f(\cdots (f(x))\cdots)) (n chữ f).

Bài 11. Cho hàm số y=ax^2+bx+c với a\not =0.

a) Biết đồ thị (P) của hàm số đã cho có đỉnh S(1;4) và cắt trục tung tại điểm có tung độ bằng 3. Tìm a,b,c;

b) Khảo sát sự biến thiên và vẽ đồ thì của hàm số ở câu a);

c) Từ đồ thị (P) hãy suy ra đồ thị của các hàm số y=-x^2+2|x|+3y=|-x^2+2|x|+3|;

d) Bằng đồ thị hãy biện luận số nghiệm của phương trình |-x^2+2|x|+3|=m-1 theo m.