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.

IMO 2024: Problems and results

Ngày thi thứ nhất (16/7/2024)

Bài 1. https://artofproblemsolving.com/community/c6h3358923

Tìm tất cả các số thực $\alpha$ sao cho với mỗi số nguyên dương $n$ , số

$[\alpha]+[2\alpha]+\cdots+[n\alpha]$

chia hết cho $n$ .

Bài 2. https://artofproblemsolving.com/community/c6h3358926

Tìm tất cả các cặp số nguyên dương $(a,b)$ sao cho tồn tại các số nguyên dương $g$ và $N$ thỏa mãn

$\gcd (a^n+b,b^n+a)=g$

với mọi số nguyên $n\geq N$ .

Bài 3. https://artofproblemsolving.com/community/c6h3358932

Cho dãy vô hạn các số nguyên dương $(a_n)_{n\geq 1}$ và số nguyên dương $N$ . Giả sử với mọi số nguyên $n>N$ , $a_n$ bằng số lần xuất hiện của $a_{n-1}$ trong dãy số $a_1$ , $a_2$ , $\ldots$ , $a_{n-1}$ . Chứng minh rằng một trong hai dãy số $(a_{2n-1})_{n\geq 1}$ và $(a_{2n})_{n\geq 1}$ là tuần hoàn kể từ lúc nào đó.

Ngày thi thứ hai (17/7/2024)

Bài 4. https://artofproblemsolving.com/community/c6h3359767

Cho $ABC$ là một tam giác với $AB < AC < BC$ . Gọi tâm đường tròn nội tiếp và đường tròn nội tiếp của tam giác $ABC$ lần lượt là $I$ và $\omega$ . Gọi $X$ là điểm trên đường thẳng $BC$ , khác $C$ , sao cho đường thẳng qua $X$ song song với $AC$ tiếp xúc với $\omega$ . Tương tự, gọi $Y$ là điểm trên đường thẳng $BC$ , khác $B$ , sao cho đường thẳng qua $Y$ song song với $AB$ tiếp xúc với $\omega$ . Đường thẳng $AI$ cắt lại đường tròn ngoại tiếp tam giác $ABC$ tại $P$ . Gọi $K$ và $L$ lần lượt là trung điểm của $AC$ và $AB$ . Chứng minh rằng $\angle KIL + \angle YPX = 180^{\circ}$ .

Bài 5. https://artofproblemsolving.com/community/c6h3359777

Ốc sên Turbo chơi trò chơi sau trên một bảng ô vuông cỡ $2024\times 2023$ . Trong $2022$ ô vuông con nào đó, có các con quỷ nấp ở đó. Ban đầu, Turbo không biết ô nào có quỷ, nhưng nó biết rằng trên mỗi hàng có đúng một con quỷ, trừ hàng đầu tiên và hàng cuối cùng, và trên mỗi cột có không quá một con quỷ.

Turbo thực hiện một dãy các phép thử để tìm cách đi từ hàng đầu đến hàng cuối của bảng. Tại mỗi lần thử, nó được quyền chọn một ô bất kỳ trên hàng đầu để xuất phát, sau đó liên tục di chuyển giữa các ô, mỗi bước từ một ô sang một ô có chung cạnh với ô mà nó đang đứng (nó được phép đến các ô đã từng đi qua). Nếu nó tới một ô có quỷ thì lần thử này dừng lại và nó được đưa trở lại hàng đầu để thực hiện một lần thử khác. Những con quỷ không di chuyển, và Turbo nhớ mỗi ô mà nó ghé qua có quỷ hay không. Nếu nó tới được một ô bất kỳ trên hàng cuối thì trò chơi kết thúc.

Xác định giá trị nhỏ nhất của $n$ sao cho Turbo luôn có chiến lược đảm bảo tới được hàng cuối cùng sau không quá $n$ lần thử, cho dù các con quỷ có nấp ở đâu.

Bài 6. https://artofproblemsolving.com/community/c6h3359771

Một hàm số $f:\mathbb{Q}\to\mathbb{Q}$ được gọi là đẹp nếu với mỗi số hữu tỷ $x$ và $y$ , $f(x+f(y))=f(x)+y$ hoặc $f(f(x)+y)=x+f(y)$ . Chứng minh rằng tồn tại số nguyên $c$ sao cho với mọi hàm số đẹp $f$ , có không quá $c$ số hữu tỷ có dạng $f(r)+f(-r)$ , với số hữu tỷ $r$ nào đó. Tìm giá trị nhỏ nhất của các số $c$ có tính chất này.

