Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
The sophisticated birth controling strategy is amazing deciever - while being totally irrelevant.
Yes, that's what makes it a brain teaser, that facepalm moment when you realize no calculation is necessary; each birth is an independent Bernoulli trial and half of all children born will be boys, no matter what each couple's criterion is for stopping.
The question asks that for 20 years. Thus, I am not sure whether it is close to 50:50, or exactly 50:50. The expectation for number of boy is Sum(k * pow(0.5, k) * 0.5), 0 <= k < 20. then we could resolve it, and finally we have Sum = 0.5 * (1-pow(0.5, 19)) / 0.5 = 1- pow(0.5, 19), which is expectation of boy's number. For the girl, the expectation is 1 intuitively. So the ratio is 1 - pow(0.5, 19) : 1. Let me know if I was wrong. Thanks.
Victor, I disagree. How many births there were on this island in these 20 years? Let's say you answer is 12345. Out of these 12345 births, each had equal 50/50 chance.
When I thought about this problem, I though is there any cooperative strategy to change 50/50. I thought about community that wants to have more boys than girls and decided to give birth untill there is one more boy than a girl - and stop in order not to equalize it. Even this will not help.
I asked this modified problem to not so well educated locksmith who is known to be puzzle lover. He was very uncomfortable with the statement "What is the boy to girl ratio in 20 years" - he said we cannot know because this is just probabilistic. I thought that he is correct, and the more proper question is "What is the most likely boy to girl ratio in 20 years"? He reacted that "most likely boy to girl ratio" is equivalent to "a chance of giving birth to boy vs girl"
It is 50/50 based on odds, since every birth is independent thing.
Since this is brain teaser, you won't get 100 points if you only answer this.
The boy/girl number is even in total. But those families with multiple children will likely have more boys than girls. It is a fact that, with fixed income, the more children you have, the less you can support for each child. So on average the education, medical care for each boy is lower than each girl. As a result of natural death of disease, boys have more fatal rates. So in 20 years, the number of girls should be larger than boys.
There is a 1/2 chance that a couple will have a girl on the first try, 1/4 after 2 tries, 1/8 after 3 tries, etc. Therefore the probability a couple has n children is given by:
P(n) = 1/2^n
This can be seen by looking at the possible outcomes of boy and girl births. For example for 2 tries the possible outcomes are:
BB
BG
GB
GG
Only 1 of these 4 is possible and results in a girl on the 2nd try, because the couple stops once they have a girl. Therefore the probability of a couple having 2 children is 1/4.
The average number of children per couple is given by:
a = 1*P(1) + 2*P(2) + ... n*P(n) = 1/2 + 2/4 + ... n/2^n
This geometric series sums to 2, therefore the average number of kids per couple is 2. Since every couple has at least 1 girl, the ratio of boys to girls is 1.
"Since every couple has at least 1 girl" is a false statement because some will not have a chance due to time limit.
The thing is I cannot figure out which one will be slightly more. From one side 20 years may not be enough time to converge close enough to 1:1. From the other side, the will be girl missing in long, less probable sibling sequences.
What are we talking about, universally every birth is 50/50 and no per-family birth control strategy can possibly change this.
Heh, ya, I was fooled too. I think I just wanted to practice a probability problem. In the end, all I calculated is the average number of children per couple given an infinite amount of time; which is irrelevant. Good practice though. I hadn't thought through that line of reasoning in a while.
Assume a couple can have one baby per year. 500 couples will have a girl in the first year and stop. 250 couples will have a boy and a girl and stop. 250 couples will have two boys. At the end of two years we have 750 girls and 750 boys.
Remaining 250 couples will continue with the same loop and at the end of each 2 years we will have the same number of boys and girls.
Assumption in the beginning is just for clarification. Eventually, number of girls and boys will be the same at the end of some interval.
50 / 50
- Anonymous October 30, 2014