IMO Shortlist 2023: Number theory

Hình học : https://nttuan.org/2024/11/02/isl2023-geometry/

Đại số: https://nttuan.org/2025/01/23/isl2023-algebra/

——

N1. https://artofproblemsolving.com/community/c6h3106752p28097575

Tìm tất cả các hợp số $n$ có tính chất: nếu $d_1, d_2, \ldots, d_k$ là tất cả ước dương của $n$ với $1=d_1<d_2<\cdots<d_k=n$ , thì $d_i$ chia hết $d_{i+1}+d_{i+2}$ với mọi $i$ thỏa mãn $1 \leqslant i \leqslant k-2$ . (IMO2023/1)

N2. https://artofproblemsolving.com/community/c6h3359734p31218394

Tìm tất cả các cặp số nguyên dương $(a,p)$ sao cho $p$ là một số nguyên tố và $p^a+a^4$ là một số chính phương.

N3. https://artofproblemsolving.com/community/c6h3359721p31218370

Với các số nguyên dương $n$ và $k \geq 2$ , gọi $E_k(n)$ là số tự nhiên $r$ lớn nhất sao cho $k^r$ chia hết $n!$ . Chứng minh rằng có vô hạn $n$ để $E_{10}(n) > E_9(n)$ và vô hạn $m$ để $E_{10}(m) < E_9(m)$ .

N4. https://artofproblemsolving.com/community/c6h3359730p31218384

Cho $a_1, \dots, a_n, b_1, \ldots, b_n$ là $2n$ số nguyên dương sao cho $n+1$ tích

$a_1 a_2 a_3 \cdots a_n, b_1 a_2 a_3 \cdots a_n, b_1 b_2 a_3 \cdots a_n, \dots, b_1 b_2 b_3 \cdots, b_n$

tạo thành một cấp số cộng tăng theo thứ tự đó. Tìm số nguyên dương nhỏ nhất có thể là công sai của một cấp số cộng như vậy.

N5. https://artofproblemsolving.com/community/c6h3359746p31218469

Cho $a_1<a_2<a_3<\dots$ là các số nguyên dương sao cho $a_{k+1}\mid 2(a_1+a_2+\dots+a_k)$ với mọi $k\geqslant 1$ . Giả sử rằng với vô hạn số nguyên tố $p$ , tồn tại $k$ để $p$ chia hết $a_k$ . Chwungs minh rằng với mỗi số nguyên dương $n$ , tồn tại $k$ để $n$ chia hết $a_k$ .

N6. https://artofproblemsolving.com/community/c6h3359725p31218376

Một dãy các số nguyên $a_0, a_1,\ldots$ được gọi là tốt nếu $a_0 =0$ , $a_1=1,$ và

$(a_{n+2}-3a_{n+1}+2a_n)(a_{n+2}-4a_{n+1}+3a_n)=0$

với mọi số nguyên $n \geq 0$ . Một số nguyên được gọi là tốt nếu nó thuộc một dãy tốt. Giả sử hai số $m$ và $m+1$ đều tốt, chứng minh rằng $m$ chia hết cho $3,$ và $m/3$ cũng là số tốt.

N7. https://artofproblemsolving.com/community/c6h3359727p31218380

Xét các số nguyên dương $a$ , $b$ , $latex $c$, và $d$ thỏa mãn

$\displaystyle \frac{ab}{a+b}+\frac{cd}{c+d}=\frac{(a+b)(c+d)}{a+b+c+d}.$

Tính tổng $a+b+c+d$ .

N8. https://artofproblemsolving.com/community/c6h3359735p31218397

Tìm tất cả các hàm số $f\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ sao cho

$f^{bf(a)}(a+1)=(a+1)f(b),$

với mọi số nguyên dương $a$ và $b$ . Trong đó $f^k$ là lũy thừa bậc $k$ của $f$ theo phép toán hợp thành.

Kỳ thi Olympic Toán học Quốc tế (IMO)

Kỳ thi Olympic Toán học Quốc tế (IMO) là cuộc thi toán học danh giá nhất dành cho học sinh trung học trên toàn thế giới. IMO được tổ chức lần đầu tiên vào năm 1959 tại Romania, với sự tham gia của 7 quốc gia Đông Âu: Romania, Hungary, Bulgaria, Ba Lan, Tiệp Khắc, Đông Đức và Liên Xô. Ý tưởng tổ chức IMO xuất phát từ mong muốn thúc đẩy sự phát triển của toán học, khuyến khích học sinh tài năng và tạo cơ hội giao lưu học thuật quốc tế. Từ quy mô nhỏ ban đầu, IMO đã phát triển mạnh mẽ, hiện thu hút hơn 100 quốc gia tham gia mỗi năm. Việt Nam bắt đầu tham dự IMO từ năm 1974 và đã đạt được nhiều thành tựu đáng tự hào, với nhiều huy chương vàng, bạc, đồng.

