IMO2021/6

Trong bài này tôi giới thiệu hai lời giải cho bài 6 trong đề thi IMO 2021, lời giải thứ hai có dùng bổ đề Siegel mà tôi đã giới thiệu cách đây rất lâu ở đường dẫn https://nttuan.org/2007/10/21/siegel/. Các bạn có thể tìm các bài toán khác trong đề IMO 2021 ở đây https://nttuan.org/2021/07/25/imo2021/

Bài toán (IMO2021/6). Cho số nguyên $m\ge 2,$ $A$ là một tập hữu hạn các số nguyên và $B_1,$ $B_2,$ …, $B_m$ là các tập con của $A$ . Giả sử rằng với mỗi $k=1,2,...,m$ , tổng các phần tử của $B_k$ là $m^k$ . Chứng minh rằng $A$ có ít nhất $\frac{m}{2}$ phần tử.

Lời giải 1. Đặt $k=|A|$ và giả sử $A = \{a_1,a_2,\ldots,a_k\}$ . Từ giả thiết, với mỗi $i\in [m]$ , ta có $\displaystyle m^i = \sum_{j=1}^{k}b_{i,j}a_{j}\quad (1)$ với các $b_{i,j} \in \{0;1\}$ . Với mỗi $0 \le x \le m^{m}-1$ , biểu diễn $mx$ theo cơ số $m$ và kết hợp với $(1)$ ta được $\displaystyle mx = \sum_{j=1}^{k}c_{j}a_{j},$ trong đó các $c_j$ là số nguyên thỏa mãn $0 \le c_j \le (m-1)m,\quad\forall j\in [k]$ . Vế trái của đẳng thức này nhận đúng $m^{m}$ giá trị, do đó $\displaystyle m^{m} \le [m(m-1)+1]^{k} < m^{2k},$ suy ra $|A|=k>m/2$ . $\Box$

Continue reading →

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