IMO Shortlist 2022: Number theory

N1. Một số nguyên dương được gọi là số Na Uy nếu nó có ba ước dương phân biệt có tổng bằng $2022$ . Xác định số Na Uy nhỏ nhất.

N2. Tìm tất cả các số nguyên dương $n>2$ sao cho

$\displaystyle n! \mid \prod_{ p<q\le n,\quad p,q\in\mathbb{P}} (p+q).$

N3. Cho $a > 1$ là một số nguyên dương và $d > 1$ là một số nguyên dương nguyên tố cùng nhau với $a$ . Đặt $x_1=1$ và với $k\geq 1$ , $x_{k+1} = x_k + d$ nếu không chia hết $x_k$ , $=x_k/a$ nếu $a$ chia hết $x_k$ . Tìm, theo $a$ và $d$ , số nguyên dương $n$ lớn nhất mà tồn tại chỉ số $k$ sao cho $x_k$ chia hết cho $a^n$ .

N4. Tìm tất cả các bộ ba số nguyên dương $(a,b,p)$ sao cho $p$ là số nguyên tố và $a^p=b!+p.$

(IMO2022/5)

N5. Đối với mỗi $i\in [9]$ và $T\in\mathbb{N}^*$ , ký hiệu $d_i(T)$ là số lần chữ số $i$ xuất hiện khi tất cả các bội của $1829$ trong $[T]$ được viết ra theo cơ số $10$ . Chứng minh rằng có vô số $T\in\mathbb{N}^*$ sao cho có đúng hai giá trị phân biệt trong các số $d_1(T)$ , $d_2(T)$ , $\dots$ , $d_9(T)$ .

N6. Cho $Q$ là một tập hợp không nhất thiết hữu hạn các số nguyên tố. Đối với một số nguyên dương $n$ , xét phân tích ra thừa số nguyên tố của nó: gọi $p(n)$ là tổng của tất cả các số mũ và $q(n)$ là tổng của các số mũ tương ứng với các số nguyên tố trong $Q$ . Số nguyên dương $n$ được gọi là đặc biệt nếu $p(n)+p(n+1)$ và $q(n)+q(n+1)$ đều là số nguyên chẵn. Chứng minh rằng tồn tại một hằng số $c>0$ không phụ thuộc $Q$ sao cho với mọi số nguyên dương $N>100$ , số các số nguyên đặc biệt trong $[N]$ ít nhất là $cN$ .

N7. Gọi $k$ là một số nguyên dương và $S$ là một tập hữu hạn các số nguyên tố lẻ. Chứng minh rằng có nhiều nhất một cách (sai khác phép quay và đối xứng) để đặt các phần tử của $S$ xung quanh một đường tròn sao cho tích của hai số cạnh nhau bất kỳ có dạng $x^2+x+k$ với một số nguyên dương $x$ .

(IMO2022/3)

N8. Chứng minh rằng với mỗi số nguyên dương $n$ , số $5^n-3^n$ không chia hết cho số $2^n+65$ .

—

Các phần khác đã được đăng ở

Đại số: https://nttuan.org/2024/05/06/isl2022-algebra/

Hình học: https://nttuan.org/2023/09/08/isl2022-geometry/

Tổ hợp: https://nttuan.org/2023/09/29/isl2022-combinatorics/

Bản pdf của IMO SL từ 2014 đến 2021: https://nttuan.org/2023/07/02/isl/

Sau khi sửa một vài chỗ, bản pdf của IMO SL 2022 sẽ được đăng trong link trên.

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.

Convex function

Để tiện theo dõi, các bạn đọc lại bài sau

Convex set

Cho $C$ là một đoạn, khoảng hoặc nửa khoảng không nhất thiết bị chặn.

Một hàm số $f:C\to\mathbb{R}$ được gọi là lồi trên $C$ nếu $f((1-\lambda)x+\lambda y)\leq (1-\lambda)f(x)+\lambda f(y)$ với mọi $x,y\in C$ và mọi $\lambda\in [0;1].$

