Tag: IMO 2021

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 “The number of prime factors of a natural number” →

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!

Kết quả của đội 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.