HMMT 十一月 2017 · 冲刺赛 · 第 16 题
HMMT November 2017 — Guts Round — Problem 16
题目详情
英文原题
- [ 7 ] A repunit is a positive integer, all of whose digits are 1 s. Let a < a < a < . . . be a list of all the
1 2 3
positive integers that can be expressed as the sum of distinct repunits. Compute a .
111
解析
英文解析
- [ 7 ] A repunit is a positive integer, all of whose digits are 1 s. Let a < a < a < . . . be a list of all the
1 2 3
positive integers that can be expressed as the sum of distinct repunits. Compute a .
Proposed by: Michael Tang 111
Answer: 1223456
Let { r } be the repunits (so r = 1, r = 11, and so on). We see that for any n , there isn n ≥ 0 0 1
r r rn n nr + r + · · · + r < + + · · · < < r ,
n − 1 n − 2 0 n
10 100 9
so r is only needed when all possible combinations of the first n repunits are exhausted (after 2 nnterms), which shows that there is a bijection between the sequence { a } and the binary numbers.
n n nn
1 2 s
In particular, if k = 2 + 2 + · · · + 2 for distinct n ’s, then a = r + r + · · · + r . Sincei k n n n
1 2 s
0 1 2 3 5 6
111 = 1101111 = 2 + 2 + 2 + 2 + 2 + 2 , we have a = r + r + r + r + r + r = 1223456 .2
111 0 1 2 3 5 6