Như vậy $f$ là lồi nếu mọi đoạn có các đầu mút thuộc đồ thị đều không nằm dưới đồ thị.

Một hàm số $f:C\to\mathbb{R}$ được gọi là lồi nghiêm ngặt trên $C$ nếu $f((1-\lambda)x+\lambda y)< (1-\lambda)f(x)+\lambda f(y)$ với mọi $x,y\in C$ và mọi $\lambda\in [0;1]$ thỏa mãn $x\not=y$ và $0<\lambda<1.$

Hàm số $f$ được gọi là lõm (lõm nghiêm ngặt) nếu hàm $-f$ lồi (lồi nghiêm ngặt).

Hàm lồi nghiêm ngặt là hàm lồi, ngược lại nói chung không đúng. Các hàm số $y=ax+b,y=\mid x\mid$ và $y=x^2$ đều lồi trên $\mathbb{R}.$ Hàm cuối cùng là hàm lồi nghiêm ngặt trên $\mathbb{R}.$

Định lí 1. Cho hàm số $f:[a;b]\to\mathbb{R}$ liên tục trên $[a;b]$ và lồi trên $(a;b).$ Khi đó $f$ lồi trên $[a;b].$

Định lí 2. Hàm số $f:C\to\mathbb{R}$ lồi trên $C$ nếu và chỉ nếu tập hợp $\text{epi}\, f=\{(x;y)\in C\times \mathbb{R}\mid f(x)\leq y\}$ là tập hợp lồi. Tập hợp này được gọi là bia của $f.$

Nếu một hàm số lồi trên một khoảng thì nó liên tục trên khoảng đó. Để chứng minh kết quả này ta cần bổ đề sau.

Bổ đề. Cho hàm số $f:C\to\mathbb{R}$ lồi trên $C.$ Khi đó $\displaystyle\frac{f(y)-f(x)}{y-x}\leq \frac{f(z)-f(x)}{z-x}\leq \frac{f(z)-f(y)}{z-y}$ với mọi $x,y,z\in C$ thỏa mãn $x<y<z.$

Định lí 3. Nếu $f:(a;b)\to\mathbb{R}$ lồi trên $(a;b)$ thì $f$ liên tục trên $(a;b).$

Nếu thay miền xác định của $f$ bởi đoạn thì khẳng định không còn đúng. Chẳng hạn hàm số $f:[0;1]\to\mathbb{R}$ xác định bởi $f(x)=\begin{cases}1,\quad x=0\\ 0,\quad 0<x\leq 1\end{cases}$ là hàm số lồi trên $[0;1]$ nhưng không liên tục trên $[0;1].$

Sau đây là tiêu chuẩn lồi với các hàm có đạo hàm cấp hai.

Continue reading →

Convex set

Trong bài này, $\mathbb{R}^1,$ $\mathbb{R}^2$ và $\mathbb{R}^3$ lần lượt là tập các điểm thuộc đường thẳng, mặt phẳng và không gian.

Cho số nguyên dương $d\leq 3.$ Một tập hợp $C\subset \mathbb{R}^d$ được gọi là tập hợp lồi nếu với mỗi hai điểm $A$ và $B$ thuộc $C,$ cả đoạn thẳng $AB$ cũng nằm trong $C.$

Dễ thấy giao của một họ bất kỳ các tập hợp lồi là một tập hợp lồi. Vì thế ta có thể định nghĩa bao lồi của một tập hợp $X\subset \mathbb{R}^d$ là giao của tất cả các tập hợp lồi trong $\mathbb{R}^d$ chứa $X.$ Như vậy bao lồi của một tập hợp là tập hợp lồi nhỏ nhất chứa nó.

Nếu $A$ và $B$ là hai điểm khác nhau thì bao lồi của tập hợp $\{A,B\}$ là đoạn thẳng $AB.$ Nếu $A,B$ và $C$ là ba điểm không thẳng hàng thì bao lồi của tập $\{A,B,C\}$ là tam giác $ABC$ (phần trong và biên).

