Drunk Rats

The generalization of a mathematical puzzle

about some very unlucky

rodents…


You organized a party with 1000 bottles of wine but you know that 1 bottle was poisoned before the party and you don’t want anybody to die.Luckily you are in the lab and you have 10 lab rats so you decide to use them to test which bottle is poisoned.The poison takes 1 hour to take effect also the party occurs in 1 hour.

Try it your self.

shutterstock_7591453

The Solution

Number the bottles in order in binary from 12 to 11111010002 and label the rats in powers of 2 from 20 all the way to 29.Now look at bottle 1 if its binary representation has a 1 on a specific place feed 1 drop to the rat labeled that corresponding place.Repeat for all of the bottles of wine.

Wait 1 hour.

Then line the rats up starting at the left with 512 and ending with 1 on the right.

Read the rats like a binary number with dead rats as 1 and alive rats as 0, then throw away the wine numbered the rat number.This is guaranteed to work for all bottle numbers.

Here’s another problem for you:

can you figure out the minimal number of rats needed for any number of bottles?

Define a function that returns the number of rats needed given the number of bottles of wine w and the number of poisoned bottles p when p=1 and if you are following my method: f(w,1)=ceiling(log2(w))

For example if there are 1010 bottles of wine(w=10,000,000,000)you would need 34 rats to find the poisoned bottle (because 234 is the smallest power of 2 more than 1010)

Now think about the case with p=2 and w=1000 in other words when there are 1000 bottles of wine and 2 poisoned bottles…

Now its okay if you don’t get this right away(I didn’t get it either) but the number of rats needed for 1000 bottles and 2 poisoned ones is 34 and the number needed for n bottles and 2 poisoned ones is(please tell me if I am wrong):                         Ω((4*log2(w))=Ω(4*log(w)/log(2))

Included below is an algorithm that I found on the internet about how you can use 60 rats to find 2 poisoned bottles out of 1000.

The reason why stopped here is that I don’t have enough knowledge to understand it but I promise when I learn more I will re-write it.

Part-I
Let’s say there are 25 (=32) wines. Represent them using binary system using 5 bits:

A-B-C-D-E

Give wines with A=0 to one person. Give wines with A=1 to another person. Do such tests for all bits (10 tests). Let’s say you got a result like the following:

(0|1)-(0)-(1)-(0|1)-(0|1)

Bits B&C have fixed values (B=0. C=1). Bits A,D,E have two probable values each. The solution must be one from the following enumerations (Two solutions if you count both (a,b) and (b,a)). We represent the solutions in binary/decimal forms for clarity. It is easy to prove that they are just pairs of numbers with a constant sum (=27 in our case).

(00100, 10111) = (4,23)

(00101, 10110) = (5,22)

(00110, 10101) = (6,21)

(00111, 10100) = (7,20)

(10100, 00111) = (20,7)

(10101, 00110) = (21,6)

(10110, 00101) = (22,5)

(10111, 00100) = (23,4)

Part-II
Renumber the wines from (0,1,2,3,4,5 …) to (0,1,4,9,16,25 …) and put them into a bigger set of size(25)2=210=1024 (We are squaring the numbers). Only 32 of the 1024 will be actual wines. Fill the rest of them with water.

Repeat the tests similar to that ones from Part-I on this bigger set (2*10=20 tests). This will give another set of solutions. Ignore all the solutions which contain water in one or both the bottles. Only the pair that matches with the corresponding pair from Part-I will be the actual solution (Two solutions if you consider duplicates).

If you get these from Part-I:

(a,b),(c,d),(e,f),(f,e),(d,c),(b,a)(a,b),(c,d),(e,f),(f,e),(d,c),(b,a)

and if you get these from Part-II:

(a2,b2),(g2,h2),(c2,i2),(i2,c2),(h2,g2),(b2,a2)(a2,b2),(g2,h2),(c2,i2),(i2,c2),(h2,g2),(b2,a2)

then the solution must be (a,b).

The reason is: Part-I satisfies x+y=c1, and Part-II satisfies x2+y2=c2. Given that x>=0 & y>=0, there is only one solution that satisfies these conditions (two solutions if you consider duplicates).

That was literally at the frontier of mathematics and anyone could try it!

Resources

http://www.cims.nyu.edu/~bandeira/2015_18.S096_7_Group_Testing.pdf

https://en.wikipedia.org/wiki/Group_testing

http://mathoverflow.net/questions/59939/identifying-poisoned-wines/60312#60312

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s