[bushindo]

Suppose that you are a prisoner on the death row. The warden offers you a chance for freedom through a game.

The game is as follows:

1) The warden shows you an array of 30 identical beakers, each containing an identical amount of clear fluid.

2) You are told that 28 beakers contain simply water. 2 beakers (you don't know which ones) contain deathly poisons which can render death in exactly 1 minute.

3) You are offered 10 live rats and 10 empty flasks. You can take turn testing for poison using the rats.

4) At each turn, you must mix fluids from any number of the 30 beakers into one of the flasks. Once done, you can feed that mixture to a rat, wait 1 min, and see if it dies or not. Only 10 turns are allowed (you can not reuse flasks or rats).

5) Assume that the poisons are sufficiently powerful that even the most minuscule amount in a mixture is sufficient to kill a rat in exactly 1 minute. Also, the poisons are very odd in that while each of them is very deathly alone, mixing them together (in any proportion) in the same flask will render the mixture completely harmless.

The goal is to identify the 2 beakers containing the poison at the end of 10 turns. If you are correct, you will be set free. If not, you'll be forced to drink 10 random beakers from the 30 =).

Find a strategy that is guaranteed to correctly identify the 2 poisoned beakers.

Edited April 7, 2011 by bushindo

[Guest]

Mix 'em all together! you wont find the answer

