The number of prime factors of a natural number

Mỗi năm, khi được mời dạy cho đội tuyển Việt Nam tham dự Olympic Toán quốc tế (IMO), tôi thường mang đến cho các em vài bài toán rất khó, và hy vọng một lời giải thanh nhã từ các thành viên của đội tuyển. Dưới đây là một bài cho đội tuyển IMO năm 2021.

Bài toán. Với mỗi số nguyên dương $n,$ gọi $\omega (n)$ là số ước nguyên tố của $n$ . Chứng minh rằng tồn tại số nguyên dương $n$ sao cho $\omega (n+1)<\omega (n+2)<\ldots <\omega (n+100).$

Lời giải. Với hai hàm $f(x)$ và $g(x)$ từ tập các số nguyên dương đến tập các số thực dương ta viết $f=o(g)$ nếu $f/g\to 0$ khi $x\to\infty$ . Thay $100$ bởi $k > 2$ . Gọi $A$ là một số nguyên dương phụ thuộc $k$ mà ta sẽ chọn sau. Giả sử $q_1<q_2<\cdots<q_m<\cdots$ là dãy tất cả các số nguyên tố lớn hơn $k$ . Với $j=1, \ldots, k$ , đặt $T_j=$ $j(j-1) / 2$ và $\displaystyle M_j=\prod_{\ell=T_j A+1}^{T_{j+1} A} q_{\ell}.$ Đặt $\displaystyle M=\prod_{j=1}^k M_j$ và gọi $N$ là số nguyên dương nhỏ nhất sao cho $M_j$ chia hết $N+j$ với mỗi $j\in [k]$ . Ta có ngay $N+k<M$ . Thật vậy, nếu không thì $N=M-i$ với $i \in [k]$ , lấy $j \in [k]\setminus \{i\}$ , ta có $M_j \mid N+j=M+(j-i)$ ; suy ra $M_j \mid j-i$ , vô lý.

Xét số $n=M \lambda+N$ , ở đây $\lambda$ là số nguyên dương mà $\lambda \in[M, 2 M]$ . Ta có

$\displaystyle n+j=M \lambda+(N+j)=M_j\left(\left(M / M_j\right) \lambda+(N+j) / M_j\right), \quad j=1, \ldots, k .$

Khi đặt $A_j=(N+j) / M_j$ và $B_j=M / M_j$ , ta có

$\displaystyle j A=T_{j+1} A-T_j A=\omega\left(M_j\right) \leq \omega(n+j) \leq j A+\omega\left(B_j \lambda+A_j\right),$

suy ra nếu $\lambda$ thỏa mãn $\displaystyle \omega\left(B_j \lambda+A_j\right)<A, \quad \forall j=1, \ldots, k-1,\quad (1)$ thì

$\displaystyle jA \leq\omega(n+j)<j A+A \leq \omega(n+j+1), \quad\forall j=1, \ldots, k-1,$

và bài toán được giải. Vậy sẽ là đủ nếu ta chỉ ra có $A$ để tồn tại $\lambda$ thỏa mãn $(1)$ .

Với mỗi $j<k$ , ta có $(A_j,B_j)=1$ . Thật vậy, xét một chỉ số $j<k$ . Ta có

$\displaystyle B_j=M / M_j=\prod_{\substack{1 \leq \ell \leq k \\ \ell \neq j}} M_{\ell}.$

Nếu có số nguyên tố $p \mid\left(A_j, B_j\right)$ , tồn tại chỉ số $\ell \neq j$ sao cho $p \mid M_{\ell}$ . Vì $M_{\ell} \mid N+\ell$ nên $p \mid N+\ell$ . Nhưng $p\left|A_j\right| N+j$ ; suy ra $p \mid(N+\ell)-(N+j)=(\ell-j)$ , và $1 \leq|\ell-j|<k$ . Do đó $p<k$ , điều này không thể xảy ra do mọi ước nguyên tố của $M$ lớn hơn $k$ .

Bổ đề. Với mỗi số nguyên dương $x$ , ký hiệu $\tau (x)$ là số ước dương của $x$ . Khi đó

$\displaystyle \sum_{\lambda \in[M, 2 M]} \tau\left(B_j \lambda+A_j\right)\leq 4 M(\ln M+1),\quad\forall j<k.$

Chứng minh. Xét một chỉ số $j<k$ . Vì $N+k <M$ nên với mỗi số nguyên $\lambda\in [M,2M]$ , ta có

