A ‘bad’ King has 1000 bottles of delightful and very expensive wine (possibly reviewed on cork’d.com). A traitor to the king sneaks into his castle and threatens to poison him. Fortunately the guards catch the servant after he has only tampered with one wine bottle. The guards don’t know which bottle has been poisoned. With me so far ?
Furthermore, after drinking the poison it takes one full month to kill the victim. The king has an upcoming(.org?) party in exactly 1 month, and wants to serve all 999 bottles i.e. without serving the poisoned one.
Being a cheap ‘bad’ King, he wants to employ the least number of wine tasters, saving on his party budget. What is the minimum number of wine tasters the King needs ? And if you were a member of this unlucky bunch; which one would you want to be ?
matt
5 months ago, said;
No answers yet? Here’s a clue; think of combinations of tasters …
Answer soon ..
Piers Cawley
5 months ago, said;
Gah! Lost internet connection as I was trying to post a question:
How many testers is it okay to kill? How much wine is it okay to drink? How much wine (as a proportion of the bottle) do the testers have to drink in order to be poisoned? Assuming that the lethal does is negligible, you can probably get away with 10 testers.
It works likes this:
Number the bottles, 0 to 999.
Number the testers 0-9
Tester 0 drinks from all bottles(n) such that n & 1 != 0 Tester 1 drinks from all bottles(n) such that n & 2 != 0 Tester 2 drinks from all bottles(n) such that n & 4 != 0 ... Tester n drinks from all bottles(n) such that n & 2n != 0
Then at the end of the month, say tester 0 and 2 died, then you know that the pellet of poison is in bottle 22 + 2^0 = 4 + 1 = bottle 5.
I’ll be tester number 9 please, I only have to drink 999-512 bottles.
It’s a binary thing.
Piers Cawley
5 months ago, said;
Wow. I royally screwed up on the formatting didn’t I?
Matt
5 months ago, said;
Well done Piers, you are correct (!) It is a binary problem;
10 tasters, gives you 2^10 possible taster combinations, which is 1024, more than enough to test 1000 bottles. And yes, you would want to be the last taster in the sequence of 0-9 since he takes fewer sips (he is the effectively the MSB.)
To answer your questions;
Piers Cawley
5 months ago, said;
Of course, if the king’s a complete bastard, he could force the testers to drink from all the bottles such that #bottle & #taster = 0, then line ‘em all from MSB to LSB and wait for a month. That way all the tasters still vertical would be read as ‘1’ and all the dead ones as 0, which is aesthetically more satisfying somehow.
For suitably psychopathic values of ‘aesthetically satisfying’ of course.
But that reopens the question of which taster you would want to be – being taster number 9 is a good deal less appealing in this scenario, but I’m not quite sure whether there’s anything to chose between the lower order bits and I can’t quite bring myself to do the sums.
matt
5 months ago, said;
Sorry, I meant to say you’d want to be in the LSB. part. If there were 1023 bottles, it wouldn’t matter since everyone would have to take 512 sips. But there are 23 bottles less, so the people whose bits would have been on from 1001 to 1023 won’t have to take a sip.
1001 is [11111 01001] in binary and 1023 is [11111 11111]. Note the most five significant bits are always on from 1001 to 1023, so all those people are drinking during this stage. So in order to increase your chance of living, you’d probably want to be prisoner 1 to 5.