2

The question is:

You have 1000 bottles of wine for a birthday party. 20 hours before the party, the winery indicate 1 bottle of wine is filled with poison, without telling you which bottle. You have 10 lab mice to test this on. The poison is so strong that it'll take only 18 hours to kill the mice who drinks it. Is there a way that you can find the poisoned bottle using the 10 mice before the party.

Now, the part I am confused on is not the solution to this problem, but actually a solution to a slightly different problem (essentially where you have unlimited time to perform the testing) that the author of the question included in answering this question.

The alluded to solution states:

If the mice can be tested sequentially to eliminate half of the bottles each time, the problem becomes a simple binary search problem. Ten mice can identify the poisonous bottle in up to 1024 bottles of wine.

I am confused about the first sentence. How can the mice be tested sequentially to eliminate half of the bottles?

24n8
  • 1,455

1 Answers1

2

That solution assumes plenty of time for testing. Sequentially would mean to test a mouse with the first half of the bottles, wait to see if it lives, and then test the next mouse with either half of the first half or half of the second half, wait again, etc, but that takes far too much time for the problem you stated.

The solution for your problem requires simultaneous testing on all ten mice. Label the bottles in binary. Feed the first mouse from all of the bottles with a 1 in the 1's place. Feed the second mouse from all of the bottles with a 1 in the 2's place, and so on. The survival or not of each mouse gives a digit of the poisoned bottle's number.

RobertTheTutor
  • 7,415
  • 2
  • 10
  • 34
  • Right, so I do understand what it's saying, but I don't understand why, when assuming you have unlimited time, you would approach it that way. For example, why not just have the first mouse drink all 1000 bottles and observe which one kills it? – 24n8 Mar 16 '21 at 00:58
  • Sure, if you have endless time, one mouse is sufficient. But if you don't want to take forever, you might go with that approach as it will take at most 180 hours instead of at most 18000. – RobertTheTutor Mar 16 '21 at 01:00
  • Ah I see, but if we use the "binary search" approach where mice #1 drinks 500 bottles, mice number 2 drinks 250 bottles (assuming mice #1 hasn't died yet), mice number 3 drinks 125 bottles (assuming mice #1 & #2 haven't died yet), etc... how does this actually tell us which bottle has the poison? It would only tell us if there's a single bottle tested on a mouse and that mouse dies. But if you have multiple bottles and give it to the mouse simultaneously and the mouse dies, you don't know which one of the bottles killed it, right? – 24n8 Mar 16 '21 at 01:03
  • No each mouse drinks from 512 bottles. There is repeated sampling. – RobertTheTutor Mar 16 '21 at 01:10
  • Here's where I went totally wrong. I thought a mouse can either drink a WHOLE bottle or none at all. I didn't know a mouse can take a sip from a bottle, which would allow multiple mice to drink from the same bottle. Now this all makes sense. – 24n8 Mar 16 '21 at 01:12