HMMT 二月 2019 · 冲刺赛 · 第 28 题
HMMT February 2019 — Guts Round — Problem 28
题目详情
- [ 15 ] How many positive integers 2 ≤ a ≤ 101 have the property that there exists a positive integer N n 2 for which the last two digits in the decimal representation of a is the same for all n ≥ N ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2019, February 16, 2019 — GUTS ROUND Organization Team Team ID#
解析
- [ 15 ] How many positive integers 2 ≤ a ≤ 101 have the property that there exists a positive integer N n 2 for which the last two digits in the decimal representation of a is the same for all n ≥ N ? Proposed by: Pakawut Jiradilok Answer: 36 Solution 1. It suffices to consider the remainder mod 100. We start with the four numbers that have the same last two digits when squared: 0, 1, 25, 76. 2 We can now go backwards, repeatedly solving equations of the form x ≡ n (mod 100) where n is a number that already satisfies the condition. 0 and 25 together gives all multiples of 5, for 20 numbers in total. 1 gives 1 , 49 , 51 , 99, and 49 then gives 7 , 43 , 57 , 93. Similarly 76 gives 24 , 26 , 74 , 76, and 24 then gives 18 , 32 , 68 , 82, for 16 numbers in total. Hence there are 20 + 16 = 36 such numbers in total. Solution 2. An equivalent formulation of the problem is to ask for how many elements of Z the 100 2 map x 7 → x reaches a fixed point. We may separately solve this modulo 4 and modulo 25. Modulo 4, it is easy to see that all four elements work. Modulo 25, all multiples of 5 will work, of which there are 5. For the remaining 25 elements that are coprime to 5, we may use the existence of a primitive root to equivalently ask for how many elements of Z the map y 7 → 2 y reaches a fixed point. The only fixed point is 0, so the only valid choices are 20 the multiples of 5 again. There are 5 + 4 = 9 solutions here. Finally, the number of solutions modulo 100 is 4 × 9 = 36.