PUMaC 2016 · 团队赛 · 第 6 题

PUMaC 2016 — Team Round — Problem 6

(5) Compute the sum of all positive integers less than 100 that do not have consecutive 1s in their binary representation.

解析

This is the same as the sum of all 7-digit binary sequences with no consecutive 1s. We note that the number of d -digit binary sequences with this property goes 2, 3, 5, 8, 13 for d = 1 , 2 , 3 , 4 , 5; let n ( d ) represent this sequence. Let f ( d ) be the sum-sequence. Then f (1) = 1, f (2) = 3, and for d > 2, we have f ( d ) = 4 f ( d − 2) + n ( d − 2) + n ( d − 1) (the first two terms are if the sequence we’re adding in ends in a 1 and the last term is if it ends in a 0). Evaluating this for d = 3 , 4 , 5 , 6, and, finally, 7, gives f (7) = 1389 , as desired. Problem written by Eric Neyman.