IMO nhằm mục đích phát hiện và nuôi dưỡng tài năng toán học trẻ, khuyến khích tư duy sáng tạo, khả năng giải quyết vấn đề phức tạp và thúc đẩy hợp tác quốc tế trong lĩnh vực giáo dục toán học. Đề thi IMO yêu cầu thí sinh không chỉ nắm vững kiến thức toán học mà còn phải có khả năng tư duy logic, sáng tạo và áp dụng linh hoạt các phương pháp giải bài toán ở trình độ cao. Các bài toán thường không yêu cầu kiến thức vượt quá chương trình trung học, nhưng đòi hỏi sự sâu sắc trong tư duy và khả năng tìm ra các cách tiếp cận độc đáo.

IMO diễn ra trong hai ngày thi, mỗi ngày thí sinh giải 3 bài toán trong 4,5 giờ (tổng cộng 6 bài toán). Đề thi bao gồm các bài toán thuộc bốn phân môn chính của toán học trung học:

– Đại số: Các bài toán về phương trình hàm, bất đẳng thức, đa thức, hoặc dãy số.

– Hình học: Các bài toán về hình học phẳng, thường yêu cầu sử dụng các phương pháp hình học tổng hợp.

– Số học: Các bài toán liên quan đến lý thuyết số cơ sơ cấp, tính chất chia hết, số nguyên tố, hoặc ngôn ngữ đồng dư.

– Tổ hợp: Các bài toán về đếm, xác suất, lý thuyết đồ thị, hoặc các bài toán liên quan đến sắp xếp tổ hợp.

Mỗi bài toán được chấm tối đa 7 điểm, tổng điểm tối đa là 42 điểm. Đề thi được thiết kế để phân loại rõ ràng trình độ của thí sinh, với các bài toán có độ khó tăng dần.

Quy trình ra đề thi IMO được thực hiện rất nghiêm ngặt để đảm bảo tính công bằng và chất lượng. Mỗi quốc gia tham gia IMO được mời gửi các bài toán đề xuất đến Ban tổ chức. Các bài toán này được một ủy ban quốc tế (IMO Problem Selection Committee) xem xét và lựa chọn. Ủy ban này, bao gồm các chuyên gia toán học từ nhiều quốc gia, sẽ đánh giá tính sáng tạo, độ khó, và tính phù hợp của bài toán. Sau đó, các bài toán được chọn sẽ được dịch ra nhiều ngôn ngữ và kiểm tra kỹ lưỡng để tránh sai sót. Các bài toán được giữ bí mật tuyệt đối cho đến ngày thi. Mỗi năm, đề thi được thiết kế để cân bằng giữa các phân môn và đảm bảo có ít nhất một bài toán “dễ” (để hầu hết thí sinh có thể giải), một bài toán “trung bình” và một bài toán “khó” (thách thức các thí sinh xuất sắc nhất).

Quy trình chấm thi IMO được thực hiện công bằng và minh bạch. Sau khi hoàn thành bài thi, các bài làm của thí sinh được trưởng đoàn của quốc gia đó chấm sơ bộ. Sau đó, bài thi được chuyển đến một ban chấm thi quốc tế, nơi các giám khảo sẽ thảo luận và thống nhất điểm số. Nếu có tranh cãi về cách chấm, trưởng đoàn có thể giải thích hoặc bảo vệ cách giải của thí sinh trước ban chấm thi. Mỗi bài toán được chấm theo thang điểm 0-7 dựa trên mức độ hoàn chỉnh và chính xác của lời giải. Tổng điểm của thí sinh quyết định thứ hạng và các giải thưởng (huy chương vàng, bạc, đồng hoặc bằng khen).

Continue reading →

Ramsey numbers

Các bạn đọc lại các bài sau để theo dõi cho dễ:

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

[3] https://nttuan.org/2023/09/01/graph02/

—

Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.

Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau.

Lời giải. Gọi $A$ là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, $A$ sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là $B$ , $C$ , $D$ , mà $A$ cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng $A$ quen cả ba người $B$ , $C$ , và $D$ . Nếu trong $B$ , $C$ , và $D$ có hai người quen nhau, chẳng hạn là $B$ và $C$ thì ba người $A$ , $B$ , và $C$ đôi một quen nhau. Nếu không, $B$ , $C$ , và $D$ đôi một không quen nhau. $\Box$

Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.

Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ $K_6$ trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của $K_6$ bởi hai màu, luôn có $K_3$ mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay $K_6$ bởi $K_n$ với $n<6$ . Kết quả sẽ thay đổi thế nào nếu thay $K_3$ bởi $K_{\alpha}$ ? Ta xét bài toán tổng quát sau:

