Problem:
For positive integers , denote by the number of pairs of different adjacent digits in the binary (base two) representation of . For example, , and . For how many positive integers less than or equal to does
Answer Choices:
A.
B.
C.
D.
E.
Solution:
In order that , the binary representation of must consist of a block of 's followed by a block of 's followed by a block of 's. Among the integers with -digit binary representations, how many are there for which If the 's block consists of just one , there are possible locations for the . If the block consists of multiple 's, then there are such blocks, since only the first and last places for the 's need to be identified. Thus there are values of with binary digits such that . The binary representation of has seven digits, so all the -, -, -, and -digit binary integers are less than . (We need not consider the - and -digit binary integers.) The sum of the values of for , and is . We must also consider the -digit binary integers less than or equal to . If the initial block of 's contains three or more 's, then the number would be greater than ; by inspection, if there are one or two 's in the initial 's block, there are respectively five or one acceptable configurations of the 's block. It follows that the number of solutions of within the required range is .
Note that holds exactly when the binary representation of consists of an initial block of 's, followed by a block of 's, and then a final block of 's. The number of nonnegative integers for which is thus , since for each , the corresponding binary representation is given by selecting the position of the leftmost bit in each of the three blocks. If , the binary representation of is either or . Consider those 's for which . By the same argument as above, there are three of type , namely , , and . There are of type . It follows that the number of solutions of for which is .