$\displaystyle B_j \lambda+A_j \leq \frac{1}{M_j}(M \lambda+N+k)<\frac{2 M \lambda}{M_j} \leq \frac{4 M^2}{M_j}<M^2,$

suy ra

$\displaystyle \tau\left(B_j \lambda+A_j\right) \leq 2 \sum_{\substack{d \mid B_j \lambda+A_j \\ d \leq M}} 1.$

Do đó

$\displaystyle \sum_{\lambda \in[M, 2 M]} \tau\left(B_j \lambda+A_j\right)$

$\displaystyle \leq 2 \sum_{\lambda \in[M, 2 M]} \sum_{\substack{d \mid B_j \lambda+A_j \\ d \leq M}} 1 = 2 \sum_{d \leq M} \sum_{\substack{\lambda \in[M, 2 M] \\ B_j \lambda+A_j \equiv 0 \\ (\bmod d)}} 1$

$\leq 2 \sum_{d \leq M}\left(\left\lfloor\left.\frac{M}{d} \right\rvert\,+1\right) \leq 4 M \sum_{d \leq M} \frac{1}{d}\right. \leq 4 M(\ln M+1) .$ $\Box$

Continue reading →

IMO 2021: Problems and results

Kì thi Olympic Toán học Quốc tế lần thứ 62 (IMO 2021) diễn ra từ 14/7 đến 24/7. Do dịch Covid nên kì thi được tổ chức online, nước chủ nhà là Nga.

I) Danh sách đội tuyển Việt Nam

Trưởng đoàn là thầy Lê Anh Vinh, Phó trưởng đoàn là thầy Lê Bá Khánh Trình.

Dưới đây là danh sách 6 học sinh:

1) Phan Hữu An, THPT Chuyên KHTN

2) Trương Tuấn Nghĩa, THPT Chuyên KHTN

3) Đỗ Bách Khoa, THPT Chuyên Hà Nội – Amsterdam

4) Đinh Vũ Tùng Lâm, THPT Chuyên KHTN

5) Phan Huỳnh Tuấn Kiệt, THPT Chuyên Lê Hồng Phong, TpHCM

6) Vũ Ngọc Bình, THPT Chuyên Vĩnh Phúc

II) Đề thi – Đáp án

Download đề thi IMO 2021

Download đáp án IMO 2021

Đề thi năm nay rất khó, đặc biệt là bài 2 và bài 3. Bài 2 quá khó đối với một bài 2 thông thường ở IMO.

III) Kết quả

Ban tổ chức IMO 2021 quyết định trao 52 HCV cho các thí sinh có điểm $\geq 24,$ trao 103 HCB cho các thí sinh có điểm $\geq 19,$ và 148 HCĐ cho các thí sinh có điểm $\geq 12.$

Đội ta được 1 HCV, 2 HCB và 3 HCĐ. Chúc mừng đội tuyển Việt Nam!

HCV duy nhất lần này thuộc về em Đỗ Bách Khoa, học sinh lớp 12 Toán 1 trường THPT Chuyên Hà Nội – Amsterdam. Với điểm 35/42, Khoa lọt vào top 12 thí sinh có điểm cao nhất của IMO 2021.

Vậy là Ams có HCV IMO đầu tiên trong lịch sử! Trong lịch sử hơn 60 năm của IMO, Khoa cũng là học sinh đầu tiên của đội tuyển Hà Nội được HCV.

Chỉ có đúng một thí sinh đạt 42/42 ở IMO 2021, đó là một học sinh đến từ Trung Quốc.

Nhìn hai cột P2 và P3 mới thấy Khoa hay thế nào.

Tính tổng điểm thì lần này đội ta đứng thứ 14.

Đội Trung Quốc xếp thứ nhất với 208 điểm

IMO 2022 sẽ được tổ chức ở Nauy.

Square roots are linearly independent

Trong bài này tôi giới thiệu nhiều lời giải cho bài toán quan trọng sau:

Bài toán. Cho $a_1,\ldots,a_k$ là các số nguyên không đồng thời bằng $0$ . Chứng minh rằng nếu $n_1,$ $n_2,\ldots,$ $n_k$ là các số nguyên dương đôi một khác nhau và không có ước chính phương lớn hơn $1$ thì $\sum a_i\sqrt{n_i}\not=0$ .

