f(n) represents the sum of the digits of the binary representation of n, where n is a positive integer with 1 ≤ n ≤ 2012.

Determine the probability that f(n) ≥ 3. What is the probabiliy that f(n) ≥ 4?

2012 in binary is 11111011100 so we have no problems with having the number begin with 111

Every number in binary has at least one 1, there are eleven that have exactly one: 1, 10, 100, 1000, ..., 10000000000

To count the ways with exactly two just count the zeroes in the above list: 0+1+2+3+...+10 = 55

To count the ways with exactly three, you have to count the ways of replacing two of the zeroes with ones in the same list: 0+0+1+3+6+10+15+21+28+36+45 = 165

So P(f(n)≥3)=1 - P(f(n)<3) = 1 - (11+55+165)/2012 = 1781/2012

To count the ways with exactly four, we need to replace three of the zeroes with ones in the same list:
0+0+0+1+5+15+35+70+126+210 = 462

So P(f(n)≥4)=1 - P(f(n)<4) = 1 - (11+55+165+462)/2012 = 1781/2012 = 1319/2012

Posted by Jer on 2012-01-16 17:32:25