Please comment your solutions, questions and remarks..
Imagine that you have one thousand bottles in front of you. You know that one of them is filled with poison and others with water, but you do not know which one is the poisoned one. The poison doesn’t look or smell different. Apart from that, you have ten bunnies with the following property: if you give a drop of the poison to a bunny, then the bunny will die at midnight. Describe, how would you find out — for sure — in which bottle the poison is, by midnight.
The image is free.
something involving binary search?
2^10 is roughly 1000…
You are close.
so you need to learn about 1-bit of information about the system for each bunny you use.
which probably means feeding about 500drops to each bunny, and selecting the bottles from which those drops come smartly so at midnight we have a row of bunnies from the MSB to the LSB and can read off the poison dead/alive 0/1 bit-pattern…
Something like that I guess, although the acronyms are not familiar to me. Anyway the solution can be presented in a much simpler way. ;)
You index the bottles one-to-one with collections of bunnies. (As someone noted, 2 to 10 is greater than 1000). Then the set of dead bunnies determines a unique bottle.
However, I must say, that you are a horrible, horrible person. How can you even consider giving poison to furry little bunnies.
Reformulate: suppose you are a bunny and you have 1000 carrots and ten vampires. One of the carrots is Different. The touch of The Different Carrot turns a vampire into a were wolf by midnight.
The basic problem is simple but what about the following version: There are N carrots of which k are “special”, and M vampires. The touch of a special carrot turns a vampire into a werewolf by midnight with probability p (given in the input).
What’s the best you can do with p=0.99, p=0.5 and p=0.01. Note that only one touch per vampire-carrot pair allowed, otherwise a trivial solution would be the same as the original problem but redo each touch a lot of times to get an exponentially low probability for the turning not happening…