Bài toán. Cho một số nguyên dương $\alpha$ . Tồn tại hay không số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu, luôn có $K_{\alpha}$ mà các cạnh mang cùng một màu. Số nguyên dương $n$ nhỏ nhất có tính chất này bằng bao nhiêu?

Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được $n$ như một hàm của $\alpha$ trong tình huống tổng quát mà chỉ có thể ước lượng nó.

Định lý 1 (Ramsey). Cho $s$ và $t$ là hai số nguyên lớn hơn $1$ . Khi đó tồn tại số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, $K_n$ có đồ thị con $K_s$ với các cạnh xanh hoặc có đồ thị con $K_t$ với các cạnh đỏ. Nếu ký hiệu $R(s,t)$ là số nguyên dương $n$ nhỏ nhất có tính chất này thì

$R(s,t)\leq R(s,t-1)+R(s-1,t)$

mỗi khi $s$ và $t$ lớn hơn $2$ .

Các số $R(s,t)$ được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết $R(3,3)=6$ . Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số $R(k,k)$ , chúng được gọi là các số Ramsey đối xứng.

Chứng minh. Ta chứng minh bằng quy nạp theo $s$ và $t$ . Lập luận đơn giản ta thu được $R(k,2)$ , $R(2,k)$ đều tồn tại và bằng $k$ với mọi $k>1$ .

Bây giờ giả sử $R(s,t-1)$ và $R(s-1,t)$ đều tồn tại, ở đây $s$ và $t$ là các số nguyên lớn hơn $2$ . Đặt $\alpha=R(s,t-1)+R(s-1,t)$ . Xét một cách tô màu các cạnh của $K_{\alpha}$ bởi một trong hai màu xanh và đỏ. Gọi $v$ là một đỉnh của $K_{\alpha}$ . Mỗi một trong $\alpha-1$ đỉnh còn lại của $K_{\alpha}$ được nối với $v$ bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có $R(s-1,t)$ đỉnh được nối với $v$ bởi cạnh xanh, hoặc có $R(s,t-1)$ đỉnh được nối với $v$ bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem $R(s-1,t)$ đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có $K_{s-1}$ với các cạnh xanh hoặc $K_t$ với các cạnh đỏ. Nếu có $K_t$ với các cạnh đỏ thì ta có điều phải chứng minh, nếu có $K_{s-1}$ với các cạnh xanh thì thêm $v$ vào ta có đồ thị con $K_s$ của $K_{\alpha}$ với các cạnh xanh, và ta cũng có điều cần chứng minh. $\Box$

Định lý 2. Với mỗi số nguyên $k>3$ , ta có $R(k,k)>2^{k/2}$ .

Chứng minh (của Paul Erdos). Xét một số nguyên $n$ thỏa mãn $k\leq n\leq 2^{k/2}$ . Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, sao cho trong $K_n$ không có $K_k$ với các cạnh cùng màu.

Tô màu mỗi cạnh của $K_n$ bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu $\Omega$ là tập tất cả các cách tô màu, và với mỗi biến cố $A$ , xác suất xảy ra $A$ bằng $\mid A\mid /\mid\Omega\mid$ .

Gọi $X$ là biến cố: trong $K_n$ không có $K_k$ với các cạnh cùng màu. Ta cần chứng $\mathbb{P}(X)>0$ . Với mỗi đồ thị con đầy đủ trên $k$ đỉnh của $K_n$ , gọi $Y_{\alpha}$ là biến cố: $\alpha$ có các cạnh cùng màu. Khi đó

$\displaystyle\mathbb{P}(Y_{\alpha})=\frac{\mid Y_{\alpha}\mid }{\mid \Omega\mid}=\frac{2\cdot 2^{C_n^2-C_k^2}}{2^{C_n^2}}=2^{1-C_k^2},$

do đó

$\mathbb{P}(X)=1-\mathbb{P}(\overline{X}) =1-\mathbb{P}\left(\bigcup_{\alpha}Y_{\alpha}\right)\geq 1-\sum_{\alpha}\mathbb{P}(Y_{\alpha})=1-C_n^k2^{1-C_k^2}.$

Mà ta lại có

$\displaystyle C_n^k2^{1-C_k^2}<\frac{n^k}{k!}\cdot 2^{1-C_k^2}\leq \frac{2^{k^2/2}}{k!}\cdot 2^{1-C_k^2}=\frac{2^{1+\frac{k}{2}}}{k!}< 1,$

