IMO 2017 training (2)


Chào các bạn đồng nghiệp,

đây là một số bài toán tôi dùng để luyện cho đội IMO 2017. Tuyển tập này gồm nhiều phần, đây là phần thứ hai.

Các bạn có thể xem phần đầu ở https://nttuan.org/2017/08/01/imo-2017-training-1/


Bài 1. Cho số nguyên dương \displaystyle n>1 và dãy số Fibonacci xác định như sau \displaystyle f_1=f_2=1, \displaystyle f_{k+2}=f_{k+1}+f_k,\,\forall k\in\mathbb{N}^*. Chứng minh rằng nếu \displaystyle a\displaystyle b là các số nguyên dương sao cho \displaystyle \dfrac{a}{b} nằm giữa hai phân số \displaystyle \dfrac{f_n}{f_{n-1}}\displaystyle \dfrac{f_{n+1}}{f_{n}} thì \displaystyle b\geq f_{n+1}.
Bài 2. (VMO 2013) Cho trước một số số tự nhiên được viết trên một đường thẳng. Ta thực hiện các bước điền số lên đường thẳng như sau: tại mỗi bước, trước tiên xác định tất cả các cặp số kề nhau hiện có trên đường thẳng theo thứ tự từ trái qua phải, sau đó điền vào giữa mỗi cặp một số bằng tổng của hai số thuộc cặp đó. Hỏi sau \displaystyle 2013 bước, số \displaystyle 2013 xuất hiện bao nhiêu lần trên đường thẳng trong các trường hợp sau:
a) Các số cho trước là: \displaystyle 1\displaystyle 1000?
b) Các số cho trước là: \displaystyle 1,2,...,1000 và được xếp theo thức tự tăng dần từ trái qua phải?
Bài 3. Dãy hữu hạn các số nguyên \displaystyle a_1, a_2, \dots, a_n được gọi là chính quy nếu tồn tại số thực \displaystyle x thỏa mãn \displaystyle \left\lfloor kx \right\rfloor = a_k với mọi \displaystyle k=1, 2,\cdots, n. Cho dãy chính quy \displaystyle a_1, a_2, \dots, a_n, với \displaystyle 1 \le k \le n ta nói \displaystyle a_k là số hạng bắt buộc nếu dãy \displaystyle a_1, a_2, \dots, a_{k-1}, b chính quy khi và chỉ khi \displaystyle b = a_k. Tìm số lớn nhất các số hạng bắt buộc của một dãy chính quy dài \displaystyle 1000.
Bài 4. Cho \displaystyle \nu là một số vô tỷ dương, và \displaystyle m là một số nguyên dương. Một cặp \displaystyle (a,b) các số nguyên dương được gọi là tốt nếu
\displaystyle a \left \lceil b\nu \right \rceil - b \left \lfloor a \nu \right \rfloor = m. Một cặp tốt \displaystyle (a,b) được gọi là rất tốt nếu không cặp nào trong hai cặp \displaystyle (a-b,b), \displaystyle (a,b-a) là tốt. Chứng minh rằng số cặp rất tốt bằng tổng các ước dương của \displaystyle m.
Bài 5. Cho \displaystyle m,n là các số nguyên dương thỏa mãn \displaystyle m \ge n. Gọi \displaystyle S là tập tất cả các cặp \displaystyle (a,b) các số nguyên dương nguyên tố cùng nhau thỏa mãn \displaystyle a,b \le m\displaystyle a+b > m. Với mỗi \displaystyle (a,b)\in S, xét nghiệm tự nhiên \displaystyle (u,v) của phương trình \displaystyle au - bv = n sao cho \displaystyle v nhỏ nhất, và gọi \displaystyle I(a,b) là khoảng \displaystyle (v/a, u/b). Chứng minh rằng \displaystyle I(a,b) \subset (0,1) với mọi \displaystyle (a,b)\in S và mỗi số vô tỷ \displaystyle \alpha\in(0,1) thuộc \displaystyle I(a,b) với đúng \displaystyle n cặp phân biệt \displaystyle (a,b)\in S.
Bài 6. Một số nguyên dương \displaystyle q được gọi là mẫu phù hợp của số thực \displaystyle \alpha nếu \displaystyle \displaystyle |\alpha - \dfrac{p}{q}|<\dfrac{1}{10q} với số nguyên \displaystyle p nào đó. Chứng minh nếu hai số vô tỷ \displaystyle \alpha\displaystyle \beta có cùng tập các mẫu phù hợp thì \displaystyle \alpha+\beta hoặc \displaystyle \alpha- \beta là một số nguyên. Continue reading “IMO 2017 training (2)”

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”

Min Ru’s book


Min Ru, Nevanlinna Theory and Its Relation to Diophantine Approximation

It was discovered recently that Nevanlinna theory and Diophantine approximation bear striking similarities and connections. This book provides an introduction to both Nevanlinna theory and Diophantine approximation, with emphasis on the analogy between these two subjects.

Each chapter is divided into part A and part B. Part A deals with Nevanlinna theory and part B covers Diophantine approximation. At the end of each chapter, a table is provided to indicate the correspondence of theorems.
Contents:

  • Nevanlinna Theory for Meromorphic Functions and Roth’s Theorem
  • Holomorphic Curves into Compact Riemann Surfaces and Theorems of Siegel, Roth, and Faltings
  • Holomorphic Curves in Pn(C) and Schmidt’s Sub-Space Theorem
  • The Moving Target Problems
  • Equi-Dimensional Nevanlinna Theory and Vojta’s Conjecture
  • Holomorphic Curves in Abelian Varieties and the Theorem of Faltings
  • Complex Hyperbolic Manifolds and Lang’s Conjecture