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. Thenumbers 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. Thenumbers 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
Ignore 729 = 3 = 1000000 since it will not contribute to a 012 substring. Break into cases on how 6
012 appears: (i) when an individual integer contains the string 012; (ii) when 01 are the last two digits 3
of an integer and 2 is the first digit of the next integer; and (iii) when 0 is the last digit of an integerand 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 . Sinceeach number has at most six digits, 012 appears at most once per number. If such a number has dd − 4
digits, 4 ≤ d ≤ 6, then there are d − 3 possible positions for the substring 012 and 2 · 3 possiblechoices 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 alsostart with 2. Hence it suffices to count the number of integers 1 ≤ n < N which start with 2 and endd − 3
with 01 in base three. If n has d digits, 3 ≤ d ≤ 6, then there are 3 possibilities for the middledigits, 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 alsostart with 12, so we want to count the number of 1 ≤ n < N starting with 12 and ending in 0. Likecase (ii), there are also 40 appearances of 012 in case (iii).
In total, the substring 012 appears 68 + 40 + 40 = 148 times.