Lời giải 1. Ta sẽ chứng minh bằng quy nạp theo $N$ , số ước nguyên tố của $\prod n_i$ , khẳng định: Tồn tại tổng $S'=\sum b_i\sqrt{m_i}$ sao cho $SS'$ là số nguyên khác $0$ , ở đây $m_i$ là các số nguyên dương đôi một khác nhau và không có ước chính phương khác $1$ , tập các ước nguyên tố của $\prod m_i$ là tập con của tập các ước nguyên tố của $\prod n_i$ , $b_i$ là các số nguyên, và $S=\sum a_i\sqrt{n_i}$ . Từ đó suy ra $S\not=0$ .

Với $N=0$ ta chọn $S'=1$ .

Với $N=1$ ta chọn $S'=\sqrt{p_1}$ khi $S=a_1\sqrt{p_1}$ , chọn $S'=-a_1\sqrt{p_1}+a_2$ nếu $S=a_1\sqrt{p_1}+a_2$ .

Continue reading →

A proof of Pick’s theorem

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. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ 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. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.

Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.

Định lí 1. Trong mặt phẳng tọa độ $Oxy$ , cho tam giác $ABC.$ Khi đó diện tích của tam giác $ABC$ bằng $\displaystyle \frac{1}{2}\left|(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\right|.$ Nói riêng, với mỗi hai điểm $M$ và $N$ ta có diện tích của tam giác $OMN$ bằng $\dfrac{1}{2}\mid x_My_N-y_Mx_N\mid.$

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

Chứng minh. Giả sử $TAB$ là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem $T$ trùng với gốc tọa độ $O.$ Ta cần chứng minh $\mid x_1y_2-x_2y_1\mid =1,$ với $(x_1;y_1)$ và $(x_2;y_2)$ lần lượt là tọa độ của $A$ và $B.$

Gọi $K$ là điểm sao cho $OAKB$ là hình bình hành. Giả sử $M$ là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho $M$ khác các đỉnh. Khi đó $M$ thuộc tam giác $ABK$ và điểm $N$ đối xứng với $M$ qua tâm hình bình hành là điểm nguyên thuộc tam giác $OAB$ nhưng khác các đỉnh, không thể xảy ra điều này do $OAB$ là một tam giác cơ bản. Như vậy hình bình hành $OAKB$ không chứa điểm nguyên nào khác bốn đỉnh của nó.

Giả sử $P$ là một điểm nguyên bất kỳ. Vì $\overrightarrow{OA}$ và $\overrightarrow{OB}$ là hai vector không cùng phương nên tồn tại cặp số thực $(\alpha,\beta)$ để $\overrightarrow{OP}=\alpha \overrightarrow{OA}+\beta \overrightarrow{OB}.$ Gọi $P'$ là điểm xác định bởi $\overrightarrow{OP'}=\{\alpha\} \overrightarrow{OA}+\{\beta\} \overrightarrow{OB}.$ Vì $\{\alpha\}$ và $\{\beta\}$ thuộc $[0;1)$ nên $P'$ thuộc hình bình hành $OAKB$ , nhưng $P'$ lại là một điểm nguyên, suy ra $P'$ phải là một trong bốn đỉnh của hình bình hành. Dễ thấy $P'\equiv O$ và do đó $\alpha$ và $\beta$ là hai số nguyên.

Gọi $\overrightarrow{i}$ và $\overrightarrow{j}$ lần lượt là các vector đơn vị đặt trên $Ox$ và $Oy$ . Khi đó theo lập luận trên, tồn tại các cặp số nguyên $(u,v)$ và $(u',v')$ để $\overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB}$ và $\overrightarrow{j}=u' \overrightarrow{OA}+v' \overrightarrow{OB}.$ Từ hai đẳng thức này ta có $\begin{cases} 1=ux_1+vx_2\\ 0=uy_1+vy_2\end{cases}$ và $\begin{cases}0=u'x_1+v'x_2\\ 1=u'y_1+v'y_2,\end{cases}$ suy ra $\displaystyle u=\frac{y_2}{D},v=-\frac{y_1}{D},u'=-\frac{x_2}{D}$ và $\displaystyle v'=\frac{x_1}{D},$ trong đó $D=x_1y_2-x_2y_1\not =0$ do $O,A$ và $B$ không thẳng hàng. Vì $u,$ $v,$ $u'$ và $v'$ là các số nguyên nên $x_1,x_2,y_1$ và $y_2$ đều là bội của $D$ , do đó $D^2\mid D$ và bởi thế, $D=\pm 1.$

Đị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. 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.$

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$ , suy ra $N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2$ . Để ý thêm $S_P=\dfrac{1}{2}N$ , ta có điều phải chứng minh.