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 number i i of digits in m (in base 10), then n + n + · · · + n = N . Let p denote the fraction of the first M 1 2 10 M positive integers that are piquant. Find lim p . M M →∞ d d − 1
解析
- A positive integer N is piquant if there exists a positive integer m such that if n denotes the number i i of digits in m (in base 10), then n + n + · · · + n = N . Let p denote the fraction of the first M 1 2 10 M positive integers that are piquant. Find lim p . M M →∞ Proposed by: James Lin 32 Answer: 55 i 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 i k 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 ≤ h i i ( m + 1) , or m < 10 ≤ m + 1 for some integer h . This means that, as we increment m by 1, h i the sum n + n + · · · + n increases when m “jumps over” 10 for i ≤ 10. Furthermore, when 1 2 10 h h 1 2 m is big enough, all “jumps” are distinguishable, i.e. there does not exist two 6 = such that i 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 h k k +1 k k +1 i from 10 to 10 is the number of different 10 in the range (10 , 10 ]. If we take the fractional j part of the exponent, this is equivalent to the number of distinct fractions 0 < ≤ 1 where 1 ≤ i ≤ 10. i The number of such fractions with denominator i is ϕ ( i ), so the total number of such fractions is ϕ (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 the 32 k k +1 range [ N (10 ) , N (10 )) are piquant. This implies that lim p = . M →∞ M 55 d d − 1