## Tuesday, July 26, 2011

### In a country in which people only want boys…

…every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

This one is particularly intriguing:

a.  given that we have N families we will have N males
b.  how many kids do we have?

1, 1 boy   -> N/2 kids
10, 1 boy, 1 girl -> possible combinations are 01, 10 -> 2 * N / 4 (01 has N/4 chances)
100, 1 boy, 2 girls -> possible combinations are 3 * N / 8
1000, 1 boy, 3 girls -> possible combinations are 4 * N / 16
10000
100000

N ( 1/2 + 2/4 + 3/8 + 4/16 + ... ) ; N ( 1/2 + 2/4 +
3/8 + 4/16 +  + n / 2^n )

now that above recurrence is the one used for saying that the time for building an heap is linear (if you remember the demonstration) and this should give you an hint for the solution

1/2 + 2/4 = 1
3/8 + 4/16 + ... + n / 2^n = 1

the total number of kids is 2N

3. So the number of females must be 2N - N = N