suy ra $\mathbb{P}(X)>0$ . $\Box$

Bipartite graph

Một đồ thị $G$ được gọi là hai phần (hay lưỡng phân) nếu $V(G)$ có thể phân hoạch thành hai tập con $X$ và $Y$ , sao cho mỗi phần tử của $E(G)$ có một đầu mút trong $X$ và đầu mút còn lại trong $Y$ . Khi đó $X$ và $Y$ được gọi là các phần của đồ thị lưỡng phân. Ta ký hiệu đồ thị lưỡng phân với hai phần $X$ và $Y$ bởi $G[X,Y]$ . Nếu trong $G[X,Y]$ , mọi đỉnh thuộc $X$ được nối với mọi đỉnh của $Y$ thì $G[X,Y]$ được gọi là đồ thị lưỡng phân đầy đủ.

Ví dụ 1. Gọi $X$ và $Y$ lần lượt là tập các cầu thủ bóng đá và tập các câu lạc bộ trong một thành phố. Khi đó ta có đồ thị lưỡng phân $G[X,Y]$ , ở đây $x\in X$ được nối với $y\in Y$ khi và chỉ khi $x$ đã từng chơi cho $y$ .

Ví dụ 2 (Bài toán tối ưu trong đường sắt). Giả sử ta có một lịch trình các chuyến tàu cùng các điểm dừng của chúng, và cần tìm một tập hợp các ga tàu càng nhỏ càng tốt sao cho mọi chuyến tàu ghé thăm ít nhất một trong các ga đã chọn. Bài toán này có thể được mô hình hóa như một bài toán trên đồ thị lưỡng phân có các phần là tập các chuyến tàu và tập các ga tàu, mỗi chuyến tàu nối với ga mà nó sẽ dừng.

Bây giờ chúng tôi sẽ giới thiệu một số kết quả cơ bản về đồ thị hai phần.

Định lý 1. Cho đồ thị lưỡng phân $G[X,Y]$ không có đỉnh cô lập và thỏa mãn $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ). Khi đó $\mid X\mid \leq \mid Y\mid$ . Đẳng thức xảy ra khi và chỉ khi $\deg (x)= \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ).

Chứng minh. Vì $G$ không có đỉnh cô lập nên với mỗi $(x,y)\in X\times Y$ , ta có

$\displaystyle \sum_{y^{\prime}\in N(x)}\frac{1}{\deg (x)}=\sum_{x^{\prime}\in N(y)}\frac{1}{\deg (y)}=1.$

Suy ra

$\displaystyle \mid X\mid =\sum_{x\in X}\sum_{y\in N(x)}\frac{1}{\deg (x)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg x},$

và

$\displaystyle \mid Y\mid =\sum_{y\in Y}\sum_{x\in N(y)}\frac{1}{\deg (y)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg y}.$

Kết hợp với giả thiết $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ) ta có những điều cần chứng minh. $\Box$

Định lý 2. Một đồ thị là lưỡng phân khi và chỉ khi nó không chứa chu trình độ dài lẻ.

Chứng minh. Nếu một đồ thị là lưỡng phân thì dọc theo một chu trình của nó, các đỉnh thuộc hai phần sẽ xuất hiện luân phiên. Vì thế, mỗi chu trình trong đồ thị lưỡng phân phải có độ dài là số chẵn. Bây giờ xét một đồ thị $G$ không chứa chu trình với độ dài là số lẻ. Ta chỉ cần xét tình huống $G$ là một đồ thị liên thông.

Gọi $T$ là một cây bao trùm trong $G$ (nó tồn tại theo [1]), và chọn một đỉnh $r$ làm gốc của cây này. Gọi $C$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn, và $L$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn. Khi đó $V(G)$ được phân hoạch thành hai phần $C$ và $L$ .

Ta sẽ chứng minh $G$ là đồ thị lưỡng phân với các phần là $L$ và $C$ . Xét hai đỉnh kề nhau $x$ và $y$ của $G$ . Nếu $xy\in T$ thì độ dài của $rTx$ và độ dài của $rTy$ khác tính chẵn-lẻ, do đó trong hai đỉnh $x$ , $y$ có một đỉnh thuộc $C$ và đỉnh còn lại thuộc $L$ . Nếu $xy\not \in T$ , từ giả thiết ta thấy chu trình $xTy\cup xy$ có độ dài chẵn. Theo phần chứng minh trước thì mỗi cạnh khác $xy$ thuộc chu trình này có các đầu mút thuộc hai phần khác nhau của phân hoạch, suy ra $x$ và $y$ thuộc hai phần khác nhau của phân hoạch. $\Box$