HMMT 十一月 2017 · THM 赛 · 第 5 题
HMMT November 2017 — THM Round — Problem 5
题目详情
- E ach of the integers 1 , 2 , . . . , 729 is written in its base-3 representation without leading zeroes. The numbers are then joined together in that order to form a continuous string of digits: 12101112202122 . . . . How many times in this string does the substring 012 appear?
解析
- E ach of the integers 1 , 2 , . . . , 729 is written in its base-3 representation without leading zeroes. The numbers are then joined together in that order to form a continuous string of digits: 12101112202122 . . . . How many times in this string does the substring 012 appear? Proposed by: Michael Tang Answer: 148 6 Ignore 729 = 3 = 1000000 since it will not contribute to a 012 substring. Break into cases on how 3 012 appears: (i) when an individual integer contains the string 012; (ii) when 01 are the last two digits of an integer and 2 is the first digit of the next integer; and (iii) when 0 is the last digit of an integer and 12 are the first two digits of the next integer. For case (i), we want to find the total number of appearances of the string 012 in 1 , 2 , 3 , . . . , N . Since each number has at most six digits, 012 appears at most once per number. If such a number has d d − 4 digits, 4 ≤ d ≤ 6, then there are d − 3 possible positions for the substring 012 and 2 · 3 possible choices for the remaining digits (since the leftmost digit must be nonzero). Thus there are 6 ∑ ( ) d − 4 ( d − 3) · 2 · 3 = 1 · 2 + 2 · 6 + 3 · 18 = 68 d =4 appearances of 012 in case (i). For case (ii), we have an integer n for which n ends in 01 and n + 1 starts with 2. Then n must also start with 2. Hence it suffices to count the number of integers 1 ≤ n < N which start with 2 and end d − 3 with 01 in base three. If n has d digits, 3 ≤ d ≤ 6, then there are 3 possibilities for the middle digits, so we have 6 ∑ d − 3 3 = 1 + 3 + 9 + 27 = 40 d =3 appearances of 012 in case (ii). For case (ii), we have an integer n for which n ends in 0 and n + 1 starts with 12. Then n must also start with 12, so we want to count the number of 1 ≤ n < N starting with 12 and ending in 0. Like case (ii), there are also 40 appearances of 012 in case (iii). In total, the substring 012 appears 68 + 40 + 40 = 148 times.