HMMT 二月 2020 · ALGNT 赛 · 第 5 题
HMMT February 2020 — ALGNT Round — Problem 5
题目详情
英文原题
- A positive integer N is piquant if there exists a positive integer m such that if n denotes the numberiof digits in m (in base 10), then n + n + · · · + n = N . Let p denote the fraction of the first Mi
1 2 10 Mpositive integers that are piquant. Find lim p .
M →∞Md d − 1
解析
英文解析
- A positive integer N is piquant if there exists a positive integer m such that if n denotes the numberiof digits in m (in base 10), then n + n + · · · + n = N . Let p denote the fraction of the first Mi
1 2 10 Mpositive integers that are piquant. Find lim p .
M →∞M
Proposed by: James Lin
Answer:32
i 55
Solution: For notation, let n ( m ) denote the number of digits of m and N ( m ) = n ( m ) + n ( m ) +
i 1 2
· · · + n ( m ). Observe that n (10 m ) = n ( m ) + i so N (10 m ) = N ( m ) + 55. We will determine, for
10 i ik k +1
k → ∞ , how many of the integers from N (10 ) to N (10 ) − 1, inclusive, are piquant.
k k +1 i i h
Increment m by 1 from 10 to 10 . The number of digits of m increases by one if m < 10 ≤
( m + 1) , or m < 10 ≤ m + 1 for some integer h . This means that, as we increment m by 1,iihhthe sum n + n + · · · + n increases when m “jumps over” 10 for i ≤ 10. Furthermore, wheni
1 2 10
h h
1 2
m is big enough, all “jumps” are distinguishable, i.e. there does not exist two 6 = such thati i
1 2
h /i h /i
1 1 2 2
m < 10 < 10 ≤ m + 1.
Thus, for large k , the number of times n ( m ) + n ( m ) + · · · + n ( m ) increases as m increments by 1
1 2 10
k k +1 k k +1 hifrom 10 to 10 is the number of different 10 in the range (10 , 10 ]. If we take the fractionaljpart of the exponent, this is equivalent to the number of distinct fractions 0 < ≤ 1 where 1 ≤ i ≤ 10.
The number of such fractions with denominator i is ϕ ( i ), so the total number of such fractions isiϕ (1) + ϕ (2) + · · · + ϕ (10) = 32.
k +1 k
We have shown that for sufficiently large k , N (10 ) − N (10 ) = 55 and exactly 32 integers in thek k +132
range [ N (10 ) , N (10 )) are piquant. This implies that lim p = .
M →∞ Md d − 155