IMO 2026, Bài 1
Đề bài
Có 2026 số nguyên lớn hơn 1, không nhất thiết khác nhau, được viết trên bảng. Mỗi bước, Khổng Tử chọn hai số nguyên và ở các vị trí khác nhau trên bảng và thay hai số nguyên đó bằngThere are 2026 integers greater than 1 written on a blackboard, not necessarily different. In a move, Confucius chooses two integers and from different places on the blackboard and replaces these two integers with
Ông cứ thực hiện các bước như vậy chừng nào còn có thể.He continues to make moves while it is possible to do so.
(a) Chứng minh rằng, mặc các cách chọn của Khổng Tử, sau một số hữu hạn các bước, trên bảng có đúng một số lớn hơn 1.(a) Prove that, regardless of the choices of Confucius, after finitely many moves, exactly one integer on the blackboard is greater than 1.
(b) Chứng minh rằng giá trị của không phụ thuộc vào các cách chọn của Khổng Tử.(b) Prove that the value of does not depend on the choices of Confucius.
(Chú ý rằng ký hiệu ước số chung lớn nhất của các số nguyên dương và , và ký hiệu bội số chung nhỏ nhất của và .)(Note that denotes the greatest common divisor of positive integers and , and denotes the least common multiple of and .)
Bước 1. Tìm hiểu đề bài
Đây là bài toán chứng minh. Để khỏi lẫn với năm bước của lời giải, ta gọi mỗi bước của Khổng Tử là một thao tác. Bạn cần chứng minh:This is a prove problem. You must establish:
- câu (a): mọi quá trình thực hiện các thao tác đều dừng lại, và lúc dừng có đúng một số lớn hơn ;part (a): every sequence of moves stops, and when it stops exactly one entry is greater than ;
- câu (b): mọi cách thực hiện từ cùng một bảng ban đầu đều cho cùng một số .part (b): all sequences from the same initial board give the same .
Câu (b) yêu cầu chứng minh, nhưng cách tự nhiên là tìm ra : tính được chỉ từ các số ban đầu thì hiển nhiên không phụ thuộc vào các lựa chọn.Part (b) asks for a proof, but the natural way is to find : if you can compute from the starting numbers alone, it clearly does not depend on the choices.
Những điều kiện cần để ý:The conditions to notice:
- chỉ những số lớn hơn mới được chọn, nên một số đã bằng thì luôn bằng ;only entries greater than can be chosen, so once an entry is , it stays ;
- cụm từ “ở các vị trí khác nhau” cho phép chọn hai số có cùng giá trị, miễn là chúng nằm ở hai vị trí khác nhau;the words “different places” allow two equal values, provided they occupy different positions;
- trên bảng luôn có 2026 số.the board always contains 2026 entries.
Nếu quá trình dừng lại thì có nhiều nhất một số lớn hơn , vì nếu còn hai số như vậy thì vẫn thực hiện được một thao tác nữa. Vậy với câu (a), bạn còn phải chứng minh rằng quá trình thật sự dừng lại và trên bảng không thể còn toàn số .If the process stops, at most one entry can exceed , since two such entries would allow another move. So for part (a), you still need to prove that the process stops and that the board cannot become all s.
Bước 2. Khảo sát rồi dự đoán
Để chứng minh quá trình phải dừng, bạn hãy tìm một đại lượng nhận giá trị nguyên dương và giảm thật sự sau mỗi thao tác. Hai số mới là và một phân số có ở mẫu số; khi nhân chúng, giản ước. Vì vậy, hãy xét tích của hai số mới:To prove that the process stops, look for a positive integer that must decrease at every move. One replacement is the gcd and the other is divided by it, so multiplying them cancels it. Inspect their product:
Hãy kiểm tra hai trường hợp của mẫu số:Test the two possibilities for the denominator:
- hai số có ước chung lớn hơn , chẳng hạn : tích giảm từ xuống ;a common factor greater than , for example : the product drops from to ;
- hai số nguyên tố cùng nhau, chẳng hạn : tích không đổi.a coprime pair, for example : the product stays the same.
Tích chỉ giữ nguyên khi hai số được chọn nguyên tố cùng nhau. Xét kĩ trường hợp này: thao tác tạo ra một số , và số đó không bao giờ được chọn lại. Điều này gợi ý đếm thêm số lượng các số lớn hơn . Số lượng ấy không thể tăng, vì mỗi thao tác thay hai số lớn hơn bằng nhiều nhất hai số lớn hơn , và nó giảm đi khi hai số nguyên tố cùng nhau (chúng thành và ).The product stays unchanged only when the chosen numbers are coprime. Examine that case: it creates a , which can never be chosen again. This suggests also counting the entries greater than . That count cannot increase, since a move replaces two entries greater than by at most two such entries, and it drops by when the two are coprime (they become and ).
Nhận xét: cả tích lẫn số lượng các số lớn hơn đều không tăng. Mỗi thao tác làm giảm ít nhất một trong hai đại lượng này.Neither the product nor the number of entries greater than increases. Every move decreases at least one of them.
Nhận xét trên gợi ý cách chứng minh quá trình dừng lại, nhưng chưa xác định được số cuối cùng. Để so sánh các kết quả cuối cùng có thể xảy ra, bạn hãy tìm thông tin được giữ nguyên qua mọi thao tác.This suggests how to prove termination, but it does not identify the surviving number. To compare different possible endings, look for information that every move preserves.
Quy tắc biến đổi dùng ƯCLN, BCNN và phép chia. Cả ba đều tính được bằng cách so sánh các phân tích ra thừa số nguyên tố, riêng với từng số nguyên tố:The rule uses gcd, lcm and division. All three can be worked out by comparing prime factorisations, one prime at a time:
- ƯCLN lấy số mũ nhỏ hơn;the gcd takes the smaller exponent;
- BCNN lấy số mũ lớn hơn;the lcm takes the larger;
- phép chia thì trừ các số mũ.division subtracts exponents.
Vì vậy, bạn có thể xét riêng từng số nguyên tố. Để dễ thấy điều này, hãy bắt đầu với các số chỉ có một ước nguyên tố, chẳng hạn các lũy thừa của .So you can study each prime separately. To make that easier to see, start with numbers containing only one prime factor, such as powers of .
Ví dụ, và . ƯCLN của chúng là , còn BCNN là , nên thao tác làFor example, and . Their gcd is , and their lcm is , so the move is
Xét các số mũ, ta có . Bạn giữ số mũ nhỏ hơn và lấy số mũ lớn hơn trừ đi số mũ nhỏ hơn. Đây là một phép trừ trong thuật toán Euclid, nên ƯCLN của hai số mũ không đổi. Tiếp tục như vậy, ta đượcOn the exponents, this becomes . You keep the smaller exponent and subtract it from the larger. This is a step of the Euclidean algorithm, which preserves the gcd. Continuing gives
Số mũ khác cuối cùng là , và số cuối cùng là .The final nonzero exponent is , and the final number is .
Dự đoán: số cuối cùng có đúng các thừa số nguyên tố đã xuất hiện trong các số ban đầu. Với mỗi số nguyên tố đó, số mũ của nó trong số cuối cùng bằng ƯCLN của các số mũ tương ứng trong tất cả các số ban đầu.The final number contains exactly the primes that appear initially. For each such prime, its final exponent is the gcd of its exponents in all the starting entries.
Để kiểm tra dự đoán, hãy chọn ví dụ , vì nó có:To test the conjecture, take the example , because it has:
- ba số, nên cặp đầu tiên chọn được theo nhiều cách: đó là cách kiểm tra sự phụ thuộc vào cách chọn;three entries, so different first pairs can be chosen: that tests whether the choices matter;
- hai số nguyên tố, và , để xem quy luật có còn đúng ngoài các lũy thừa của .two primes, and , to test whether the rule extends beyond powers of .
Các số mũ của là , của là . Nếu một số nguyên tố không xuất hiện trong phân tích của một số thì số mũ tương ứng bằng ; các số không ảnh hưởng đến ƯCLN khi danh sách có ít nhất một số dương. Dự đoán cho taThe exponents of are , those of are . An absent prime has exponent ; zeros do not affect a gcd when at least one entry is positive. The conjecture predicts
Cả hai kiểu lựa chọn cặp đầu tiên đều cho kết quả này:Both types of first choice agree:
Các cách thực hiện này phù hợp với dự đoán. Bạn vẫn cần chứng minh dự đoán đúng với mọi thao tác hợp lệ trên toàn bộ bảng.These paths support the conjecture. You still need to prove it for every allowed move on the full board.
Bước 3. Xây dựng lời giải
Nhận xét ở Bước 2 cho ta hai đại lượng không tăng, và mỗi thao tác làm ít nhất một đại lượng giảm. Để có một đại lượng duy nhất giảm sau mọi thao tác, ta cộng chúng. Gọi là tích tất cả các số trên bảng và là số lượng các số lớn hơn . Khi một trong hai đại lượng giảm, đại lượng kia không thể tăng để bù lại, nên giảm thật sự sau mỗi thao tác.The observation in Step 2 gives two quantities that never increase, and every move decreases at least one of them. To get a single quantity that decreases at every move, add them. Let be the product of all entries and the number of entries greater than . When one of the two decreases, the other cannot increase to make up for it, so strictly decreases at every move.
Điều quan trọng ở đây là nguyên dương, vì mọi số trên bảng luôn là số nguyên dương (, ):What matters here is that is a positive integer, since every number on the board is always a positive integer (, ):
- vì là số nguyên nên mỗi lần giảm, nó giảm ít nhất ;being an integer, it drops by at least each time it decreases;
- vì luôn dương nên nó không thể giảm mãi: nếu lúc đầu nó bằng thì có nhiều nhất thao tác.staying positive, it cannot decrease for ever: if it starts at , there are at most moves.
Một đại lượng chỉ thay đổi theo một chiều được gọi là đơn biến; ở đây, đơn biến ta dùng là : nguyên dương và giảm thật sự.A quantity that changes in one direction only is called a monovariant; here the monovariant we use is : a positive integer that strictly decreases.
Việc dừng lại chỉ cho biết trên bảng có nhiều nhất một số lớn hơn . Để có “đúng một”, bạn còn phải loại trừ khả năng bảng còn toàn số . Xét hai số mới:Stopping only tells you that at most one entry greater than remains. For “exactly one”, you must still exclude a board of all s. Look at the two new numbers:
- nếu thì số thứ nhất lớn hơn ;if , the first exceeds ;
- nếu thì số thứ hai là .if , the second is .
Vậy mỗi thao tác luôn để lại ít nhất một số lớn hơn . Cùng với điều đã thấy ở Bước 1, lúc dừng có nhiều nhất một số như vậy, ta có câu (a).So every move leaves at least one entry greater than . Together with what Step 1 showed, that at most one remains when it stops, this gives part (a).
Để xác định số cuối cùng, ta quay lại nhận xét về các số mũ. Trong ví dụ về các lũy thừa, ƯCLN của các số mũ được giữ nguyên. Nếu điều này đúng trên toàn bộ bảng, thì dù chọn cách nào, bảng cuối cùng vẫn mang thông tin này của bảng ban đầu. Vì vậy, hãy kiểm tra quy luật ấy cho từng số nguyên tố.To determine the final number, go back to the observation about exponents. In the prime-power example, the gcd of the exponents stayed the same. If this holds on the whole board, then whichever way you choose, the final board still carries this information from the starting board. So check the pattern for each prime.
Cố định một số nguyên tố là ước của ít nhất một số ban đầu. Gọi số mũ của trong hai số được chọn là và ; không mất tính tổng quát, giả sử . Trong ƯCLN, có số mũ ; trong BCNN, có số mũ . Vì vậy, các số mũ biến đổi theo quy tắcFix a prime that divides at least one starting number. Let its exponents in the two chosen numbers be and ; without loss of generality, . In the gcd, has exponent ; in the lcm, it has exponent . So the exponents change by the rule
Quy tắc này vẫn đúng khi hai số được chọn có thêm các thừa số nguyên tố khác, vì ƯCLN, BCNN và phép chia được tính riêng với từng số nguyên tố.The rule still holds when the chosen numbers have other prime factors too, since gcd, lcm and division work prime by prime.
Trước khi xét ƯCLN của cả danh sách, cần kiểm tra rằng các số mũ không thể đồng thời bằng , để ƯCLN của cả danh sách luôn là một số nguyên dương:Before looking at the gcd of the whole list, check that the exponents cannot all be , so that the gcd of the list is always a positive integer:
- nếu ít nhất một trong hai số mũ được chọn là số dương thì , và tổng hai số mũ mới bằng , nên ít nhất một số mũ mới vẫn dương;if at least one chosen exponent is positive, then and the two new exponents add up to , so at least one of them stays positive;
- nếu cả hai số mũ được chọn bằng thì các số chia hết cho ở những vị trí khác không bị thay đổi.if both chosen exponents are , the numbers divisible by elsewhere are untouched.
Do đó, trên bảng luôn còn một số chia hết cho .So the board always keeps a number divisible by .
Một thao tác chỉ thay đổi hai số mũ, nhưng ta cần thông tin về toàn bộ bảng. Để nối hai việc này, hãy xét các ước chung. Một số nguyên dương là ước của cả khi và chỉ khi nó là ước của cả . Các số mũ khác không đổi, nên các ước chung của cả danh sách cũng không đổi. Vì vậy, ƯCLN của tất cả các số mũ của được giữ nguyên sau mọi thao tác. Một đại lượng được bảo toàn như vậy được gọi là bất biến.A move changes only two exponents, but you need information about the whole board. To bridge the two, look at common divisors. A positive integer divides both if and only if it divides both . The other exponents do not change, so the common divisors of the whole list do not change either. Hence the gcd of all the exponents of stays the same after every move. A quantity preserved like this is called an invariant.
Then chốt: xét riêng từng số nguyên tố: trên các số mũ, mỗi thao tác là một phép trừ trong thuật toán Euclid, với , nên ƯCLN của các số mũ của mỗi số nguyên tố trên cả bảng không bao giờ thay đổi.Look at one prime at a time: on the exponents, a move is one subtraction step of the Euclidean algorithm, with , so the gcd of each prime's exponents over the whole board never changes.
Bất biến này xác định được kết quả. Ở bảng cuối cùng, mọi số khác đều bằng , nên mọi số mũ của ngoài số mũ trong đều bằng , mà thêm các số không làm thay đổi ƯCLN. Do đó, số mũ của trong bằng , tức là bằng ƯCLN của các số mũ tương ứng lúc đầu. Mọi cách chọn đều cho cùng số mũ này.This invariant determines the result. On the final board every entry other than is , so every exponent of other than the one in is , and adding zeros does not change a gcd. So the exponent of in equals , the gcd of the starting exponents. Every way of choosing gives this same exponent.
Để xác định hoàn toàn , còn phải loại trừ thừa số nguyên tố mới. Cả hai số thay thế đều là ước của , nên không có thừa số nguyên tố nào mới xuất hiện. Như vậy, mọi thừa số nguyên tố của và mọi số mũ tương ứng đều được xác định từ bảng ban đầu. Tính duy nhất của phân tích ra thừa số nguyên tố cho ta câu (b).To pin down completely, new primes must be ruled out. Both replacements divide , so no new prime can appear. Every prime factor of and its exponent are therefore determined by the starting board, and unique prime factorisation gives part (b).
Bước 4. Trình bày lời giải
Gọi là tích tất cả các số trên bảng và là số lượng các số lớn hơn . Với một thao tác chọn , đặt . Tích của hai số mới làLet be the product of all entries on the board, and let be the number of entries greater than . In a move using , put . The product of the replacements is
nên trở thành , còn không tăng vì cả hai số bị xóa đều lớn hơn :so becomes , while cannot increase, since both removed entries exceed :
- nếu thì giảm;if , then strictly decreases;
- nếu thì hai số mới là , nên giảm đi .if , the replacements are , so decreases by .
Mọi số trên bảng luôn nguyên dương, vì là ước của . Do đó, số nguyên dương giảm thật sự sau mỗi thao tác. Suy ra quá trình kết thúc sau hữu hạn thao tác.Every number on the board stays a positive integer, since divides . Thus the positive integer strictly decreases at every move, proving that the process terminates.
Hai số mới không thể đồng thời bằng :The two replacements cannot both equal :
- nếu thì số thứ nhất lớn hơn ;for , the first exceeds ;
- nếu thì số thứ hai là .for , the second is .
Vì vậy, trên bảng luôn còn ít nhất một số lớn hơn . Khi quá trình kết thúc, có nhiều nhất một số như vậy, vì nếu còn hai số thì vẫn thực hiện được một thao tác nữa. Vậy câu (a) được chứng minh.Hence at least one entry greater than always remains. At termination there is at most one, since any two would allow another move. This proves (a).
Cố định một số nguyên tố là ước của ít nhất một số ban đầu. Giả sử các số mũ của trong hai số được chọn là , với . Khi đó, trong ƯCLN và BCNN của chúng, các số mũ tương ứng là và . Vì vậy, các số mũ trong hai số mới là . Trên bảng luôn còn một số chia hết cho : khi ít nhất một trong hai số mũ được chọn là số dương, còn nếu cả hai bằng thì các số chia hết cho ở những vị trí khác không bị thay đổi.Fix a prime appearing initially. If its exponents in the chosen entries are , their gcd and lcm have exponents and , respectively. The replacement exponents are therefore . This preserves the presence of on the board: whenever either selected exponent is positive, and if both are , the entries divisible by elsewhere are untouched.
Gọi là ƯCLN của tất cả 2026 số mũ của trên bảng, kể cả các số mũ bằng . Một số nguyên dương là ước của cả khi và chỉ khi nó là ước của cả . Các số mũ còn lại không đổi, nên là một bất biến.Let be the gcd of all 2026 exponents of on the board, including zero exponents. A positive integer divides both if and only if it divides both . All other exponents are unchanged, so is invariant.
Khi quá trình kết thúc, nếu số mũ của trong là , thì danh sách các số mũ gồm và 2025 số . Do đó,At termination, if the exponent of in is , the exponent list consists of and 2025 zeros. Hence
Như vậy, bảng ban đầu xác định số mũ trong của từng thừa số nguyên tố xuất hiện lúc đầu. Không thể có thừa số nguyên tố mới, vì cả hai số thay thế đều là ước của . Theo tính duy nhất của phân tích ra thừa số nguyên tố,Thus the exponent of each initially present prime in is determined by the starting board. No other prime can appear, since both replacements divide . By unique prime factorisation,
trong đó tích lấy theo các số nguyên tố xuất hiện lúc đầu và là ƯCLN của các số mũ của trong các số ban đầu. Vậy không phụ thuộc vào các thao tác, và câu (b) được chứng minh.where the product runs over the primes present initially and is the gcd of the exponents of in the starting entries. So does not depend on the moves, proving (b).
Bước 5. Nhìn lại
Bài này dùng hai phương pháp, mỗi phương pháp một việc:This problem uses two methods, each with its own job:
- đơn biến chứng minh quá trình dừng;the monovariant proves that the process stops;
- bất biến xác định số mũ của mỗi số nguyên tố trong , nên không phụ thuộc cách chọn.the invariant fixes the exponent of each prime in , so does not depend on the choices.
Mấu chốt là áp dụng phương pháp bất biến sau khi chuyển sang xét các số mũ của từng thừa số nguyên tố; khi đó, mỗi thao tác trở thành một phép trừ trong thuật toán Euclid.The crux is the method of invariants applied after changing to prime exponents, where the move becomes a subtraction step of the Euclidean algorithm.
ƯCLN và BCNN của các số trên bảng có thể thay đổi, nên theo dõi trực tiếp chúng không cho ta bất biến cần tìm. Cách tính quen thuộc thông qua phân tích ra thừa số nguyên tố gợi ý một cách biểu diễn thích hợp hơn. Phép trừ các số mũ giúp ta nhận ra một ƯCLN được giữ nguyên.The gcd and lcm of the board entries need not stay fixed, so tracking them would not give the required invariant. Their familiar calculation through prime factorisation suggests a better representation. The subtraction of exponents then reveals a gcd that is preserved.
Phần đơn biến cho bạn một bài học khác. Nếu đại lượng nguyên bạn thử dùng có lúc giữ nguyên, hãy xét đúng những trường hợp đó. Trong bài này, chúng tạo ra một số không bao giờ thay đổi nữa. Điều đó gợi ý tìm thêm một đại lượng nguyên không âm, không bao giờ tăng, và giảm mỗi khi đại lượng thứ nhất giữ nguyên. Khi đó tổng hai đại lượng giảm thật sự.The monovariant part teaches a separate lesson. If a proposed integer measure sometimes stays unchanged, examine exactly those cases. Here, they create a permanent . That suggests a second nonnegative, nonincreasing integer measure that decreases whenever the first does not. Their sum then strictly decreases.
Dùng lại khi: bạn cần chứng minh:Reuse this when you must prove:
- một quá trình dừng: tìm một đơn biến, một đại lượng nguyên dương giảm thật sự sau mỗi thao tác;that a process stops: find a monovariant, a positive integer that strictly decreases at every move;
- kết quả không phụ thuộc cách chọn: tìm một bất biến, rồi chỉ ra giá trị cuối của nó xác định kết quả.that a result does not depend on the choices: find an invariant, then show that its final value determines the result.
Khi thao tác dùng ƯCLN, BCNN và phép chia, hãy xét số mũ của từng số nguyên tố và để ý phép trừ của thuật toán Euclid.When a move uses gcd, lcm and quotients, look at the exponents of each prime and watch for the subtraction of the Euclidean algorithm.
Lời giải cũng đúng với một bảng ban đầu có hữu hạn số nguyên lớn hơn , miễn là có ít nhất một số. vẫn là số nguyên dương và là số nguyên không âm, còn lập luận về ước chung áp dụng được cho mọi danh sách hữu hạn các số mũ. Con số cụ thể không đóng vai trò thiết yếu.The proof also works for any finite positive number of starting entries greater than . is still a positive integer and a nonnegative integer, and the common-divisor argument applies to any finite list of exponents. The particular number is not essential.