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 Nnfor which the last two digits in the decimal representation of a is the same for all n ≥ N ?2
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
for which the last two digits in the decimal representation of a 2 n
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 Nnfor which the last two digits in the decimal representation of a is the same for all n ≥ N ?2
Proposed by: Pakawut Jiradilok
Answer: 36
Solution 1. It suffices to consider the remainder mod 100. We start with the four numbers that havethe same last two digits when squared: 0, 1, 25, 76.
We can now go backwards, repeatedly solving equations of the form x ≡ n (mod 100) where n is a 2
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
2100
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 arecoprime to 5, we may use the existence of a primitive root to equivalently ask for how many elementsof Z the map y 7 → 2 y reaches a fixed point. The only fixed point is 0, so the only valid choices are the multiples of 5 again. There are 5 + 4 = 9 solutions here.20
Finally, the number of solutions modulo 100 is 4 × 9 = 36.