Đề thi Olympic Toán Quốc tế lần thứ 65 năm 2024

Chia sẻ: Blog Toán | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

6
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhằm phục vụ cho quá trình học tập và ôn thi Olympic, Đề thi Olympic Toán Quốc tế lần thứ 65 năm 2024 sẽ là tư liệu tham khảo hữu ích cho các bạn học sinh thi Olympic Toán sắp tới. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi Olympic Toán Quốc tế lần thứ 65 năm 2024

IMO2024 65th International Mathematical Olympiad VNM1 Vietnamese (vie), day 1 Exam hall: J - 05 Thứ Ba, ngày 16 tháng Bảy năm 2024 Bài 1. Xác định tất cả các số thực 𝛼 sao cho với mọi số nguyên dương 𝑛 thì số nguyên ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ là một bội của 𝑛. (Trong đó, ⌊𝑧⌋ ký hiệu số nguyên lớn nhất không vượt quá 𝑧. Ví dụ, ⌊−𝜋⌋ = −4 và ⌊2⌋ = ⌊2,9⌋ = 2.) Bài 2. Xác định tất cả các cặp số nguyên dương (𝑎, 𝑏) sao cho tồn tại các số nguyên dương 𝑔 và 𝑁 thỏa mãn: gcd⁡(𝑎 𝑛 + 𝑏, 𝑏 𝑛 + 𝑎) = 𝑔 với mọi số nguyên 𝑛 ⩾ 𝑁. (Trong đó, gcd⁡(𝑥, 𝑦) ký hiệu ước chung lớn nhất của các số nguyên 𝑥 và 𝑦.) Bài 3. Cho dãy vô hạn các số nguyên dương 𝑎1 , 𝑎2 , 𝑎3 , … và số nguyên dương 𝑁. Giả sử rằng với mọi 𝑛 > 𝑁, 𝑎 𝑛 bằng số lần xuất hiện của 𝑎 𝑛−1 trong dãy 𝑎1 , 𝑎2 , … , 𝑎 𝑛−1. Chứng minh rằng một trong hai dãy số 𝑎1 , 𝑎3 , 𝑎5 , … và 𝑎2 , 𝑎4 , 𝑎6 , … là tuần hoàn kể từ một chỉ số nào đó. (Một dãy số vô hạn 𝑏1 , 𝑏2 , 𝑏3 , … là tuần hoàn kể từ một chỉ số nào đó nếu tồn tại các số nguyên dương 𝑝 và 𝑀 sao cho 𝑏 𝑚+𝑝 = 𝑏 𝑚 với mọi 𝑚 ⩾ 𝑀.) IMO2024 65th International Mathematical Mathematical Olympiad Vietnamese (vie), day 2 Exam hall: R - 36 Thú Tư, ngày 17 tháng Bảy năm 2024 Bài 4. Cho tam giác 𝐴𝐵𝐶 với 𝐴𝐵 < 𝐴𝐶 < 𝐵𝐶. Gọi 𝐼 và 𝜔 tương ứng là tâm nội tiếp và đường tròn nội tiếp tam giác 𝐴𝐵𝐶. Gọi 𝑋 là điểm nằm trên đường thẳng 𝐵𝐶, khác 𝐶, sao cho đường thẳng qua 𝑋 và song song với 𝐴𝐶 tiếp xúc với 𝜔. Tương tự, gọi 𝑌 là điểm nằm trên đường thẳng 𝐵𝐶, khác 𝐵, sao cho đường thẳng qua 𝑌 và song song với 𝐴𝐵 tiếp xúc với 𝜔. Đường thẳng 𝐴𝐼 cắt lại đường tròn ngoại tiếp tam giác 𝐴𝐵𝐶 tại 𝑃 ≠ 𝐴. Gọi 𝐾 và 𝐿 tương ứng là trung điểm của 𝐴𝐶 và 𝐴𝐵. Chứng minh rằng ∠𝐾𝐼𝐿 + ∠𝑌𝑃𝑋 = 180∘ .
Bài 5. Ốc sên Turbo chơi trò chơi sau trên một bảng ô vuông gồm 2024 hàng và 2023 cột. Trong 2022 ô vuông đơn vị nào đó, có các con quỷ nấp ở đó. Ban đầu, Turbo không hề biết ô nào có quỷ nấp, nhưng nó biết rằng trên mỗi hàng có đúng một con quỷ, ngoại 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 chuỗi các lần thử để tìm cách đi từ hàng đầu tiên tới hàng cuối cùng. Tại mỗi lần thử, nó được quyền chọn một ô bất kỳ trên hàng đầu tiên để 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ó cạnh chung với ô mà nó đang đứng. (Nó được phép đi qua các ô đã từng ghé qua trước đó.) 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 tiên để thực hiện một lần thử mới. Những con quỷ không di chuyển, và Turbo nhớ mỗi ô nó từng ghé qua là có quỷ hay không. Nếu nó tới được một ô bất kỳ trên hàng cuối cùng thì trò chơi kết thúc. Xác định giá trị nhỏ nhất của 𝑛 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á 𝑛 lần thử, cho dù những con quỷ có nấp ở những ô nào đi chăng nữa. Bài 6. Ký hiệu ℚ là tập các số hữu tỷ. Một hàm số 𝑓: ℚ → ℚ được gọi là đẹp nếu có tính chất sau: với mỗi 𝑥, 𝑦 ∈ ℚ, 𝑓(𝑥 + 𝑓(𝑦)) = 𝑓(𝑥) + 𝑦 hoặc ⁡𝑓(𝑓(𝑥) + 𝑦) = 𝑥 + 𝑓(𝑦). Chứng minh rằng tồn tại số nguyên 𝑐 sao cho với mọi hàm số đẹp 𝑓, có không quá 𝑐 số hữu tỷ phân biệt có dạng 𝑓(𝑟) + 𝑓(−𝑟), với 𝑟 là số hữu tỷ nào đó, và tìm giá trị nhỏ nhất có thể của 𝑐.
Bài 1. Xác định tất cả các số thực 𝛼 sao cho với mọi số nguyên dương 𝑛 thì số nguyên ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ là một bội của 𝑛. (Trong đó, ⌊𝑧⌋ ký hiệu số nguyên lớn nhất không vượt quá 𝑧. Ví dụ, ⌊−𝜋⌋ = −4 và ⌊2⌋ = ⌊2,9⌋ = 2.) Câu trả lời: Tất cả các số nguyên chẵn đều thỏa mãn điều kiện của bài toán và không có số thực 𝛼 nào khác thỏa mãn điều kiện này. Lời giải 1: Đầu tiên, chúng ta sẽ chứng minh rằng các số nguyên chẵn thỏa mãn điều kiện. Nếu 𝛼 = 2m , trong đó m là một số nguyên, thì ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ = 2𝑚 + 4𝑚 + ⋯ + 2𝑚𝑛 = 𝑚𝑛(𝑛 + 1) đây là một bội số của 𝑛. Bây giờ chúng ta sẽ chứng minh rằng chỉ có các số thực này mới thỏa mãn điều kiện của bài toán. Giả sử 𝛼 = 𝑘 + 𝜖, trong đó 𝑘 là một số nguyên và 0 ⩽ 𝜖 < 1. Khi đó số 𝑘𝑛(𝑛 + 1) ⁡⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ = 𝑘 + ⌊𝜖⌋ + 2𝑘 + ⌊2𝜖⌋ + ⋯ + 𝑛𝑘 + ⌊𝑛𝜖⌋ = + ⌊𝜖⌋ + 2 ⁡⌊2𝜖⌋ + ⋯ + ⌊𝑛𝜖⌋ phải là một bội số của n. Chúng ta xét hai trường hợp dựa trên tính chẵn lẻ của 𝑘. Trường hợp 1: k là số chẵn. Khi đó: 𝑘𝑛(𝑛 + 1) 2 luôn là một bội số của 𝑛. Do đó: ⌊𝜖⌋ + ⌊2𝜖⌋ + ⋯ + ⌊𝑛𝜖⌋ cũng phải là một bội số của 𝑛. Chúng ta sẽ chứng minh rằng ⌊𝑛𝜖⌋ = 0 với mọi số nguyên dương 𝑛 bằng phương pháp quy nạp mạnh. Trường hợp cơ sở 𝑛 = 1 xuất phát từ thực tế rằng 0 ⩽ 𝜖 < 1. Giả sử rằng ⌊𝑚𝜖⌋ = 0 với mọi 1 ⩽ m < n. Khi đó số: ⌊𝜖⌋ + ⌊2𝜖⌋ + ⋯ + ⌊𝑛𝜖⌋ = ⌊𝑛𝜖⌋ phải là một bội số của 𝑛. Vì 0 ⩽ 𝜖 < 1 nên 0 ⩽ 𝑛𝜖 < 𝑛, điều này có nghĩa là số ⌊𝑛𝜖⌋ phải bằng 0.
Đẳng thức ⌊𝑛𝜖⌋ = 0 ngụ ý 0 ⩽ 𝜖 < 1/𝑛. Vì điều này phải đúng với mọi 𝑛, chúng ta kết luận rằng 𝜖 = 0 và khi đó 𝛼 là một số nguyên chẵn. Trường hợp 2: k là số lẻ. Chúng ta sẽ chứng minh rằng ⌊𝑛𝜖⌋ = 𝑛 − 1 với mọi số tự nhiên 𝑛 bằng phương pháp quy nạp mạnh. Trường hợp cơ sở 𝑛 = 1 xuất phát từ thực tế rằng 0 ⩽ 𝜖 < 1. Giả sử rằng ⌊𝑛𝜖⌋ = 𝑚 − 1 với mọi 1 ⩽ 𝑚 < n. Chúng ta cần số: 𝑘𝑛(𝑛 + 1) 𝑘𝑛(𝑛 + 1) + ⌊𝜖⌋ + ⌊2𝜖⌋ + ⋯ + ⌊𝑛𝜖⌋ = + 0 + 1 + ⋯ + (𝑛 − 2) + ⌊𝑛𝜖⌋ = 2 2 𝑘𝑛(𝑛 + 1) (𝑛 − 2)(𝑛 − 1) (𝑘 + 1) 2 (𝑘 − 3) + + ⌊𝑛𝜖⌋ = 𝑛 + 𝑛 + 1 + ⌊𝑛𝜖⌋ 2 2 2 2 phải là một bội số của 𝑛. Vì 𝑘 là số lẻ, chúng ta cần 1 + ⌊𝑛𝜖⌋ là một bội số của 𝑛. Lại nữa, vì 0 ⩽ 𝜖 < 1 nên 0 ⩽ 𝑛 ∈< 𝑛, do đó ⌊𝑛𝜖⌋ = 𝑛 − 1 như chúng ta mong muốn. Điều này ngụ ý rằng 1 − 1/𝑛 ⩽ 𝜖 < 1 với mọi 𝑛, điều này là vô lý. Vì vậy, không có nghiệm nào khác trong trường hợp này. Lời giải 2: Như trong Lời giải 1, chúng ta kiểm tra rằng các số nguyên chẵn thỏa mãn điều kiện. Sau đó, không mất tính tổng quát, chúng ta có thể giả sử 0 ⩽ 𝛼 < 2. Chúng ta đặt 𝑆 𝑛 = ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋. Lưu ý rằng: 𝑆 𝑛 ≡ 0(mod𝑛) 𝑆 𝑛 ≡ 𝑆 𝑛 − 𝑆 𝑛−1 = ⌊𝑛𝛼⌋⁡(mod⁡𝑛 − 1) Ngoài ra, 𝑛 𝑛 𝑛(𝑛 − 1) 0 ⩽ 𝑛⌊𝑛𝛼⌋ − 𝑆 𝑛 = ∑ (⌊𝑛𝛼⌋ − ⌊𝑘𝛼⌋) < ∑ (𝑛𝛼 − 𝑘𝛼 + 1) = 𝛼+ 𝑛 2 𝑘=1 𝑘=1 Với n đủ lớn, vế phải của (4) nhỏ hơn n(n-1). Sau đó (3) buộc 𝑛 0 = 𝑆 𝑛 − 𝑛⌊𝑛𝛼⌋ = ∑ (⌊𝑛𝛼⌋ − ⌊𝑘𝛼⌋) 𝑘=1 với n đủ lớn. Vì ⌊𝑛𝛼⌋ − ⌊𝑘𝛼⌋ ⩾ 0 với mọi 1 ⩽ k ⩽ n, chúng ta có từ (5) rằng, với mọi n đủ lớn, tất cả các bất đẳng thức này đều là đẳng thức. Cụ thể ⌊𝛼⌋ = ⌊𝑛𝛼⌋ với mọi n đủ lớn, điều này là vô lý trừ khi 𝛼 = 0.
Nhận xét: Một kết thúc thay thế cho lời giải trước như sau. 𝑛(𝑛+1) Theo định nghĩa, chúng ta có 𝑆 𝑛 ⩽ 𝛼 2 , mặt khác (5) ngụ ý 𝑆 𝑛 ⩾ 𝛼𝑛2 − 𝑛 với mọi n đủ lớn, do đó 𝛼 = 0. Lời giải 3. Như các lời giải trước, Không mất tính tổng quát chúng ta có thể giả sử rằng 0 ⩽ 𝛼 < 2. Các số nguyên chẵn thỏa mãn điều kiện này, nên chúng ta giả sử 0 < 𝛼 < 2 và sẽ dẫn đến một mâu thuẫn. Bằng quy nạp theo 𝑛, chúng ta chứng đồng thời rằng: ⁡⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ = 𝑛2 ,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(6) 2𝑛 − 1 và ⁡ ⩽ 𝛼 < 2.⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(7) 𝑛 1 Trường hợp cơ sở 𝑛 = 1 : Nếu 𝛼 < 1, xét 𝑚 = ⌈ 𝛼⌉ > 1, thì: ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑚𝛼⌋ = 1 Không phải là một bội số của 𝑚, vì vậy chúng ta suy ra (7). Do đó, ⌊𝛼⌋ = 1 và (6) được thỏa mãn. Đối với bước quy nạp: giả sử giả thiết quy nạp đúng với 𝑛, thì theo (7): 1 2𝑛 + 1 − ⩽ (𝑛 + 1)𝛼 < 2𝑛 + 2. 𝑛 Do đó, 𝑛2 + 2𝑛 ⩽ ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ + ⌊(𝑛 + 1)𝛼⌋ = 𝑛2 + ⌊(𝑛 + 1)𝛼⌋ < 𝑛2 + 2𝑛 + 2. Vì vậy, bắt buộc phải có ⌊(𝑛 + 1)𝛼⌋ = 2𝑛 + 1 và ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ + ⌊(𝑛 + 1)𝛼⌋ = (𝑛 + 1)2 Để đạt được một bội số của 𝑛 + 1. Hai đẳng thức này lần lượt cho ta (6) và (7). Cuối cùng, chúng ta nhận thấy rằng điều kiện (7) đúng với mọi 𝑛 dẫn đến mộ mâu thuẫn. Lời giải 4. Như trong các lời giải khác, không mất tính tổng quát, chúng ta sẽ giả sử rằng 0 < 𝛼 < 2 và dẫn đến một mâu thuẫn. Với mỗi n , chúng ta định nghĩa ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ 𝑏𝑛 = , 𝑛 là một số nguyên không âm theo điều kiện của bài toán và giả sử của chúng ta. Lưu ý rằng ⌊(𝑛 + 1)𝛼⌋ ≥ ⌊𝛼⌋, ⌊2𝛼⌋, … , ⌊𝑛𝛼⌋ và ⌊(𝑛 + 1)𝛼⌋ > ⌊𝛼⌋
đối với tất cả n > 1/𝛼. Từ đó suy ra rằng 𝑏 𝑛+1 > 𝑏 𝑛 ⇒ 𝑏 𝑛+1 ≥ 𝑏 𝑛 + 1 đối với n > 1/𝛼. Vì vậy, đối với tất cả các 𝑛 như vậy, 𝑏𝑛 ≥ 𝑛+ 𝐶 trong đó 𝐶 là một số nguyên cố định. Mặt khác, định nghĩa của 𝑏 𝑛 cho ta ⌊𝛼⌋ + ⌊2𝛼⌋ + ⋯ + ⌊𝑛𝛼⌋ 𝛼 + 2𝛼 + ⋯ + 𝑛𝛼 𝛼 𝑏𝑛 = ≤ = (𝑛 + 1), 𝑛 𝑛 2 điều này dẫn đến một mâu thuẫn đối với 𝑛 đủ lớn. Bài 2. Xác định tất cả các cặp số nguyên dương (𝑎, 𝑏) sao cho tồn tại các số nguyên dương 𝑔 và 𝑁 thỏa mãn: gcd⁡(𝑎 𝑛 + 𝑏, 𝑏 𝑛 + 𝑎) = 𝑔 với mọi số nguyên 𝑛 ⩾ 𝑁. (Trong đó, gcd⁡(𝑥, 𝑦) ký hiệu ước chung lớn nhất của các số nguyên 𝑥 và 𝑦.) Đáp án: Chỉ có một nghiệm duy nhất là (𝑎, 𝑏) = (1,1). Lời giải 1. Rõ ràng rằng chúng ta có thể chọn 𝑔 = 2 cho (a, b) = (1,1). Giả sử rằng (a, b) thỏa mãn các điều kiện trong bài toán, hãy để N là một số nguyên dương sao cho gcd⁡(𝑎 𝑛 + 𝑏, 𝑏 𝑛 + 𝑎) = 𝑔 đối với mọi 𝑛 ≥ 𝑁. Bổ đề. Chúng ta có 𝑔 = gcd⁡(𝑎, 𝑏) hoặc 𝑔 = 2gcd⁡(𝑎, 𝑏). Chứng minh. Lưu ý rằng cả 𝑎 𝑁 + 𝑏 và 𝑎 𝑁+1 + 𝑏 đều chia hết cho 𝑔. Do đó 𝑎(𝑎 𝑁 + 𝑏) − (𝑎 𝑁+1 + 𝑏) = 𝑎𝑏 − 𝑏 = 𝑏(𝑎 − 1) chia hết cho 𝑔. Tướng tự, 𝑎(𝑏 − 1) chia hết cho 𝑔. Hiệu của chúng, 𝑎 − 𝑏, do đó cũng chia hết cho 𝑔, nên 𝑔 cũng chia hết cho 𝑎(𝑏 − 1) + 𝑎(𝑎 − 𝑏) = 𝑎2 − 𝑎. Tất cả các lũy thừa của 𝑎 đều đồng dư theo modulo 𝑔, nên 𝑎 + 𝑏 ≡ 𝑎 𝑁 + 𝑏 ≡ 0(mod𝑔). Vậy thì 2𝑎 = (𝑎 + 𝑏) + (𝑎 − 𝑏) và 2𝑏 = (𝑎 + 𝑏) − (𝑎 − 𝑏) đều chia hết cho 𝑔, nên 𝑔 ∣ 2gcd⁡(𝑎, 𝑏). Mặt khác, rõ ràng rằng gcd⁡(𝑎, 𝑏) ∣ 𝑔, do đó chứng minh được Bổ đề. Đặt 𝑑 = gcd⁡(𝑎, 𝑏), và viết 𝑎 = 𝑑𝑥 và 𝑏 = 𝑑𝑦 với 𝑥 và 𝑦 là các số nguyên dương nguyên tố cùng nhau. Chúng ta có: gcd⁡((𝑑𝑥) 𝑛 + 𝑑𝑦, (𝑑𝑦) 𝑛 + 𝑑𝑥) = 𝑑 ⋅ gcd⁡(𝑑 𝑛−1 𝑥 𝑛 + 𝑦, 𝑑 𝑛−1 𝑦 𝑛 + 𝑥), vì vậy Bổ đề cho chúng ta biết rằng: gcd⁡(𝑑 𝑛−1 𝑥 𝑛 + 𝑦, 𝑑 𝑛−1 𝑦 𝑛 + 𝑥) ≤ 2 đối với mọi 𝑛 ≥ 𝑁. Định nghĩa 𝐾 = 𝑑2 𝑥𝑦 + 1, lưu ý rằng 𝐾 là nguyên tố cùng nhau với mỗi 𝑑, 𝑥, và 𝑦. Theo định lý Euler, với 𝑛 ≡ −1(mod𝜑(𝐾)) chúng ta có:
𝑑 𝑛−1 𝑥 𝑛 + 𝑦 ≡ 𝑑 −2 𝑥 −1 + 𝑦 ≡ 𝑑−2 𝑥 −1 (1 + 𝑑2 𝑥𝑦) ≡ 0(mod𝐾) nên 𝐾 ∣ 𝑑 𝑛−1 𝑥 𝑛 + 𝑦. Tương tự, chúng ta có 𝐾 ∣ 𝑑 𝑛−1 𝑦 𝑛 + 𝑥. Chọn 𝑛 sao cho 𝑛 ≥ 𝑁 và thỏa mãn điều kiện trên cho chúng ta biết rằng: 𝐾 ∣ gcd⁡(𝑑 𝑛−1 𝑥 𝑛 + 𝑦, 𝑑 𝑛−1 𝑦 𝑛 + 𝑥) ≤ 2. Điều này chỉ có thể xảy ra khi 𝑑 = 𝑥 = 𝑦 = 1, điều này đưa ra nghiệm duy nhất là (a, b) = (1,1). Lời giải 2. Sau khi chứng minh Bổ đề, ta có thể hoàn tất lời giải như sau. Đối với bất kỳ ước nguyên tố 𝑝 của 𝑎𝑏 + 1, 𝑝 là nguyên tố cùng nhau với 𝑎 và 𝑏. Chọn 𝑛 ≥ 𝑁 sao cho 𝑛 ≡ −1(mod⁡𝑝 − 1). Theo Bổ đề nhỏ Fermat, chúng ta có 𝑎 𝑛 + 𝑏 ≡ 𝑎−1 + 𝑏 = 𝑎 −1 (1 + 𝑎𝑏) ≡ 0(mod𝑝) 𝑏 𝑛 + 𝑎 ≡ 𝑏 −1 + 𝑎 = 𝑏 −1 (1 + 𝑎𝑏) ≡ 0(mod𝑝), khi đó 𝑝 chia hết cho 𝑔. Theo Bổ đề, ta có 𝑝 ∣ 2gcd⁡(𝑎, 𝑏), do đó 𝑝 = 2. Vì vậy, 𝑎𝑏 + 1 là lũy thừa của 2 , và cả 𝑎 và 𝑏 đều là các số lẻ. Nếu (𝑎, 𝑏) ≠ (1,1), thì 𝑎𝑏 + 1 chia hết cho 4 , do đó {𝑎, 𝑏} = {−1,1}(mod4). Đối với 𝑛 lẻ ≥ 𝑁, ta có 𝑎 𝑛 + 𝑏 ≡ 𝑏 𝑛 + 𝑎 ≡ (−1) + 1 = 0(mod4), khi đó 4 chia hết cho 𝑔. Nhưng theo Bổ đề, ta có 𝜈2 (𝑔) ≤ 𝜈2 (2gcd⁡(𝑎, 𝑏)) = 1, điều này dẫn đến một mâu thuẫn. Vậy nghiệm duy nhất của bài toán là (𝑎, 𝑏) = (1,1). Bình luận. Trên thực tế, ý tưởng xét 𝑎 𝑛 + 𝑏 và 𝑏 𝑛 + 𝑎 theo modulo 𝑎𝑏 + 1 là đủ để giải quyết bài toán, không cần đến Bổ đề. Như trong lời giải 2 , chúng ta có 𝑎𝑏 + 1 ∣ 𝑎 𝑛 + 𝑏 và 𝑎𝑏 + 1 ∣ 𝑏 𝑛 + 𝑎 đối với vô số mũ 𝑛; do đó 𝑎𝑏 + 1 ∣ 𝑔. Sau đó, đối với 𝑛 đủ lớn ≡ 0⁡(mod𝜑(𝑎𝑏 + 1)) chúng ta có: 0 ≡ 𝑎 𝑛 + 𝑏 ≡ 1 + 𝑏(mod𝑎𝑏 + 1) và 0 ≡ 𝑏 𝑛 + 𝑎 ≡ 1 + 𝑎(mod𝑎𝑏 + 1) Điều này dẫn ngay đến 𝑎 = 𝑏 = 1. Bài 3. Cho dãy vô hạn các số nguyên dương 𝑎1 , 𝑎2 , 𝑎3 , … và số nguyên dương 𝑁. Giả sử rằng với mọi 𝑛 > 𝑁, 𝑎 𝑛 bằng số lần xuất hiện của 𝑎 𝑛−1 trong dãy 𝑎1 , 𝑎2 , … , 𝑎 𝑛−1. Chứng minh rằng một trong hai dãy số 𝑎1 , 𝑎3 , 𝑎5 , … và 𝑎2 , 𝑎4 , 𝑎6 , … là tuần hoàn kể từ một chỉ số nào đó.
(Một dãy số vô hạn 𝑏1 , 𝑏2 , 𝑏3 , … là tuần hoàn kể từ một chỉ số nào đó nếu tồn tại các số nguyên dương 𝑝 và 𝑀 sao cho 𝑏 𝑚+𝑝 = 𝑏 𝑚 với mọi 𝑚 ⩾ 𝑀.) Lời giải 1. Giả sử 𝑀 > max(𝑎1 , … , 𝑎 𝑁 ). Trước tiên, chúng ta chứng minh rằng có một số nguyên xuất hiện vô hạn lần. Nếu không, thì dãy số chứa các số nguyên lớn hơn bất kỳ giá trị nào. Lần đầu tiên mỗi số nguyên lớn hơn 𝑀 xuất hiện, nó sẽ được theo sau bởi số 1 . Vì vậy, số 1 xuất hiện vô hạn lần, điều này dẫn đến mâu thuẫn. Bây giờ chúng ta chứng minh rằng mỗi số nguyên 𝑥 ≥ 𝑀 xuất hiện ít nhất là 𝑀 − 1 lần. Nếu không, hãy xem lần đầu tiên mà bất kỳ số 𝑥 ≥ 𝑀 xuất hiện lần thứ 𝑀. Tính đến thời điểm này, mỗi lần xuất hiện của 𝑥 sẽ được theo sau bởi một số nguyên đã xuất hiện 𝑥 ≥ 𝑀 lần. Do đó, ít nhất đã có 𝑀 số đã xuất hiện ít nhất 𝑀 lần trước khi 𝑥 xuất hiện, điều này dẫn đến mâu thuẫn. Vì vậy, chỉ có một số hữu hạn các số xuất hiện vô hạn lần. Giả sử số lớn nhất trong số đó là 𝑘. Vì 𝑘 xuất hiện vô hạn lần, nên có vô hạn số nguyên lớn hơn 𝑀 xuất hiện ít nhất 𝑘 lần trong dãy số, vì vậy mỗi số nguyên 1,2, … , 𝑘 − 1 cũng xuất hiện vô hạn lần. Vì 𝑘 + 1 không xuất hiện vô hạn lần nên chỉ có một số hữu hạn các số xuất hiện nhiều hơn 𝑘 lần. Giả sử số lớn nhất trong số đó là 𝑙 ≥ 𝑘. Từ đây trở đi, chúng ta gọi một số nguyên 𝑥 là lớn nếu 𝑥 > 𝑙, là trung bình nếu 𝑙 ≥ 𝑥 > 𝑘 và là nhỏ nếu 𝑥 ≤ 𝑘. Tóm lại, mỗi số nhỏ xuất hiện vô hạn lần trong dãy số, trong khi mỗi số lớn xuất hiện ít nhất là 𝑘 lần trong dãy số. Chọn một số 𝑁 ′ > 𝑁 đủ lớn sao cho 𝑎 𝑁′ là số nhỏ, và trong dãy 𝑎1 , … , 𝑎 𝑁′ : • Mỗi số trung bình đã xuất hiện đủ số lần của nó; • Mỗi số nhỏ đã xuất hiện nhiều hơn max(𝑘, 𝑁) lần. Vì mỗi số nhỏ đã xuất hiện nhiều hơn 𝑘 lần, nên sau điểm này, mỗi số nhỏ phải được theo sau bởi một số lớn. Cũng theo định nghĩa, mỗi số lớn xuất hiện ít nhất là 𝑘 lần, nên nó phải được theo sau bởi một số nhỏ. Do đó, dãy số luân phiên giữa các số lớn và số nhỏ sau 𝑎 𝑁′ . Bổ đề 1. Giả sử 𝑔 là một số lớn xuất hiện sau 𝑎 𝑁′ . Nếu 𝑔 được theo sau bởi số nhỏ ℎ, thì ℎ bằng số lượng các số nhỏ đã xuất hiện ít nhất 𝑔 lần trước thời điểm đó. Chứng minh. Theo định nghĩa của 𝑁 ′ , số nhỏ ngay trước 𝑔 đã xuất hiện nhiều hơn max(𝑘, 𝑁) lần, vì vậy 𝑔 > max(𝑘, 𝑁). Và vì 𝑔 > 𝑁, lần xuất hiện thứ 𝑔 của mỗi số nhỏ phải xảy ra sau 𝑎 𝑁 và do đó được theo sau bởi 𝑔. Vì có 𝑘 số nhỏ và 𝑔 xuất hiện ít nhất là 𝑘 lần, 𝑔 phải xuất hiện chính xác 𝑘 lần, luôn theo sau một số nhỏ sau 𝑎 𝑁 . Do đó, tại lần xuất hiện thứ ℎ của 𝑔, chính xác ℎ số nhỏ đã xuất hiện ít nhất 𝑔 lần trước thời điểm đó. Bổ đề 2. Giả sử rằng 𝑖 và 𝑗 thỏa mãn các điều kiện sau: (a) 𝑗 > 𝑖 > 𝑁 ′ + 2,
(b) 𝑎 𝑖 là số nhỏ và 𝑎 𝑖 = 𝑎 𝑗 , (c) Không có giá trị nhỏ nào xuất hiện nhiều hơn một lần trong 𝑎[𝑖,𝑗−1] . Thì 𝑎 𝑖−2 bằng một số nhỏ nào đó trong 𝑎[𝑖,𝑗−1] . Chứng minh. Gọi 𝐼 là tập hợp các số nhỏ xuất hiện ít nhất 𝑎 𝑖−1 lần trong 𝑎[1,𝑖−1] . Theo Bổ đề 1, 𝑎 𝑖 = |𝐼|. Tương tự, gọi 𝐽 là tập hợp các số nhỏ xuất hiện ít nhất 𝑎 𝑗−1 lần trong 𝑎[1,𝑗−1] . Sau đó theo Bổ đề 1, 𝑎 𝑗 = |𝐽| và do đó theo (b), |𝐼| = |𝐽|. Cũng theo định nghĩa, 𝑎 𝑖−2 ∈ 𝐼 và 𝑎 𝑗−2 ∈ 𝐽. Giả sử số nhỏ 𝑎 𝑗−2 không thuộc 𝐼. Điều này có nghĩa là 𝑎 𝑗−2 đã xuất hiện ít hơn 𝑎 𝑖−1 lần trong 𝑎[1,𝑖−1] . Theo (c), 𝑎 𝑗−2 đã xuất hiện ít nhất là 𝑎 𝑖−1 lần trong 𝑎[1,𝑗−1] , do đó 𝑎 𝑗−1 ≤ 𝑎 𝑖−1 . Kết hợp với 𝑎[1,𝑖−1] ⊆ 𝑎[1,𝑗−1] , điều này dẫn đến 𝐼 ⊆ 𝐽. Nhưng vì 𝑎 𝑗−2 ∈ 𝐽 ∖ 𝐼, điều này mâu thuẫn với |𝐼| = |𝐽|. Vậy 𝑎 𝑗−2 ∈ 𝐼, có nghĩa là nó đã xuất hiện ít nhất là 𝑎 𝑖−1 lần trong 𝑎[1,𝑖−1] và một lần nữa trong 𝑎[𝑖,𝑗−1] . Do đó, 𝑎 𝑗−1 > 𝑎 𝑖−1 . Theo (c), bất kỳ số nhỏ nào xuất hiện ít nhất là 𝑎 𝑗−1 lần trong 𝑎[1,𝑗−1] cũng đã xuất hiện ít nhất 𝑎 𝑗−1 − 1 ≥ 𝑎 𝑖−1 lần trong 𝑎[1,𝑖−1] . Do đó, 𝐽 ⊆ 𝐼 và do đó 𝐼 = 𝐽. Vì vậy, 𝑎 𝑖−2 ∈ 𝐽, vì vậy nó phải xuất hiện ít nhất là 𝑎 𝑗−1 − 𝑎 𝑖−1 = 1 lần nữa trong 𝑎[𝑖,𝑗−1] . Đối với mỗi số nhỏ 𝑎 𝑛 với 𝑛 > 𝑁 ′ + 2, gọi 𝑝 𝑛 là số nhỏ nhất sao cho 𝑎 𝑛+𝑝 𝑛 = 𝑎 𝑖 cũng là số nhỏ với một số 𝑖 sao cho 𝑛 ≤ 𝑖 < 𝑛 + 𝑝 𝑛 . Nói cách khác, 𝑎 𝑛+𝑝 𝑛 = 𝑎 𝑖 là số nhỏ đầu tiên xuất hiện hai lần sau 𝑎 𝑛−1 . Nếu 𝑖 > 𝑛, Bổ đề 2 (với 𝑗 = 𝑛 + 𝑝 𝑛 ) chỉ ra rằng 𝑎 𝑖−2 xuất hiện lại trước 𝑎 𝑛+𝑝 𝑛 , mâu thuẫn với tính tối thiểu của 𝑝 𝑛 . Vì vậy, 𝑖 = 𝑛. Bổ đề 2 cũng chỉ ra rằng 𝑝 𝑛 ≥ 𝑝 𝑛−2. Do đó, 𝑝 𝑛 , 𝑝 𝑛+2 , 𝑝 𝑛+4 , … là một dãy số không giảm bị chặn trên bởi 2𝑘 (vì có chỉ 𝑘 số nhỏ). Vì vậy, 𝑝 𝑛 , 𝑝 𝑛+2 , 𝑝 𝑛+4 , … cuối cùng trở nên không thay đổi và dãy số của các số nhỏ trở nên tuần hoàn với chu kỳ tối đa là 𝑘. Lưu ý. Vì mỗi số nhỏ xuất hiện vô hạn lần, Lời giải 1 còn chứng minh rằng dãy số của các số nhỏ có chu kỳ bằng 𝑘. Phần lặp lại của dãy số các số nhỏ do đó là một hoán vị của các số nguyên từ 1 đến 𝑘. Có thể chỉ ra rằng bất kỳ hoán vị nào của các số nguyên từ 1 đến 𝑘 đều có thể đạt được theo cách này. Lời giải 2. Chúng ta tiếp tục theo Lời giải 1 cho đến sau Bổ đề 1. Đối với mỗi 𝑛 > 𝑁 ′ , chúng ta theo dõi số lần mỗi số từ 1 đến 𝑘 đã xuất hiện trong 𝑎1 , … , 𝑎 𝑛 . Chúng ta sẽ ghi lại thông tin này trong một tuple (𝑘 + 1) đang cập nhật: (𝑏1 , 𝑏2 , … , 𝑏 𝑘 ; 𝑗) trong đó mỗi 𝑏 𝑖 ghi số lần số 𝑖 đã xuất hiện. Phần tử cuối cùng 𝑗 của tuple (k + 1), còn gọi là phần tử hiện tại, đại diện cho số nhỏ gần nhất đã xuất hiện trong 𝑎1 , … , 𝑎 𝑛 .
Khi 𝑛 tăng lên, giá trị của (𝑏1 , 𝑏2 , … , 𝑏 𝑘 ; 𝑗) được cập nhật mỗi khi 𝑎 𝑛 là số nhỏ. Tuple (k+1) cập nhật theo cách xác định dựa trên giá trị trước đó của nó. Cụ thể, khi 𝑎 𝑛 = 𝑗 là số nhỏ, phần tử hiện tại được cập nhật thành 𝑗 và chúng ta tăng 𝑏 𝑗 lên 1 . Số lớn tiếp theo là 𝑎 𝑛+1 = 𝑏 𝑗 . Theo Bổ đề 1, giá trị tiếp theo của phần tử hiện tại, hoặc số nhỏ tiếp theo 𝑎 𝑛+2 , được cho bởi số lượng các 𝑏 có giá trị lớn hơn hoặc bằng 𝑏 𝑗 mới được cập nhật, hoặc |{𝑖 ∣ 1 ≤ 𝑖 ≤ 𝑘, 𝑏 𝑖 ≥ 𝑏 𝑗 }| Mỗi số nguyên đủ lớn xuất hiện 𝑖 + 1 lần cũng phải xuất hiện 𝑖 lần, với cả hai lần xuất hiện này xảy ra sau khối ban đầu của 𝑁. Vì vậy, tồn tại một hằng số toàn cục 𝐶 sao cho 𝑏 𝑖+1 − 𝑏 𝑖 ≤ 𝐶. Giả sử rằng với một số 𝑟, 𝑏 𝑟+1 − 𝑏 𝑟 không bị chặn từ dưới. Vì giá trị của 𝑏 𝑟+1 − 𝑏 𝑟 thay đổi tối đa là 1 khi nó được cập nhật, nên phải có một lần cập nhật nào đó mà 𝑏 𝑟+1 − 𝑏 𝑟 giảm và 𝑏 𝑟+1 − 𝑏 𝑟 < −(𝑘 − 1)𝐶. Kết hợp với thực tế rằng 𝑏 𝑖 − 𝑏 𝑖−1 ≤ 𝐶 cho tất cả 𝑖, chúng ta thấy rằng tại điểm cụ thể này, theo bất đẳng thức tam giác: min(𝑏1 , … , 𝑏 𝑟 ) > max(𝑏 𝑟+1 , … , 𝑏 𝑘 ) Vì 𝑏 𝑟+1 − 𝑏 𝑟 vừa giảm, phần tử hiện tại mới là 𝑟. Từ điểm này trở đi, nếu phần tử hiện tại mới là tối đa 𝑟, theo (1) và (2), phần tử tiếp theo để tăng là từ 𝑏1 , … , 𝑏 𝑟 . Do đó, chỉ có 𝑏1 , … , 𝑏 𝑟 sẽ tăng từ điểm này trở đi, và 𝑏 𝑘 sẽ không còn tăng nữa, điều này mâu thuẫn với thực tế rằng 𝑘 phải xuất hiện vô hạn lần trong dãy số. Do đó, |𝑏 𝑟+1 − 𝑏 𝑟 | bị chặn. Vî |𝑏 𝑟+1 − 𝑏 𝑟 | bị chặn, điều này dẫn đến mỗi |𝑏 𝑖 − 𝑏1 | bị chặn cho 𝑖 = 1, … , 𝑘. Điều này có nghĩa là chỉ có một số hữu hạn các trạng thái khác nhau cho (𝑏1 − 𝑏1 , 𝑏2 − 𝑏1 , … , 𝑏 𝑘 − 𝑏1 ; 𝑗). Vì phần tử hiện tại tiếp theo hoàn toàn được xác định bởi các kích thước tương đối của 𝑏1 , 𝑏2 , … , 𝑏 𝑘 với nhau, và việc cập nhật các giá trị 𝑏 phụ thuộc vào phần tử hiện tại, phần tử hiện tại phải trở nên tuần hoàn. Do đó, dãy số con, hoặc 𝑎1 , 𝑎3 , 𝑎5 , … hoặc 𝑎2 , 𝑎4 , 𝑎6 , …, phải trở nên tuần hoàn. Bài 4. Cho tam giác 𝐴𝐵𝐶 với 𝐴𝐵 < 𝐴𝐶 < 𝐵𝐶. Gọi 𝐼 và 𝜔 tương ứng là tâm nội tiếp và đường tròn nội tiếp tam giác 𝐴𝐵𝐶. Gọi 𝑋 là điểm nằm trên đường thẳng 𝐵𝐶, khác 𝐶, sao cho đường thẳng qua 𝑋 và song song với 𝐴𝐶 tiếp xúc với 𝜔. Tương tự, gọi 𝑌 là điểm nằm trên đường thẳng 𝐵𝐶, khác 𝐵, sao cho đường thẳng qua 𝑌 và song song với 𝐴𝐵 tiếp xúc với 𝜔. Đường thẳng 𝐴𝐼 cắt lại đường tròn ngoại tiếp tam giác 𝐴𝐵𝐶 tại 𝑃 ≠ 𝐴. Gọi 𝐾 và 𝐿 tương ứng là trung điểm của 𝐴𝐶 và 𝐴𝐵. Chứng minh rằng ∠𝐾𝐼𝐿 + ∠𝑌𝑃𝑋 = 180∘ . Lời giải 1. Giả sử 𝐴′ là hình chiếu của 𝐴 qua 𝐼, thì 𝐴′ nằm trên phân giác góc 𝐴𝑃. Các đường thẳng 𝐴′ 𝑋 và 𝐴′ 𝑌 là hình chiếu của 𝐴𝐶 và 𝐴𝐵 qua 𝐼, tương ứng, và do đó chúng là các tiếp tuyến của 𝜔 từ 𝑋 và 𝑌. Như đã biết, 𝑃𝐵 = 𝑃𝐶 = 𝑃𝐼 và vì 1 ∠𝐵𝐴𝑃 = ∠𝑃𝐴𝐶 > 30∘ , 𝑃𝐵 = 𝑃𝐶 lớn hơn bán kính ngoại tiếp. Do đó, 𝑃𝐼 > 2 𝐴𝑃 > 𝐴𝐼; chúng ta kết luận rằng 𝐴′ nằm trong đoạn 𝐴𝑃.
Chúng ta có ∠𝐴𝑃𝐵 = ∠𝐴𝐶𝐵 trong đường tròn ngoại tiếp và ∠𝐴𝐶𝐵 = ∠𝐴′ 𝑋𝐶 vì 𝐴′ 𝑋 ∥ 𝐴𝐶. Do đó, ∠𝐴𝑃𝐵 = ∠𝐴′ 𝑋𝐶, và do đó tứ giác 𝐵𝑃𝐴′ 𝑋 là tứ giác ngoại tiếp. Tương tự, điều này cho thấy 𝐶𝑌𝐴′ 𝑃 là tứ giác ngoại tiếp. Bây giờ chúng ta sẵn sàng chuyển đổi ∠𝐾𝐼𝐿 + ∠𝑌𝑃𝑋 thành tổng các góc trong tam giác 𝐴′ 𝐶𝐵 . Bằng phép vị tự tỷ lệ 2 tại 𝐴, chúng ta có ∠𝐾𝐼𝐿 = ∠𝐶𝐴′ 𝐵. Trong các đường tròn 𝐵𝑃𝐴′ 𝑋 và 𝐶𝑌𝐴′ 𝑃, chúng ta có ∠𝐴𝑃𝑋 = ∠𝐴′ 𝐵𝐶 và ∠𝑌𝑃𝐴 = ∠𝐵𝐶𝐴′ , do đó ∠𝐾𝐼𝐿 + ∠𝑌𝑃𝑋 = ∠𝐶𝐴′ 𝐵 + (∠𝑌𝑃𝐴 + ∠𝐴𝑃𝑋) = ∠𝐶𝐴′ 𝐵 + ∠𝐵𝐶𝐴′ + ∠𝐴′ 𝐵𝐶 = 180∘ Nhận xét. Ràng buộc 𝐴𝐵 < 𝐴𝐶 < 𝐵𝐶 được Ủy ban Lựa chọn bài toán thêm vào nhằm giảm các trường hợp xảy ra. Nếu không có điều này, sẽ có thêm hai cấu hình có thể xảy ra theo thứ tự của các điểm 𝐴, 𝑃 và 𝐴′ , như được chỉ ra trong các hình minh họa dưới đây. Lời giải cho các trường hợp này về cơ bản là giống nhau, nhưng cần phải chú ý thêm trong trường hợp suy biến khi 𝐴′ trùng với 𝑃 và đường thẳng 𝐴𝑃 là tiếp tuyến chung của các đường tròn 𝐵𝑃𝑋 và 𝐶𝑃𝑌.
𝑎+𝑏+𝑐 Lời giải 2. Gọi 𝐵𝐶 = 𝑎, 𝐴𝐶 = 𝑏, 𝐴𝐵 = 𝑐 và 𝑠 = 2 . Gọi bán kính của đường tròn nội tiếp, đường tròn bàng tiếp tại đỉnh B và đường tròn bàng tiếp tại đỉnh C lần lượt là 𝑟, 𝑟 𝑏 và 𝑟𝑐 . Gọi đường tròn nội tiếp tiếp xúc với 𝐴𝐶 và 𝐴𝐵 tại 𝐵0 và 𝐶0 , tương ứng; gọi đường tròn bàng tiếp tại đỉnh B tiếp xúc với 𝐴𝐶 tại 𝐵1, và gọi đường tròn bàng tiếp tại đỉnh C tiếp xúc với 𝐴𝐵 tại 𝐶1 . Như đã biết, 𝐴𝐵1 = 𝑠 − 𝑐 và diện tích của tam giác △ 𝐴𝐵𝐶 = 𝑟𝑠 = 𝑟𝑐 (𝑠 − 𝑐). Gọi đường thẳng qua 𝑋, song song với 𝐴𝐶, tiếp xúc với đường tròn nội tiếp tại 𝐸, và đường thẳng qua 𝑌, song song với 𝐴𝐵, tiếp xúc với đường tròn nội tiếp tại 𝐷. Cuối cùng, gọi 𝐴𝑃 cắt 𝐵𝐵1 tại 𝐹.
Như đã biết, các điểm 𝐵, 𝐸, và 𝐵1 nằm trên một đường thẳng theo phép đồng dạng giữa đường tròn nội tiếp và đường tròn bàng tiếp tại đỉnh B, và 𝐵𝐸 ∥ 𝐼𝐾 vì 𝐼𝐾 là đường trung tuyến trong tam giác 𝐵0 𝐸𝐵1. Tương tự, các điểm 𝐶, 𝐷, và 𝐶1 cũng nằm trên một đường thẳng và 𝐶𝐷 ∥ 𝐼𝐿. Do đó, bài toán giảm xuống việc chứng minh ∠𝑌𝑃𝐴 = ∠𝐶𝐵𝐸 (và đối xứng với nó là ∠𝐴𝑃𝑋 = ∠𝐷𝐶𝐵 với đỉnh là 𝐶 ), vì vậy chỉ cần chứng minh rằng 𝐹𝑌𝑃𝐵 là tứ giác ngoại tiếp. Vì 𝐴𝐶𝑃𝐵 là tứ giác 𝐵𝐹 𝐵𝑌 ngoại tiếp, điều này tương đương với việc 𝐹𝑌 ∥ 𝐵1 𝐶 và 𝐹𝐵 = 𝑌𝐶 . 1 Theo định lý về phân giác của 1 góc, ta có: 𝐵𝐹 𝐴𝐵 𝑐 = = . 𝐹𝐵1 𝐴𝐵1 𝑠− 𝑐 Phép đồng dạng tại 𝐶 biến đường tròn nội tiếp thành đường tròn bàng tiếp tại đỉnh C , biến 𝑌 thành 𝐵, vì vậy: 𝐵𝐶 𝑟𝑐 𝑠 = = 𝑌𝐶 𝑟 𝑠− 𝑐 Do đó, 𝐵𝑌 𝐵𝐶 𝑠 𝑐 𝐵𝐹 = −1= −1= = 𝑌𝐶 𝑌𝐶 𝑠− 𝑐 𝑠− 𝑐 𝐹𝐵1 hoàn tất bài toán. Bài 5. Ốc sên Turbo chơi trò chơi sau trên một bảng ô vuông gồm 2024 hàng và 2023 cột. Trong 2022 ô vuông đơn vị nào đó, có các con quỷ nấp ở đó. Ban đầu, Turbo không hề biết ô nào có quỷ nấp, nhưng nó biết rằng trên mỗi hàng có đúng một con quỷ, ngoại 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 chuỗi các lần thử để tìm cách đi từ hàng đầu tiên tới hàng cuối cùng. Tại mỗi lần thử, nó được quyền chọn một ô bất kỳ trên hàng đầu tiên để 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ó cạnh chung với ô mà nó đang đứng. (Nó được phép đi qua các ô đã từng ghé qua trước đó.) 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 tiên để thực hiện một lần thử mới. Những con quỷ không di chuyển, và Turbo nhớ mỗi ô nó từng ghé qua là có quỷ hay không. Nếu nó tới được một ô bất kỳ trên hàng cuối cùng thì trò chơi kết thúc. Xác định giá trị nhỏ nhất của 𝑛 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á 𝑛 lần thử, cho dù những con quỷ có nấp ở những ô nào đi chăng nữa.
Bình luận. Một trong những khó khăn chính của bài toán này là xác định biểu thức chính xác cho 𝑛. Học sinh có thể dành nhiều thời gian cố gắng chứng minh các giới hạn cho giá trị sai của 𝑛 trước khi tìm được chiến lược tốt hơn. Học sinh có thể giả định sai rằng Turbo không được phép quay lại các ô mà anh ấy đã viếng thăm trong một lần thử. May mắn thay, việc đưa ra giả định này không làm thay đổi kết quả của bài toán, mặc dù có thể làm cho việc tìm kiếm một chiến lược chiến thắng trở nên khó khăn hơn. Câu trả lời: Giá trị của 𝑛 là 3 . Lời giải. Đầu tiên, chúng ta chứng minh rằng không có chiến lược chiến thắng nếu Turbo chỉ có 2 lần thử. Giả sử rằng (2, 𝑖) là ô đầu tiên trong hàng thứ hai mà Turbo đến được trong lần thử đầu tiên của anh ấy. Có thể có một con quái vật trong ô này, trong trường hợp đó, Turbo phải quay trở lại hàng đầu tiên ngay lập tức, và anh ấy không thể đã đến bất kỳ ô nào khác qua hàng đầu tiên. Tiếp theo, giả sử rằng (3, 𝑗) là ô đầu tiên trong hàng thứ ba mà Turbo đến được trong lần thử thứ hai của anh ấy. Turbo chắc chắn phải di chuyển đến ô này từ (2, 𝑗), vì vậy chúng ta biết 𝑗 ≠ 𝑖. Do đó, có thể có một con quái vật trên (3, 𝑗), trong trường hợp đó Turbo cũng sẽ thất bại trong lần thử thứ hai. Do đó, Turbo không thể đảm bảo đến được hàng cuối cùng trong 2 lần thử. Tiếp theo, chúng ta đưa ra một chiến lược cho 𝑛 = 3. Trong lần thử đầu tiên, Turbo di chuyển theo đường đi: (1,1) → (2,1) → (2,2) → ⋯ → (2,2023) Đường đi này đi qua mọi ô trong hàng thứ hai, vì vậy Turbo sẽ tìm thấy con quái vật trong hàng thứ hai và lần thử của anh ấy sẽ kết thúc. Nếu con quái vật trong hàng thứ hai không nằm ở mép của bảng (tức là, nó ở ô (2, 𝑖) với 2 ≤ 𝑖 ≤ 2022), thì Turbo thực hiện hai đường đi sau trong lần thử thứ hai và thứ ba của anh ấy: Đường đi 1: (1, 𝑖 − 1) → (2, 𝑖 − 1) → (3, 𝑖 − 1) → (3, 𝑖) → (4, 𝑖) → ⋯ → (2024, 𝑖) Đường đi 2: (1, 𝑖 + 1) → (2, 𝑖 + 1) → (3, 𝑖 + 1) → (3, 𝑖) → (4, 𝑖) → ⋯ → (2024, 𝑖) Các ô duy nhất có thể chứa quái vật trong bất kỳ đường đi nào trong số này là (3, 𝑖 − 1) và (3, 𝑖 + 1). Tối đa một trong số các ô này có thể chứa quái vật, vì vậy ít nhất một trong hai đường đi sẽ thành công.
Hình 1: Lần thử đầu tiên của Turbo, cùng với lần thử thứ hai và thứ ba trong trường hợp con quái vật ở hàng thứ hai không nằm ở mép. Dấu chéo chỉ vị trí của con quái vật, và các ô tối màu là các ô được đảm bảo không chứa quái vật. Nếu con quái vật ở hàng thứ hai nằm ở mép của bảng, mà không làm mất tính tổng quát, ta có thể giả định rằng nó nằm ở (2,1). Trong trường hợp này, trong lần thử thứ hai, Turbo thực hiện đường đi sau: (1,2) → (2,2) → (2,3) → (3,3) → ⋯ → (2022,2023) → (2023,2023) → (2024,2023) Hình 2: Các lần thử thứ hai và thứ ba của Turbo trong trường hợp con quái vật ở hàng thứ hai nằm ở mép. Các ô màu xám nhạt trên sơ đồ bên phải chỉ các ô đã được viếng thăm trong lần thử trước đó. Lưu ý rằng không phải tất cả các ô an toàn đã được tô màu.
Giải thích: • Trong lần thử đầu tiên, Turbo di chuyển qua toàn bộ hàng thứ hai. Nếu con quái vật không nằm ở mép, thì nó nằm trong khoảng từ (2,2) đến (2,2022). Các đường đi trong lần thử thứ hai và thứ ba đều được thiết kế để kiểm tra các ô gần con quái vật mà không để bỏ sót bất kỳ ô nào. • Trong trường hợp con quái vật nằm ở mép (ví dụ, tại (2,1) ), đường đi của lần thử thứ hai của Turbo được thiết kế để kiểm tra các ô có thể chứa con quái vật mà không bỏ qua bất kỳ ô nào trong hàng thứ ba mà Turbo cần phải kiểm tra. Như vậy, bằng cách này, Turbo có thể đảm bảo rằng anh ấy sẽ phát hiện ra con quái vật trong 3 lần thử, cho dù con quái vật nằm ở đâu trong hàng thứ hai. Nếu không có con quái vật nào trên đường đi này, thì Turbo chiến thắng. Nếu không, giả sử (𝑖, 𝑗) là ô đầu tiên mà Turbo gặp phải con quái vật. Chúng ta có thể có 𝑗 = 𝑖 hoặc 𝑗 = 𝑖 + 1. Sau đó, trong lần thử thứ ba, Turbo thực hiện đường đi sau: (1,2) ⁡→ (2,2) → (2,3) → (3,3) → ⋯ → (𝑖 − 2, 𝑖 − 1) → (𝑖 − 1, 𝑖 − 1) ⁡→ (𝑖, 𝑖 − 1) → (𝑖, 𝑖 − 2) → ⋯ → (𝑖, 2) → (𝑖, 1) ⁡→ (𝑖 + 1,1) → ⋯ → (2023,1) → (2024,1). Giải thích: • Đường đi trong lần thử thứ ba này được thiết kế để đảm bảo rằng Turbo sẽ kiểm tra toàn bộ hàng 𝑖 từ ô (𝑖, 1) đến (𝑖, 2023), nếu cần thiết. • Nếu con quái vật nằm ở (𝑖, 𝑗) với 𝑗 = 𝑖 hoặc 𝑗 = 𝑖 + 1, thì Turbo sẽ tiếp tục theo đường đi này để kiểm tra tất cả các ô từ đầu hàng 𝑖 cho đến hết hàng, và sau đó di chuyển xuống hàng dưới cùng. • Nếu con quái vật nằm ở ô (𝑖, 𝑗) (với 𝑗 = 𝑖 hoặc 𝑗 = 𝑖 + 1 ), thì đường đi của Turbo trong lần thử thứ ba sẽ đảm bảo rằng ít nhất một trong các đường đi của anh ấy sẽ bao phủ con quái vật. Bây giờ, lưu ý rằng: • Các ô từ (1,2) đến (𝑖 − 1, 𝑖 − 1) không chứa quái vật vì chúng đã được viếng thăm trước khi Turbo gặp phải quái vật tại (𝑖, 𝑗) trong lần thử trước đó. • Các ô (𝑖, 𝑘) với 1 ≤ 𝑘 ≤ 𝑖 − 1 không chứa quái vật vì chỉ có một con quái vật ở hàng 𝑖, và nó nằm ở (𝑖, 𝑖) hoặc (𝑖, 𝑖 + 1). • Các ô (𝑘, 1) với 𝑖 ≤ 𝑘 ≤ 2024 không chứa quái vật vì chỉ có một con quái vật ở cột 1 , và nó nằm ở (2,1).
Do đó, Turbo sẽ thắng trong lần thử thứ ba. Bình luận: Một biến thể nhỏ trong chiến lược của Turbo khi con quái vật ở hàng thứ hai nằm ở mép là có thể thực hiện. Trong lần thử thứ hai, Turbo có thể đi theo đường sau: (1,2023) ⁡→ (2,2023) → (2,2022) → ⋯ → (2,3) → (2,2) → (2,3) → ⋯ → (2,2023) ⁡→ (3,2023) → (3,2022) → ⋯ → (3,4) → (3,3) → (3,4) → ⋯ → (3,2023) ⁡→ ⋯ ⁡→ (2022,2023) → (2022,2022) → (2022,2023) ⁡→ (2023,2023) ⁡→ (2024,2023). Nếu có quái vật trên đường đi này, giả sử ở ô (𝑖, 𝑗), thì trong lần thử thứ ba Turbo có thể đi thẳng xuống ô ngay bên trái của quái vật thay vì theo đường đi đã vạch ra trong lần thử thứ hai: (1, 𝑗 − 1) ⁡→ (2, 𝑗 − 1) → ⋯ → (𝑖 − 1, 𝑗 − 1) → (𝑖, 𝑗 − 1) ⁡→ (𝑖, 𝑗 − 2) → ⋯ → (𝑖, 2) → (𝑖, 1) ⁡→ (𝑖 + 1,1) → ⋯ → (2023,1) → (2024,1). Hình 3. Chiến lược thay thế cho Turbo trong lần thử thứ 2 và 3 Bài 6. Ký hiệu ℚ là tập các số hữu tỷ. Một hàm số 𝑓: ℚ → ℚ được gọi là đẹp nếu có tính chất sau: với mỗi 𝑥, 𝑦 ∈ ℚ, 𝑓(𝑥 + 𝑓(𝑦)) = 𝑓(𝑥) + 𝑦 hoặc ⁡𝑓(𝑓(𝑥) + 𝑦) = 𝑥 + 𝑓(𝑦).
Chứng minh rằng tồn tại số nguyên 𝑐 sao cho với mọi hàm số đẹp 𝑓, có không quá 𝑐 số hữu tỷ phân biệt có dạng 𝑓(𝑟) + 𝑓(−𝑟), với 𝑟 là số hữu tỷ nào đó, và tìm giá trị nhỏ nhất có thể của 𝑐. Đáp án: Giá trị nhỏ nhất là 𝑐 = 2. Nhận xét chung: Giả sử 𝑓 là một hàm thỏa mãn điều kiện của bài toán. Chúng ta sẽ sử dụng các ký hiệu sau xuyên suốt tất cả các lời giải: • 𝑎 ∼ 𝑏 nếu 𝑓(𝑎) = 𝑏 hoặc 𝑓(𝑏) = 𝑎, • 𝑎 → 𝑏 nếu 𝑓(𝑎) = 𝑏, • 𝑃(𝑥, 𝑦) để biểu thị mệnh đề rằng hoặc 𝑓(𝑥 + 𝑓(𝑦)) = 𝑓(𝑥) + 𝑦 hoặc 𝑓(𝑓(𝑥) + 𝑦) = 𝑥 + 𝑓(𝑦), • 𝑔(𝑥) = 𝑓(𝑥) + 𝑓(−𝑥). Với các ký hiệu này, điều kiện 𝑃(𝑥, 𝑦) có thể được diễn giải lại là 𝑥 + 𝑓(𝑦) ∼ 𝑓(𝑥) + 𝑦, và chúng ta được yêu cầu xác định số lượng lớn nhất các phần tử của tập {𝑔(𝑥) ∣ 𝑥 ∈ ℚ}. Lời giải 1. Chúng ta bắt đầu bằng việc đưa ra một ví dụ về một hàm 𝑓 mà với hàm đó có hai giá trị của 𝑔(𝑥). Chúng ta lấy hàm 𝑓(𝑥) = ⌊𝑥⌋ − {𝑥}, trong đó ⌊𝑥⌋ là phần nguyên của 𝑥 (tức là số nguyên lớn nhất nhỏ hơn hoặc bằng 𝑥) và {𝑥} = 𝑥 − ⌊𝑥⌋ là phần thập phân của 𝑥. Trước tiên, chúng ta chứng minh rằng 𝑓 thỏa mãn 𝑃(𝑥, 𝑦). Với 𝑥, 𝑦 ∈ ℚ, chúng ta có: 𝑓(𝑥) + 𝑦 = ⌊𝑥⌋ − {𝑥} + ⌊𝑦⌋ + {𝑦} = (⌊𝑥⌋ + ⌊𝑦⌋) + ({𝑦} − {𝑥}) 𝑥 + 𝑓(𝑦) = ⌊𝑥⌋ + {𝑥} + ⌊𝑦⌋ − {𝑦} = (⌊𝑥⌋ + ⌊𝑦⌋) + ({𝑥} − {𝑦}) Nếu {𝑥} < {𝑦}, thì phần thập phân của 𝑓(𝑥) + 𝑦 là {𝑦} − {𝑥} và phần nguyên là ⌊𝑥⌋ + ⌊𝑦⌋, do đó 𝑓(𝑥) + 𝑦 → 𝑥 + 𝑓(𝑦). Tương tự, nếu {𝑥} > {𝑦}, thì 𝑥 + 𝑓(𝑦) → 𝑓(𝑥) + 𝑦. Cuối cùng, nếu {𝑥} = {𝑦}, thì 𝑓(𝑥) + 𝑦 = 𝑥 + 𝑓(𝑦) = ⌊𝑥⌋ + ⌊𝑦⌋ là một số nguyên. Trong mọi trường hợp, mệnh đề 𝑃 được thỏa mãn. Cuối cùng, chúng ta nhận thấy rằng nếu 𝑥 là một số nguyên thì 𝑔(𝑥) = 0, và nếu 𝑥 không phải là một số nguyên thì 𝑔(𝑥) = −2, vì vậy có hai giá trị cho 𝑔(𝑥) như yêu cầu. Chứng minh không có hơn hai giá trị của 𝑔(𝑥) : 𝑃(𝑥, 𝑥) cho chúng ta biết rằng 𝑥 + 𝑓(𝑥) ∼ 𝑥 + 𝑓(𝑥), hay nói cách khác, với mọi 𝑥,
𝑓(𝑥 + 𝑓(𝑥)) = 𝑥 + 𝑓(𝑥). (1) Chúng ta bắt đầu với Bổ đề sau: Bổ đề 1. 𝑓 là một song ánh, và thỏa mãn: 𝑓(−𝑓(−𝑥)) = 𝑥 (2) Chứng minh. Trước tiên chúng ta chứng minh rằng 𝑓 là hàm đơn ánh. Giả sử rằng 𝑓(𝑥1 ) = 𝑓(𝑥2 ), khi đó 𝑃(𝑥1 , 𝑥2 ) cho chúng ta biết rằng 𝑓(𝑥1 ) + 𝑥2 ∼ 𝑓(𝑥2 ) + 𝑥1 . Không mất tính tổng quát, giả sử rằng 𝑓(𝑥1 ) + 𝑥2 → 𝑓(𝑥2 ) + 𝑥1 . Nhưng 𝑓(𝑥1 ) = 𝑓(𝑥2 ), nên 𝑓(𝑓(𝑥1 ) + 𝑥2 ) = 𝑓(𝑓(𝑥2 ) + 𝑥2 ) = 𝑓(𝑥2 ) + 𝑥2 theo điều kiện (1). Do đó, 𝑓(𝑥2 ) + 𝑥1 = 𝑓(𝑥2 ) + 𝑥2 , như vậy chúng ta đã chứng minh được 𝑥1 = 𝑥2 . Bây giờ, (1) với 𝑥 = 0 cho chúng ta biết rằng 𝑓(𝑓(0)) = 𝑓(0) và do hàm 𝑓 là đơn ánh, 𝑓(0) = 0. Áp dụng 𝑃(𝑥, −𝑓(𝑥)) cho chúng ta biết rằng 0 ∼ 𝑥 + 𝑓(−𝑓(𝑥)), nên hoặc 0 = 𝑓(0) = 𝑥 + 𝑓(−𝑓(𝑥)) hoặc 𝑓(𝑥 + 𝑓(−𝑓(𝑥))) = 0 điều này dẫn tới 𝑥 + 𝑓(−𝑓(𝑥)) = 0 do tính đơn ánh của 𝑓. Dù sao, chúng ta cũng suy ra rằng 𝑥 = −𝑓(−𝑓(𝑥)), hoặc 𝑥 = 𝑓(−𝑓(−𝑥)) bằng cách thay 𝑥 bằng −𝑥. Cuối cùng, chúng ta nhận thấy rằng tính song ánh của 𝑓 suy ra ngay lập tức từ (2). Vì 𝑓 là hàm song ánh, nó có một hàm ngược, mà chúng ta ký hiệu là 𝑓 −1 . Sắp xếp lại (2) (sau khi thay 𝑥 bằng −𝑥) cho chúng ta biết rằng 𝑓(−𝑥) = −𝑓 −1 (𝑥). Chúng ta có 𝑔(𝑥) = 𝑓(𝑥) + 𝑓(−𝑥) = 𝑓(𝑥) − 𝑓 −1 (𝑥). Giả sử 𝑔(𝑥) = 𝑢 và 𝑔(𝑦) = 𝑣, trong đó 𝑢 ≠ 𝑣 và cả hai đều khác không. Định nghĩa 𝑥 ′ = 𝑓 −1 (𝑥) và 𝑦 ′ = 𝑓 −1 (𝑦); theo định nghĩa, chúng ta có: 𝑥 ′ → 𝑥 → 𝑥 ′ + 𝑢, 𝑦 ′ → 𝑦 → 𝑦 ′ + 𝑣. Thay vào 𝑃(𝑥 ′ , 𝑦) cho chúng ta biết 𝑥 + 𝑦 ∼ 𝑥 ′ + 𝑦 ′ + 𝑣, và thay vào 𝑃(𝑥, 𝑦 ′ ) cho chúng ta biết 𝑥 + 𝑦 ∼ 𝑥 ′ + 𝑦 ′ + 𝑢. Những điều này không bằng nhau vì 𝑢 ≠ 𝑣, và 𝑥 + 𝑦 chỉ có thể có một mũi tên đi vào và đi ra vì 𝑓 là hàm song ánh, nên chúng ta phải có hoặc 𝑥 ′ + 𝑦 ′ + 𝑢 → 𝑥 + 𝑦 → 𝑥 ′ + 𝑦 ′ + 𝑣 hoặc ngược lại. Thay đổi (x, u) và (y, v) nếu cần thiết, chúng ta có thể giả sử không mất tính tổng quát rằng đây là hướng đúng của các mũi tên. Ngoài ra, chúng ta có −𝑥 ′ − 𝑢 → −𝑥 → −𝑥 ′ theo Bổ đề 1 . Thay vào 𝑃(𝑥 + 𝑦, −𝑥 ′ − 𝑢) cho chúng ta biết 𝑦 ∼ 𝑦 ′ + 𝑣 − 𝑢, và vì vậy 𝑦 ′ + 𝑣 − 𝑢 phải là hoặc 𝑦 ′ + 𝑣 hoặc 𝑦 ′ . Điều này có nghĩa là 𝑢 phải là hoặc 0 hoặc 𝑣, và điều này mâu thuẫn với giả định của chúng ta về 𝑢 và 𝑣. Nhận xét: Bổ đề 1 cũng có thể được chứng minh như sau. Chúng ta bắt đầu bằng việc chứng minh rằng 𝑓 phải là hàm toàn ánh. Giả sử ngược lại; khi đó, phải có một số 𝑡 không xuất hiện trong kết quả của 𝑓. 𝑃(𝑥, 𝑡 − 𝑓(𝑥)) cho chúng ta biết rằng 𝑡 ∼ 𝑥 + 𝑓(𝑡 − 𝑓(𝑥)), và do giả định 𝑓(𝑡) = 𝑥 + 𝑓(𝑡 − 𝑓(𝑥)) cho mọi 𝑥. Nhưng đặt 𝑥 = 𝑓(𝑡) − 𝑡 cho chúng ta biết 𝑡 = 𝑓(𝑡 − 𝑓(𝑓(𝑡) − 𝑡)) , mâu thuẫn với giả định của chúng ta về 𝑡.
Bây giờ, chọn một số 𝑡 sao cho 𝑓(𝑡) = 0; một số 𝑡 như vậy phải tồn tại do tính toàn ánh. 𝑃(𝑡, 𝑡) cho chúng ta biết rằng 𝑓(𝑡) = 𝑡, hay nói cách khác 𝑡 = 0 và 𝑓(0) = 0. Phần còn lại của chứng minh giống như chứng minh trong Lời giải 1. Lời giải 2. Chúng ta lại bắt đầu với Bổ đề 1 , và nhận thấy rằng 𝑓(0) = 0 như trong chứng minh của bổ đề đó. 𝑃(𝑥, −𝑓(𝑦)) cho chúng ta biết rằng 𝑥 + 𝑓(−𝑓(𝑦)) ∼ 𝑓(𝑥) − 𝑓(𝑦), và sử dụng (2) điều này trở thành 𝑥 − 𝑦 ∼ 𝑓(𝑥) − 𝑓(𝑦). Nói cách khác, hoặc 𝑓(𝑥 − 𝑦) = 𝑓(𝑥) − 𝑓(𝑦) hoặc 𝑥 − 𝑦 = 𝑓(𝑓(𝑥) − 𝑓(𝑦)). Trong trường hợp thứ hai, chúng ta suy ra rằng: 𝑓(−(𝑥 − 𝑦)) = 𝑓(−𝑓(𝑓(𝑥) − 𝑓(𝑦))), 𝑓(𝑦 − 𝑥) = 𝑓(−𝑓(𝑓(𝑥) − 𝑓(𝑦))) = 𝑓(𝑦) − 𝑓(𝑥). Do đó, 𝑓(𝑦) − 𝑓(𝑥) bằng hoặc 𝑓(𝑦 − 𝑥) hoặc −𝑓(𝑥 − 𝑦). Thay 𝑦 bằng 𝑥 + 𝑑, chúng ta suy ra rằng 𝑓(𝑥 + 𝑑) − 𝑓(𝑥) ∈ {𝑓(𝑑), −𝑓(−𝑑)}. Bây giờ, chúng ta chứng minh khẳng định sau. Khẳng định: Với bất kỳ 𝑛 ∈ ℤ>0 và 𝑑 ∈ ℚ, chúng ta có rằng hoặc 𝑔(𝑑) = 0 hoặc 𝑔(𝑑) = ±𝑔(𝑑/𝑛). Đặc biệt, nếu 𝑔(𝑑/𝑛) = 0 thì 𝑔(𝑑) = 0. Chứng minh. Trước tiên, chúng ta chứng minh rằng nếu 𝑔(𝑑/𝑛) = 0 thì 𝑔(𝑑) = 0. Giả sử rằng 𝑔(𝑑/𝑛) = 0. Khi đó, 𝑓(𝑑/𝑛) = −𝑓(−𝑑/𝑛) và do đó 𝑓(𝑥 + 𝑑/𝑛) − 𝑓(𝑥) = 𝑓(𝑑/𝑛) với mọi 𝑥. Áp dụng điều này lặp lại, chúng ta suy ra rằng 𝑓(𝑥 + 𝑑) − 𝑓(𝑥) = 𝑛𝑓(𝑑/𝑛) với mọi 𝑥. Áp dụng điều này với 𝑥 = 0 và 𝑥 = −𝑑 và cộng lại, chúng ta có 𝑓(𝑑) + 𝑓(−𝑑) = 0, vì vậy 𝑔(𝑑) = 0, và đặc biệt khẳng định này đúng bất cứ khi nào 𝑔(𝑑) = 0. Bây giờ, chọn 𝑛 ∈ ℤ>0 và 𝑑 ∈ ℚ sao cho 𝑔(𝑑) ≠ 0, và nhận thấy rằng chúng ta phải có 𝑔(𝑑/𝑛) ≠ 0. Nhận thấy rằng với mọi 𝑘 ∈ ℤ chúng ta có rằng 𝑓(𝑘𝑑/𝑛) − 𝑓((𝑘 − 1)𝑑/𝑛) ∈ {𝑓(𝑑/𝑛), −𝑓(−𝑑/𝑛)}. Để 𝐴 𝑖 là số lượng 𝑘 ∈ ℤ với 𝑖 − 𝑛 < 𝑘 ≤ 𝑖 sao cho sự khác biệt này bằng 𝑓(𝑑/𝑛). Chúng ta suy ra rằng với mọi 𝑖 ∈ ℤ : 𝑓(𝑖𝑑/𝑛) − 𝑓(𝑖𝑑/𝑛 − 𝑑) = ∑ (𝑓(𝑘𝑑/𝑛) − 𝑓((𝑘 − 1)𝑑/𝑛)) = 𝐴 𝑖 𝑓(𝑑/𝑛) − (𝑛 − 𝑖−𝑛