Category: Number Theory

USEMO – United States Ersatz Math Olympiad


USEMO là một cuộc thi toán dành cho tất cả học sinh trung học cơ sở và trung học phổ thông Hoa Kỳ. Giống như nhiều cuộc thi, mục tiêu của nó là phát triển sự quan tâm và khả năng trong toán học (chứ không phải là đo lường nó). Tuy nhiên, đây là một trong số ít các cuộc thi cho tất cả học sinh trung học cơ sở và trung học phổ thông Hoa Kỳ.

USEMO được lưu trữ trên trang AoPS. Cuộc thi này không được tài trợ bởi MAA.

Độ khó của các bài toán của cuộc thi tương tự như IMO.

Các bạn có thể tìm hiểu thêm về cuộc thi ở đây, hoặc download.

Popoviciu’s theorem


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)=1 và n 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)=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ì (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

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é! 🙂

Continue reading “Một số trang về Olympic Toán”