Cho $m$ và $n$ là các số nguyên lớn hơn $1$ . Trong mỗi ô vuông đơn vị của lưới $m\times n$ có một đồng xu với mặt trái hướng lên trên. Một phép toán bao gồm các bước sau.

chọn một hình vuông $2\times 2$ trong lưới;
lật các đồng xu ở ô đơn vị trên cùng bên trái và dưới cùng bên phải;
lật đồng xu ở ô vuông đơn vị trên cùng bên phải hoặc dưới cùng bên trái.

Xác định tất cả các cặp $(m,n)$ sao cho mọi đồng xu đều hiện mặt phải sau một số hữu hạn lần thực hiện phép toán.

C2. https://artofproblemsolving.com/community/c6h3359755p31218537

Xác định số nguyên dương $L$ lớn nhất sao cho tồn tại một dãy các số nguyên dương $a_1,\dots,a_L$ có tính chất: mỗi số hạng của dãy không lớn hơn $2^{2023}$ , và không có các số hạng liên tiếp $a_i,a_{i+1},\dots,a_j$ (ở đây $1\le i\le j\le L$ ) với một cách chọn dấu $s_i,s_{i+1},\dots,s_j\in\{1,-1\}$ để

$s_ia_i+s_{i+1}a_{i+1}+\dots+s_ja_j=0.$

C3. https://artofproblemsolving.com/community/c6h3107350p28104367

Cho $n$ là một số nguyên dương. Một tam giác Nhật Bản gồm $1+2+\cdots+n$ hình tròn được xếp thành một hình tam giác đều sao cho với mỗi $i = 1, 2, ..., n$ , hàng thứ $i$ có đúng $i$ hình tròn và trên hàng đó có đúng một hình tròn được tô màu đỏ. Một đường đi ninja trong một tam giác Nhật Bản là một dãy gồm $n$ hình tròn nhận được bằng cách xuất phát từ hàng trên cùng, đi lần lượt từ một hình tròn xuống một trong hai hình tròn ngay dưới nó, và kết thúc tại hàng dưới cùng. Trong hình vẽ là một tam giác Nhật Bản với $n = 6$ và một đường đi ninja có chứa hai hình tròn màu đỏ.

Như một hàm số của $n$ , tìm giá trị lớn nhất của $k$ sao cho trong mỗi tam giác Nhật Bản luôn có một đường đi ninja chứa ít nhất $k$ hình tròn màu đỏ. (IMO2023/5)

C4. https://artofproblemsolving.com/community/c6h3359724p31218375

Cho $n\geqslant 2$ là một số nguyên dương. Paul có một dải hình chữ nhật cỡ $1\times n^2$ gồm $n^2$ hình vuông đơn vị, trong đó hình vuông thứ $i$ được gắn nhãn $i$ với mọi $1\leqslant i\leqslant n^2$ . Anh ta muốn cắt dải giấy thành nhiều mảnh, trong đó mỗi mảnh bao gồm một số ô vuông đơn vị liên tiếp, sau đó dịch chuyển (không xoay hoặc lật) các mảnh để thu được hình vuông $n\times n$ thỏa mãn tính chất sau: nếu hình vuông đơn vị trong hàng $i$ và cột $j$ được gắn nhãn $a_{ij}$ , thì $a_{ij}-(i+j -1)$ chia hết cho $n$ .

Xác định số mảnh nhỏ nhất mà Paul cần tạo để hoàn thành việc này.

C5. https://artofproblemsolving.com/community/c6h3359765p31218619

Elisa có $latex $2023$ rương kho báu, tất cả đều được mở khóa và trống rỗng lúc đầu. Mỗi ngày, Elisa thêm một viên đá quý mới vào một trong những chiếc rương đã mở khóa mà cô ấy chọn, và sau đó, một cô tiên sẽ hành động theo các quy tắc sau:

nếu có nhiều hơn một rương được mở khóa, cô sẽ khóa một trong số chúng, hoặc
nếu chỉ có một rương được mở khóa, cô sẽ mở khóa tất cả các rương.

Cho rằng quá trình này diễn ra mãi mãi, hãy chứng minh rằng tồn tại một hằng số $C$ với tính chất sau: Elisa có thể đảm bảo rằng chênh lệch giữa số viên ngọc trong hai rương bất kỳ không bao giờ vượt quá $latex $C$, bất kể cô tiên hành động như thế nào.

C6. https://artofproblemsolving.com/community/c6h3359747p31218478

Cho $N$ là một số nguyên dương và xét một lưới $N \times N$ các ô vuông. Đường dẫn xuống bên phải là một dãy các ô lưới sao cho mỗi ô là một ô ở bên phải hoặc một ô bên dưới ô trước đó trong chuỗi. Đường dẫn lên bên phải là một chuỗi các ô lưới sao cho mỗi ô là một ô ở bên phải hoặc một ô phía trên ô trước đó trong chuỗi.

Chứng minh rằng không thể phân chia các ô của lưới $N \times N$ thành ít hơn $N$ vùng sao cho mỗi vùng là một đường dẫn xuống bên phải xuống hoặc một đường dẫn lên bên phải.

Chẳng hạn, lưới $5 \times 5$ có thể phân chia thành $5$ vùng như hình vẽ.

C7. https://artofproblemsolving.com/community/c6h3359751p31218524

Quần đảo Imomi bao gồm $n\geq 2$ hòn đảo. Giữa mỗi cặp đảo khác nhau có một tuyến phà duy nhất chạy theo cả hai hướng và mỗi tuyến phà được điều hành bởi một trong $k$ công ty. Được biết, nếu bất kỳ công ty nào đóng cửa tất cả các tuyến phà của mình thì một du khách, bất kể bắt đầu từ đâu, sẽ không thể ghé thăm tất cả các hòn đảo đúng một lần (đặc biệt là không quay lại hòn đảo mà du khách bắt đầu). Xác định giá trị lớn nhất có thể có của $k$ theo $n$ .

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$

Tag: Mathematical Olympiad

IMO Shortlist 2023: Combinatorics

IMO Shortlist 2023: Number theory

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

Ramsey numbers