Ban tổ chức quyết định điểm xếp giải như sau:

HCV: $\geq 29$ , HCB: $\geq 22$ , HCĐ: $\geq 16$ .

Đội tuyển Việt Nam được 2 HCB và 3 HCĐ. Đội đứng thứ 33 về tổng điểm.

Top 10 đội có điểm cao nhất. Đội tuyển Trung Quốc đứng thứ hai, sau nhiều năm đứng thứ nhất.

Top 10 thí sinh có điểm cao nhất. Haojia Shi lần thứ hai đạt 42/42 điểm. 🙂

Nguồn ảnh: https://www.imo-official.org/

Chessboard comeback

Trưa nay tôi được hỏi câu V trong đề thi tuyển sinh vào lớp 10 Chuyên toán năm học 2024-2025 của Hà Nội. Trong bài này tôi sẽ phát biểu bài toán tổng quát và giới thiệu một lời giải của bài toán đó.

Bài toán. Cho một số nguyên $n$ lớn hơn $1$ và một bảng ô vuông cỡ $n\times n$ . Ban đầu một số ô vuông của bảng được tô màu đỏ. Sau đó mỗi giây, các ô vuông có chung cạnh với ít nhất hai ô đỏ sẽ được tô đỏ. Hỏi ban đầu cần tô ít nhất bao nhiêu ô vuông để sau một thời gian, tất cả các ô của bảng đều được tô đỏ?

Lời giải. Cần tô màu ít nhất $n$ ô để sau một thời gian, tất cả các ô của bảng đều được tô đỏ.

Mỗi ô vuông con được xem là có cạnh $1$ . Gọi $k$ là số ô được tô đỏ ban đầu, và ở mỗi thời điểm gọi $S$ là tổng chu vi của các vùng được tô đỏ. Ta thấy ban đầu $S\leq 4k$ và nếu tất cả các ô của bảng mang màu đỏ thì $S=4n$ . Để ý rằng sau mỗi giây $S$ không tăng. Vì thế, nếu sau một thời gian các ô đều mang màu đỏ thì $4k\geq 4n$ , suy ra $k\geq n$ .

Bây giờ nếu lúc đầu tô $n$ ô dọc theo một đường chéo chính của bảng thì sau một thời gian, tất cả các ô của bảng đều được tô đỏ. $\Box$

The degree of a vertex

Bài này là phần tiếp theo của bài https://nttuan.org/2023/09/01/graph02/

Cho đồ thị $\displaystyle G=(V,E).$ Bậc của một đỉnh $\displaystyle v\in G,$ ký hiệu $\displaystyle \deg_G(v)$ hoặc $\displaystyle \deg (v),$ là số đỉnh của $\displaystyle G$ kề với $\displaystyle v.$ Đỉnh có bậc bằng $\displaystyle 0$ được gọi là đỉnh cô lập. Đỉnh có bậc bằng $1$ được gọi là lá. Nếu mọi đỉnh của $\displaystyle G$ đều có bậc $\displaystyle k$ thì ta nói $\displaystyle G$ là $\displaystyle k-$ đều.

Định lý 1. Trong mỗi đồ thị có cấp lớn hơn $\displaystyle 1$ , tồn tại ít nhất hai đỉnh có cùng bậc.

Chứng minh. Gọi $\displaystyle n$ là cấp của đồ thị. Bậc của mỗi đỉnh của đồ thị là một số tự nhiên bé hơn $\displaystyle n$ . Vì vậy, nếu các đỉnh của đồ thị có bậc đôi một khác nhau thì có đỉnh cô lập và có đỉnh kề với mọi đỉnh khác, vô lý. $\Box$

Định lý 2. Với mỗi đồ thị $\displaystyle G=(V,E),$ ta có

$\displaystyle \displaystyle \sum_{v\in V}\deg (v)=2\mid E\mid.$

Chứng minh. Khi ta cộng tất cả bậc của các đỉnh, ta đã đếm mỗi cạnh đúng hai lần, một cho mỗi đầu mút của nó. $\Box$

Hệ quả. Số đỉnh bậc lẻ trong một đồ thị là số chẵn.

