You have 1000 bottles of wine but one of them is poisoned Yo

You have 1000 bottles of wine but one of them is poisoned! You want to find out exactly which bottle is poisoned. To do this, you have access to an unlimited number of prisoners that you can feed wine to. If a prisoner drinks from the bottle that is poisoned, they will die after 24 hours. Prisoners are also allowed to drink from multiple bottles. Assuming that the amount of wine and prisoners is unlimited, what is the least number of prisoners needed to identify the exact bottle that is poisoned within 24 hours?

Solution

This is a very common \"puzzle\". Let us suppose minimum number of prisoners are n. Since after 24 hours, a prisoner is either dead or alive, there are total of 2^n different outcomes, and this number should be just larger than 1000 so that we can create a mapping between the two. Thus we solve for minimum integer n such that 2^n > 1000, and we find 2^10 > 1024. Thus, we need atleast 10 prisoners to identify exact bottle.

In fact, we can create a mapping: number all bottles from 1 to 1000, and write its binary code (10 digits long), for exacaple, for bottle #3, code is 0000000011, now for each \"1\" position in each binary code, make corresponding prisoner drink a sip of that wine. For example, wine #3 will be given both prisoner number 9 and 10. Now, after 24 hours, the sequence of dead and alive prisoners will pin point exact poisoned bottle number in binary code (1 = dead, 0 = alive).