but you can at least survive(you're cobining the poisons so they are useless.)

[Guest]

Divide the 30 beakers into three groups of 10 labeled 'A', 'B', and 'C'.

Combine all flasks in 'A' and all flasks in 'B' for test '1', all flasks in 'B' and 'C' for test '2', and all flasks in 'A' and 'C' for '3'.

The possible results should be:

• '1' & '2' Killed
  
• '2' & '3' Killed
  
• '1' & '3' Killed
  
• None Killed
  

If '1' and '2' are killed, then one flask of poison is in group 'A' and one is in group 'C'.

If '2' and '3' result in death, then the poison is in 'A' and 'B'.

If '1' and '3' are fatal, then the poison is in 'B' and 'C'.

If none of the tests are fatal, then both flasks of poison are in the same group, but we have not yet determined if they are in 'A', 'B', or 'C'.

*EDIT* This will leave 7 rats and empty flasks for additional testing.

Edited April 7, 2011 by tamjap

[Guest]

But if you make 5 groups, called A through E, from consecutive beakers such as (1,2,3,4,5,6), (7,8,9,10,11,12), etc., and then another five groups, called I through V, of (1,7,13,19,25), (2,8,14,20,26), etc. You have 10 groups now, and you test all 10. Of the second group, you didn't test 6,12,18, etc. Now, if A kills, you know you have poison in one of 1 through 6. Combined with which of I through V kill, you can pinpoint the poison. Now, for the 2nd poison. If both I and II kill, yet none of A through E do, then you know it's 1 and 2, 7 and 8, 13 and 14, 19 and 20, or 25 and 26. Hmmmmm. Time to think some more! And I didn't even address not testing the others and what nothing killing means. Arg!

[EventHorizon]

I think I've got a strategy that only requires 6 tests. I may be overlooking something, but I'll flush out the idea completely and report back.

--correction, 9 tests. I was overlooking something

Edited April 8, 2011 by EventHorizon

[witzar]

How about using dodecahedron?

It has 20 vertices, so let's put one beaker into each vertex.

It also has 12 faces, but let's remove two opposite faces.

Now each out of remaining 10 faces represents a test.

To perform each test we use five beakers that are in vertices of the face representing this test.

If result of the test is positive (rat dies), we paint the face representing test black (a color of death).

If result of the test is negative (rat lives), we paint the face white (a color of life).

After all tests are performed our dodecahedron (without two faces) will be painted in black and white.

Will it be always possible to determine poisoned beakers from the way dodecahedron is painted?

[EventHorizon]

First, add in two beakers of water (simpler explanation)

Second, kill one rat for fun. Mwaahaha. Or let it go (added in case PETA is watching...).

Third, since 32 is 2^5, do 5 tests of mixing 16 beakers. This will be done in the regular binary fashion. One possibility listed below:

Test 1: Odds

Test 2: 1-2,5-6,9-10,13-14,17-18,21-22,25-26,29-30

Test 3: 1-4,9-12,17-20,25-28

Test 4: 1-8,17-24

Test 5: 1-16

(Notice that at least 1 test must end up with a dead rat (i.e., you cannot have both poisons in each of the tests that has any poison, and only 1 beaker is left untested (32)).)

Fourth, choose one of the tests that killed a rat, and do a binary search through it for the poison. This will take 4 tests since 2^4 is 16 and the original test had 16 mixed beakers.

Fifth.... oh no! no more rats to test! That's ok, we know where one of the beakers of poison is, so toggle the results from the first 5 tests that contain the poison we know of, and it will give you the location to the other beaker of poison.

Example:

Test 1: dead = 1

Test 2: live = 0

Test 3: live = 0

Test 4: dead = 1

Test 5: dead = 1

We found the poison in beaker 17 (just chosen arbitrarily). 17 was used in tests 1-4, so toggling those tests results in:

Test 1: toggled = 0

Test 2: toggled = 1

Test 3: toggled = 1

Test 4: toggled = 0

Test 5: dead = 1

So, what number was in test {2,3,5} and not in {1,4}? 10!

So the poisons were in beakers 17 and 10.

If I would have set up the tests differently, it would have been simpler to find the last beaker (adding powers of two), but I'll leave that as an exercise to the reader.(i.e., me == lazy)

Though I will give a (lazy) proof of the claim that at least 1 test will kill a rat.

Since the position of the poison is essentially a set of the tests that get toggled due to it being poisoned, having two poisoned beakers and all tests with live rats means that the two binary positions (set of tests resulting in dead rats) of the two poisoned beakers would need to be identical since they toggled the exact same tests. Since that cannot be, and we know there are 2 unique ones, there must be at least 1 test of the first 5 resulting in a dead rat.

Edit:: Perhaps the extra rat could be a check at the end to make sure the warden isn't trying to trick you by having 3 or 1 poisoned beaker. Those evil wardens...

Anyone see a mistake?

Edited April 8, 2011 by EventHorizon

[EventHorizon]

How about using dodecahedron?

It has 20 vertices, so let's put one beaker into each vertex.

It also has 12 faces, but let's remove two opposite faces.

Now each out of remaining 10 faces represents a test.

To perform each test we use five beakers that are in vertices of the face representing this test.

If result of the test is positive (rat dies), we paint the face representing test black (a color of death).

If result of the test is negative (rat lives), we paint the face white (a color of life).

After all tests are performed our dodecahedron (without two faces) will be painted in black and white.

Will it be always possible to determine poisoned beakers from the way dodecahedron is painted?

That looks like it should work, except there are 30 beakers and not 20.

[bushindo]

First, add in two beakers of water (simpler explanation)

Second, kill one rat for fun. Mwaahaha. Or let it go (added in case PETA is watching...).

Third, since 32 is 2^5, do 5 tests of mixing 16 beakers. This will be done in the regular binary fashion. One possibility listed below:

Test 1: Odds

Test 2: 1-2,5-6,9-10,13-14,17-18,21-22,25-26,29-30

Test 3: 1-4,9-12,17-20,25-28

Test 4: 1-8,17-24

Test 5: 1-16

(Notice that at least 1 test must end up with a dead rat (i.e., you cannot have both poisons in each of the tests that has any poison, and only 1 beaker is left untested (32)).)

Fourth, choose one of the tests that killed a rat, and do a binary search through it for the poison. This will take 4 tests since 2^4 is 16 and the original test had 16 mixed beakers.

Fifth.... oh no! no more rats to test! That's ok, we know where one of the beakers of poison is, so toggle the results from the first 5 tests that contain the poison we know of, and it will give you the location to the other beaker of poison.

Example:

Test 1: dead = 1

Test 2: live = 0

Test 3: live = 0

Test 4: dead = 1

Test 5: dead = 1

We found the poison in beaker 17 (just chosen arbitrarily). 17 was used in tests 1-4, so toggling those tests results in:

Test 1: toggled = 0

Test 2: toggled = 1

Test 3: toggled = 1

Test 4: toggled = 0

Test 5: dead = 1

So, what number was in test {2,3,5} and not in {1,4}? 10!

So the poisons were in beakers 17 and 10.

If I would have set up the tests differently, it would have been simpler to find the last beaker (adding powers of two), but I'll leave that as an exercise to the reader.(i.e., me == lazy)

Though I will give a (lazy) proof of the claim that at least 1 test will kill a rat.

Since the position of the poison is essentially a set of the tests that get toggled due to it being poisoned, having two poisoned beakers and all tests with live rats means that the two binary positions (set of tests resulting in dead rats) of the two poisoned beakers would need to be identical since they toggled the exact same tests. Since that cannot be, and we know there are 2 unique ones, there must be at least 1 test of the first 5 resulting in a dead rat.

Edit:: Perhaps the extra rat could be a check at the end to make sure the warden isn't trying to trick you by having 3 or 1 poisoned beaker. Those evil wardens...

Anyone see a mistake?

Good work, EventHorizon. Nice job going beyond the call of duty. As a prize, you get both your freedom, and the 10th rat for a pet .

[witzar]

That looks like it should work, except there are 30 beakers and not 20.

Right, my mistake. So you put beakers into edges (it is 30 of them), not vertices. The rest is the same.

[witzar]

So you put beakers into edges (it is 30 of them), not vertices. The rest is the same.

It will not work

[EventHorizon]

Right, my mistake. So you put beakers into edges (it is 30 of them), not vertices. The rest is the same.

If that's the case, the way the dodecahedron is painted is not unique. Here are some possibilities with the same result:

Second from left on the top is painted black.

  __________XXXX__________

 |    |    X    |    |    |

 |    |    X    |    |    |

  \  / \  / \  / \  / \  / \

   \/   \/   \/   \/   \/   \

   |    |    |    |    |    |

   |____|____|____|____|____|


  XXXX____________________

 |    X    |    |    |    |

 |    X    |    |    |    |

  \  / \  / \  / \  / \  / \

   \/   \/   \/   \/   \/   \

   |    |    |    |    |    |

   |____|____|____|____|____|




2nd and 4th on the top are painted black.

  ________________________

 |    |    X    X    |    |

 |    |    X    X    |    |

  \  / \  / \  / \  / \  / \

   \/   \/   \/   \/   \/   \

   |    |    |    |    |    |

   |____|____|____|____|____|


  _____XXXX______XXXX_____

 |    |    |    |    |    |

 |    |    |    |    |    |

  \  / \  / \  / \  / \  / \

   \/   \/   \/   \/   \/   \

   |    |    |    |    |    |

   |____|____|____|____|____|




2nd and 3rd on the top and 2nd on the bottom are painted black.

  __________XXXX__________

 |    |    |    |    |    |

 |    |    |    |    |    |

  \  / \  X \  / \  / \  / \

   \/   \X   \/   \/   \/   \

   |    |    |    |    |    |

   |____|____|____|____|____|


  _____XXXX_______________

 |    |    |    |    |    |

 |    |    |    |    |    |

  \  / \  / X  / \  / \  / \

   \/   \/   X/   \/   \/   \

   |    |    |    |    |    |

   |____|____|____|____|____|

Edit:: Didn't see your last post.

Edited April 8, 2011 by EventHorizon

[Guest]

Test samples 1-10 and 11-20.

Pour a sample from 1-10 into vial A, samples from 11-20 into vial B.

Vial A: 1-10

Vial B: 11-20

If A and B both test positive, we have eliminated 10 vials 21-30. If A tests Positive and B negative, 21-30 still may contain a poison. Similarly, if A tests Neg and B tests Pos, 21-30 still may contain a poison. However, we still have eliminated 10 vials. If both test negative, 21-30 contains both vials of poison and we have eliminated 20 vials.

Two vials used, two tests.

Assume the worst case scenario, 20 vials need to be tested. Number them 1-20 for convenience.

Test A: samples from 1-5, 11-15 and B: samples from 6-10,16-20.

4 vials and 4 tests used.

There are 3 possible outcomes:

1. A is Pos and B is neg.

2. A is Neg and B is Pos.

3. A and B are both Pos.

Possibility 1: A is Pos and B is neg, then the poison is in 1-5 and 11-15.

Test samples from vials 1-3.

If 1-3 tests Pos, test 1 and 2 separately. This will determine which vial 1, 2 or 3 contains the poison in 3 tests and 3 vials.

If 1-3 tests Neg, test sample 4. This will determine if the poison is vial 4 or 5. This requires 2 tests.

Worst case scenario is if 1-3 is pos. Max 3 tests and 3 vials used.

Similar tests on 11-15 will determine the poisonous vial in a max of 3 tests and 3 vials.

Total tests and vials for Possibilty 1 is 6.

Total tests and vials used is 10.

Possibility 2: A is Neg and B is Pos, then the poison is in 6-10, 16-20.

This is the same reasoning as Possiblity 1.

Total tests and vials for Possibilty 1 is 6.

Total tests and vials used is 10.

Possibility 3: If A and B are both pos.

Test samples 1-5. If this is positive, vials 11-15 are eliminated. If 1-5 is negative, 1-5 is eliminated and the 11-15 must contain the poisonous vial.

Similarly, testing samples 6-10 will determine if the poison is in 6-10 or 16-20.

2 tests and 2 vials bringing the total tests and vials to 6.

Suppose 1-5 contains tests Pos., the test samples from 1 and 2.

a. If it is positive, test 1. If pos, 1 is poisonous. If Neg, 2 is poisonous. - 2 tests and vials.

b. If test 1-2 neg, test samples from 3 and 4. If pos, test 3. if pos, 3 is poisonous. If Neg, 4 is poisonous. - 2 tests and vials.

c. If test 3-4 is also neg, then 5 contains the poison. Only 1 test.

Worst cast scenario is 2 tests.

Similar tests on 11-15 can also determine the poisonous vial in a max of 2 tests and vials.

Maximum total tests and vials for Possibilty 3 is 4.

Total tests and vials used is 10.

The only other what if is if the both vials poison is in 21-30. Since only two tests and vials were used with this possibility, determining the poisonous vials should be rather simple.

Edited April 8, 2011 by jpf

[Guest]

Test samples 1-10 and 11-20.

Pour a sample from 1-10 into vial A, samples from 11-20 into vial B.

Vial A: 1-10

Vial B: 11-20

If A and B both test positive, we have eliminated 10 vials 21-30. If A tests Positive and B negative, 21-30 still may contain a poison. Similarly, if A tests Neg and B tests Pos, 21-30 still may contain a poison. However, we still have eliminated 10 vials. If both test negative, 21-30 contains both vials of poison and we have eliminated 20 vials.

Two vials used, two tests.

Assume the worst case scenario, 20 vials need to be tested. Number them 1-20 for convenience.

Test A: samples from 1-5, 11-15 and B: samples from 6-10,16-20.

4 vials and 4 tests used.

There are 3 possible outcomes:

1. A is Pos and B is neg.

2. A is Neg and B is Pos.

3. A and B are both Pos.

Possibility 1: A is Pos and B is neg, then the poison is in 1-5 and 11-15.

Test samples from vials 1-3.

If 1-3 tests Pos, test 1 and 2 separately. This will determine which vial 1, 2 or 3 contains the poison in 3 tests and 3 vials.

If 1-3 tests Neg, test sample 4. This will determine if the poison is vial 4 or 5. This requires 2 tests.

Worst case scenario is if 1-3 is pos. Max 3 tests and 3 vials used.

Similar tests on 11-15 will determine the poisonous vial in a max of 3 tests and 3 vials.

Total tests and vials for Possibilty 1 is 6.

Total tests and vials used is 10.

Possibility 2: A is Neg and B is Pos, then the poison is in 6-10, 16-20.

This is the same reasoning as Possiblity 1.

Total tests and vials for Possibilty 1 is 6.

Total tests and vials used is 10.

Possibility 3: If A and B are both pos.

Test samples 1-5. If this is positive, vials 11-15 are eliminated. If 1-5 is negative, 1-5 is eliminated and the 11-15 must contain the poisonous vial.

Similarly, testing samples 6-10 will determine if the poison is in 6-10 or 16-20.

2 tests and 2 vials bringing the total tests and vials to 6.

Suppose 1-5 contains tests Pos., the test samples from 1 and 2.

a. If it is positive, test 1. If pos, 1 is poisonous. If Neg, 2 is poisonous. - 2 tests and vials.

b. If test 1-2 neg, test samples from 3 and 4. If pos, test 3. if pos, 3 is poisonous. If Neg, 4 is poisonous. - 2 tests and vials.

c. If test 3-4 is also neg, then 5 contains the poison. Only 1 test.

Worst cast scenario is 2 tests.

Similar tests on 11-15 can also determine the poisonous vial in a max of 2 tests and vials.

Maximum total tests and vials for Possibilty 3 is 4.

Total tests and vials used is 10.

The only other what if is if the both vials poison is in 21-30. Since only two tests and vials were used with this possibility, determining the poisonous vials should be rather simple.

Test samples 1-10 and 11-20.

Pour a sample from 1-10 into vial A, samples from 11-20 into vial B.

Vial A: 1-10

Vial B: 11-20

If A and B both test positive, we have eliminated 10 vials 21-30. If A tests Positive and B negative, 21-30 still may contain a poison. Similarly, if A tests Neg and B tests Pos, 21-30 still may contain a poison. However, we still have eliminated 10 vials. If both test negative, 21-30 contains both vials of poison and we have eliminated 20 vials. If both are negative, one of the two groups of ten could contain both poison vials which is not accounted for here.