Ví dụ 1. Có đồ thị với dãy bậc của đỉnh như sau hay không?

(a) $\displaystyle 3,2,2,2.$

(b) $\displaystyle 3,3,2,2.$

Hướng dẫn. Ý đầu là không vì tổng bậc phải chẵn, ý thứ hai là có. Ý thứ ba là không, vì nếu có thì khi xét hai đỉnh bậc $\displaystyle 4,$ có ít nhất $\displaystyle 6$ cạnh đến các đỉnh bậc $\displaystyle 1,$ vô lý. $\Box$

Vào năm 1960, Paul Erdos và Tibor Gallai đã tìm được kết quả sau:

Định lý 3 (Erdos-Gallai). Dãy số nguyên không âm $\displaystyle d_1\geq d_2\geq\ldots \geq d_n$ là dãy bậc của một đồ thị trên $\displaystyle n$ đỉnh khi và chỉ khi $\displaystyle \sum d_i$ chẵn và

$\displaystyle \sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min\{d_i,k\},\quad \forall k=\overline{1,n}.$

Ví dụ 2. Cho một tập hợp $\displaystyle S$ gồm $\displaystyle 100$ điểm trong mặt phẳng sao cho khoảng cách giữa hai điểm bất kỳ trong $\displaystyle S$ không bé hơn $\displaystyle 1.$ Chứng minh rằng có không nhiều hơn $\displaystyle 300$ cặp điểm (không kể thứ tự) mà khoảng cách giữa hai điểm trong mỗi cặp bằng $\displaystyle 1.$

Hướng dẫn. Xét đồ thị $\displaystyle G$ trên $\displaystyle S$ được xác định như sau: Tập con $\displaystyle \{A,B\}$ của $\displaystyle S$ là một cạnh của $\displaystyle G$ khi và chỉ khi $\displaystyle AB=1.$ Vì $\displaystyle \deg (v)\leq 6$ với mọi $\displaystyle v\in S$ , nên $\displaystyle \mid E(G)\mid \leq 1/2\times 6\times 100=300$ . $\Box$

Ví dụ 3. Cho một lớp học có số học sinh là số chẵn. Chứng minh rằng tồn tại hai học sinh trong lớp có số người quen chung trong lớp là số chẵn.

Lời giải. Xét đồ thị $\displaystyle G$ trên tập hợp $\displaystyle V$ các học sinh trong lớp được xác định như sau: với hai đỉnh $\displaystyle a$ và $\displaystyle b$ của $\displaystyle G,$ có một cạnh nối $\displaystyle a$ và $\displaystyle b$ khi $\displaystyle a$ và $\displaystyle b$ quen nhau. Giả sử ngược lại rằng với mỗi $\displaystyle a$ và $\displaystyle b$ phân biệt thuộc $\displaystyle V,$ $\displaystyle \mid N(a)\cap N(b)\mid$ là số lẻ. Nói riêng, mỗi hai đỉnh có ít nhất một láng giềng chung.

Nhận xét. Mọi đỉnh của $\displaystyle G$ đều có bậc chẵn.

Chứng minh. Xét một đỉnh $\displaystyle x$ bất kỳ và xem $\displaystyle N(x)$ như đồ thị con cảm sinh của $\displaystyle G.$ Ta thấy $\displaystyle \sum_{y\in N(x)}\deg_{N(x)}(y)$ là số chẵn và mỗi số hạng là lẻ, suy ra $\mid N(x)\mid$ là số chẵn. $\Box$

Bây giờ cố định một đỉnh $\displaystyle x$ bất kỳ của $\displaystyle G.$ Đặt $\displaystyle X=V\setminus (N(x)\cup \{x\}).$ Khi đó $\displaystyle X$ có số phần tử lẻ. Ta quan tâm đến số $\displaystyle \alpha$ các cạnh có một đầu mút thuộc $\displaystyle X$ đầu mút kia thuộc $\displaystyle N(x)$ theo hai cách. Nếu chọn đầu mút thuộc $\displaystyle X$ trước thì ta thấy $\displaystyle \alpha$ là số lẻ, trong khi nếu chọn đầu mút thuộc $\displaystyle N(x)$ trước thì ta thấy $\displaystyle \alpha$ là số chẵn (theo nhận xét), vô lý. $\Box$

Continue reading →