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 20120116 17:32:25 