HMMT 十一月 2017 · 冲刺赛 · 第 16 题

HMMT November 2017 — Guts Round — Problem 16

[ 7 ] A repunit is a positive integer, all of whose digits are 1s. 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 1s. 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 Proposed by: Michael Tang Answer: 1223456 Let { r } be the repunits (so r = 1, r = 11, and so on). We see that for any n , there is n n ≥ 0 0 1 r r r n n n r + r + · · · + r < + + · · · < < r , n − 1 n − 2 0 n 10 100 9 n so r is only needed when all possible combinations of the first n repunits are exhausted (after 2 n terms), which shows that there is a bijection between the sequence { a } and the binary numbers. n n n n 1 2 s In particular, if k = 2 + 2 + · · · + 2 for distinct n ’s, then a = r + r + · · · + r . Since i k n n n 1 2 s 0 1 2 3 5 6 111 = 1101111 = 2 + 2 + 2 + 2 + 2 + 2 , we have 2 a = r + r + r + r + r + r = 1223456 . 111 0 1 2 3 5 6