distribution probability question involving binary functions for certain n<2^10

Question

For any positive integer n, let G(n) be the number of pairs of adjacent bits in the binary representation of n which are different. For example, G(10)=3 because the bits of $1010_2$ change at all three places and G(12)=1 because the bits of $1100_2$ change only from the fours to the twos place.

For how many positive integers $n<2^{10}$ is it true that G(n)=2?

Can someone give me any hints or point me in the right direction? I am supposed to use distribution.

Thanks.

Answer 1

It looks like you don't consider leading zeroes, so the first digit of a number will always be an 1. If $G(n)=2$, then the last digit is 1 too.

Now imagine that you extend all of your $n$s with leading zeroes until it has exactly 11 bits. The first bit will be 0, and the bit will change three times if $G(n)=2$.

Now there are ten possible places where the bit can change. Will every choice of three of these places (together with the rule that the first bit is 0 and the last is 1) lead to a distinct number with $G(n)=2$?

Answer 2

You have ten bits and two "barriers": the digit changes when you hit a barrier. So you have to place two barriers within 2 of 9 possible slots. (A barrier can't be at the very end of the number, nor before the beginning. For an $n$ bit number (starting with first bit $1$) we thus have $\binom{n-1}{2}$.

But be careful of two things: The two barriers can't touch (that subtracts off $n-1$. And if the number is less than $2^9$ it is only $9$ bits and so forth, so you get a sum of these binomial coefficients.