Wine testing
The police commissioner hired a mathematician to help at a crime scene. At the scene there were between 100 and 200 glasses of wine, one of which had been poisoned. The mathematician was asked to determine which glass was the poisoned one, in the minimum number of tests. The mathematician counted exactly how many glasses there were and said "test one of the glasses at random". The commissioner asked, "wouldn't that waste a glass?". The mathematician said "no". How many glasses were there?
For each test you may mix the contents of as many glasses as you want, and then do a single test to determine if any of them was poisoned.
For each test you may mix the contents of as many glasses as you want, and then do a single test to determine if any of them was poisoned.
Labels: mathemagic
posted by Chris at
4:19 PM
14 Comments:
The mathematician was asked to determine which glass was poisoned in the MINIMUM NUMBER OF TESTS. Then ... the last paragraph of the problem statement says DO A SINGLE TEST. Either this is contradictory... or, I am mis-interpreting the information given.
Hmmmmmmm ... think I'll have a glass of wine ...
Hi Zaux. Sorry, my bad. I've now fixed the second para ("the" has become "each").
Ah .... now it makes sense ... thanks.
Looks like to me ... in the worst case scenario, he would have to do 6 tests ... but, I am still not sure exactly how many glasses there were.
sorry ... forgot the test he did at random ... making a total of 7 tests
Let me guess . . .
The initial number of glasses is an exact square plus one, i.e. 101, 122, 145, 170 or 197.
After testing one at random, and assuming it is not the poison one, set up the rest in a n x n array (n = 10, 11, 12, 13 or 14).
Mix a portion from each of the glasses in the first row and test the resulting mixture. Repeat for each row. Say row x has the poisoned wine.
Do the same for each column and find column y as the one with poison.
Then the glass at the intersection of row x and column y in the array is the one with the poison.
Up to 2n+1 tests are thus required in the worst case, where the last row and column test positive. The best case would be one if the initial random selection turned out to be the poisoned one, or three for x = y = 1.
Having said all this, this would also work for any multiple m x n between 99 and 199, so that the number of tests would be between 1 and m+n+1.
Since there is no unique solution here, methinks I might be on the wrong track.
126 glasses...no,wait.thats wrong.but i'm posting this anyway.don't really know why.
Actually, now that I think about it, why limit my array to two dimensions?
Why not a 2x2x2x2x2x2x2 array in 7 dimensions? Then there would be 129 glasses to be tested.
Mix a sample from the two glasses in each "line" of each dimension so that a maximum of 2x7 = 14 tests would be required. Plus the initial test.
My head hurts trying to think about your mathematician would set up a 7-dimensional array on a two-dimension table. I'll leave that to him/her.
Oz nailed it...
129 glasses, 7 tests (including the initial one)
Poison Wine problem
Assume: the poison test only yields a two state answer i.e. poisoned or not poisoned
(if concentration of poison in poisoned glass is known and concentration can be measured the number of tests required is reduced to 1, if , however, the concentration of poison in glass is unknown but concentration can be measured, then we could reduce the tests to 2)
Since we only get 1 bit of information out of each trial the number of glasses we have information about after n trials is 2^n.
The only number between 100-200 that meets the 2^n criteria is 128. We then add one for the randomly sampled glass for a total of 129.
The testing method is as follows:
If the randomly selected glass is poisoned, we stop. We then take a bow and rush off to buy a lotto ticket.
If not, we conduct an additional 7 tests.
We narrow down the poisoned glass by bisecting the 128 glasses in half for each test, by mixing the contents of half the glasses into 1 glass we know not to be poisoned. (we can initially use the first glass we tested). The already tested glass is #129.
For example if the poisoned glass is glass #89.
1st test we mix 64 glasses 1-64 into a clean glass. Test comes back clean, thus poisoned glass is 65-128.
2nd test we mix 32 glasses 65-96 into a clean glass. Test comes back poisoned.
3rd test we mix 16 glasses 65-80 into a clean glass. Test comes back clean, thus poisoned glass is 81-96.
4th test we mix 8 glasses 81-88 into a clean glass. Test comes back clean, thus poisoned glass is 89-96.
5th test we mix 4 glasses 89-92 into a clean glass. Test comes back poisoned.
6th test we mix 2 glasses 89-90 into a clean glass. Test comes back poisoned.
7th test we test 1 glass 89. Test comes back poisoned.
So we either get lucky and find the poisoned glass with the random selection, conducting only 1 test, or we need to conduct 7 more tests for a total of 8 tests.
Answer: 129 glasses
Cam
Agreed, Cam - definitely a better approach than 7-dim arrays!
Here we see poor police methods....
1. The commisioner needed help to count the glasses.
2. A crime scene with a poisoned glass - ergo someone drank from a glass and was poisoned, but the police have no idea of which glass...
3. Was the victim identified?
Or was this a plot for the risible TV series Numb3rs?
4. Did the police check the spilt glass next to the dead body? The glass at the dead man's table setting?
5. Was the wine a Beaujolais Nouveau which is pretty poisonous stuff anyway...
However, for once this week, I agree with Wizard of Oz - 129 glasses 128 + the first test glass.
129 is the correct answer. i.e. 2^7 + 1. So 8 tests are required (unless by luck the first glass is the poisoned one). After testing the odd glass, that leaves 7 more tests. So no wastage is involved by testing just 1 glass.
Hi Wiz. You seem to have a thing about square numbers (n^2) rather than 2^n (binary) numbers. Remember that weighing "Marbleous 2". At least I haven't introduced Fermat's Last Theorem this time.
Well done Wiz and Cam.
Post a Comment
Links to this post:
Create a Link
<< Home