From a Goldman Sachs Quant interview

[Andy Nguyen]

You have 10 mice and 1000 bottles of wine. You also have 24 hours before a party, and one of the bottles has been tainted with a slow acting poison, which takes 24 hours to kill a mouse. In the 24 hours you have remaining, how many bottles can you guarantee safe for human consumption (assume humans and mice react identically)? Assume the lethal dosage is insignificant relative to the size of the bottle.

 

[Lighty]

909?
divide the wine into 11 groups with each one of the mice assigned to one of the group and leave one unassigned.

 

[Marcos Paterson]

999

 

[darth]

999

All bottles numbered using binary digits.Assign each mice to one of the binary flags. 1024 bottles can be tested.

 

[Lighty]

hmm.. i thought about it too but i dont think its right.
suppose we have 2 mice and you are saying that 4 bottles can be tested.
the bottles are numbered as follows
(0,0) (0,1) (1,0) (1,1)
no matter how you assigned you wont be able to find the exact bottle, since the test result will only come out after 24 hours which means you can't make decisions based on the result of your previous decision

 

[Lighty]

All bottles numbered using binary digits.Assign each mice to one of the binary flags. 1024 bottles can be tested.

its not like the mouse dies immediately and you weed out half of your sample and use the mice left only for the other half.
does it make sense?

 

[Ilya W]

hmm.. i thought about it too but i dont think its right.
suppose we have 2 mice and you are saying that 4 bottles can be tested.
the bottles are numbered as follows
(0,0) (0,1) (1,0) (1,1)
no matter how you assigned you wont be able to find the exact bottle, since the test result will only come out after 24 hours which means you can't make decisions based on the result of your previous decision

Hey Lighty, darth is right, let say 1st mice drink from 1st bottle, 2nd from second, and both of them from third. So you can check three bottles, but if after 24 hour none of mice is dead it means that poisoned bottle was 4th one it is indeed 2^n power problem, I got similar on my interview long time ago

 

[Lighty]

Hey Lighty, darth is right, let say 1st mice drink from 1st bottle, 2nd from second, and both of them from third. So you can check three bottles, but if after 24 hour none of mice is dead it means that poisoned bottle was 4th one it is indeed 2^n power problem, I got similar on my interview long time ago

that make sense! you are totally right.
I was heading a wrong direction.
thanks =)

 

[satyag]

You have 10 mice and 1000 bottles of wine. You also have 24 hours before a party, and one of the bottles has been tainted with a slow acting poison, which takes 24 hours to kill a mouse. In the 24 hours you have remaining, how many bottles can you guarantee safe for human consumption (assume humans and mice react identically)? Assume the lethal dosage is insignificant relative to the size of the bottle.

Name the mice as 0 to 9 (bit 0 to 9)
Number the bottles as 1 to 1000.
For each bottle n, get the binary representation of n, you will get a bit mask of mice that should be fed with a lethal dose from that bottle.
The bit mask of dead mice (dead=1, live=0) after 24hrs give you the number of the tainted bottle.

The answer : all 1000 bottles.

 

[pruse]

you mean 999; one of them is surely poisoned.