Dùng tổ hợp lồi ta có một mô tả khác của bao lồi.

Định lí 1. Cho $X$ là một tập hợp con khác rỗng của $\mathbb{R}^2.$ Khi đó điểm $x$ thuộc bao lồi của $X$ khi và chỉ khi tồn tại các điểm $x_1,x_2,\ldots,x_n\in X$ và các số thực không âm $t_1,t_2,\ldots,t_n$ thỏa mãn $\sum t_i=1$ và $x=\sum t_ix_i.$

Biểu diễn $\sum t_ix_i$ như trong định lí trên được gọi là tổ hợp lồi của các điểm $x_1,$ $x_2,$ $\ldots,$ $x_n.$

Với tập hợp hữu hạn trong mặt phẳng ta có kết quả sau, kết quả này được dùng nhiều trong các bài toán thi chọn học sinh giỏi.

Định lí 2. Cho số nguyên $n>2$ và $n$ điểm $A_1,A_2,\ldots,A_n$ trong $\mathbb{R}^2.$ Khi đó bao lồi của tập $\{A_i\}$ là đa giác lồi có tập đỉnh là tập con của tập $\{A_i\}.$

Trong định lí trên một đoạn thẳng được xem là một đa giác lồi với hai đỉnh là các đầu mút.

Định lí Helly là một kết quả cơ bản trong hình học tổ hợp về giao của các tập hợp lồi. Nó được Eduard Helly phát hiện vào năm 1913, nhưng mãi đến năm 1923 ông mới công bố, lúc đó các chứng minh của Radon (1921) và Konig (1922) đã xuất hiện.

Định lí 3 (Helly). Cho số nguyên $n>3$ và $n$ tập hợp lồi $X_1,X_2,\ldots,X_n$ trong $\mathbb{R}^2.$ Khi đó nếu mỗi ba tập trong chúng có giao khác rỗng thì cả $n$ tập có giao khác rỗng.

Chứng minh. Ta chứng minh bằng quy nạp theo $n.$ Đầu tiên ta xét $n=4.$ Giả sử bốn tập hợp lồi $X_1,$ $X_2,$ $X_3$ và $X_4$ trong $\mathbb{R}^2$ có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Lấy bốn điểm $A_1,$ $A_2,$ $A_3$ và $A_4$ sao cho $A_i$ thuộc $\displaystyle \bigcap_{j\not=i}A_j$ với mỗi $i.$

Nếu bốn điểm $A_1,$ $A_2,$ $A_3$ và $A_4$ thẳng hàng theo thứ tự đó thì $A_2$ thuộc cả bốn tập lồi. Nếu bao lồi của $\{A_i\}$ là một tam giác thì điểm còn lại không phải là đỉnh của bao lồi sẽ thuộc cả bốn tập lồi. Nếu bao lồi của $\{A_i\}$ là một tứ giác thì giao điểm của hai đường chéo tứ giác sẽ thuộc cả bốn tập lồi.

Vậy khẳng định đúng với $n=4.$ Bây giờ ta giả sử khẳng định đúng với $n\, (n\geq 4),$ và đi chứng minh nó đúng với $n+1.$ Xét $n+1$ tập hợp lồi $X_1,X_2,\ldots,X_{n+1}$ trong $\mathbb{R}^2$ có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Dùng giả thiết quy nạp cho $n$ tập hợp lồi $X_1\cap X_{n+1},X_2\cap X_{n+1},\ldots,X_n\cap X_{n+1}$ ta có điều cần chứng minh. $\Box$

Một cách tổng quát ta có kết quả sau, chứng minh được thực hiện tương tự như trên.

Cho số nguyên $n>d+1$ và $n$ tập hợp lồi $X_1,X_2,\ldots,X_n$ trong $\mathbb{R}^d.$ Khi đó nếu mỗi $d+1$ tập trong chúng có giao khác rỗng thì cả $n$ tập có giao khác rỗng.