
The "Bad King" is wasteful
Howdy,
There's no need to kill 10 people.
Really, the waste is a bit stunning to
me. Such casual waste of life and then
let's not even get into the effort it takes
to keep the 2 extra deaths a nonissue.
The problem stated that 5 weeks later,
the king could enjoy his drink. We can
test 255 bottles of wine each day with 8
people. So, given a month (31 days worse case), that gives us 4 extra days before the king could drink. So, we only need to test for 4 days and then figure out which day which group of slaves die and we can reduce the # of prisoners by 2.
Sheesh, such casual disregard for lives
and minimization given the problem constraints. :)
Oh, I'm not going to be reading this forum to look for replies, so feel free to contact me at matthew@ebay.com if you'd like.
Cheers,
Matthew
Matthew Mengerink
Wednesday, May 8, 2002
How is this for a simpler solution.
1/ Number each prisoner to be sippers 1 to 10.
2/ Number each bottle 11000.
3/ Each prisoner then sips 100 bottles each. That is, sipper 1 sips bottles 1100, sipper 2 sips bottles 101200, and so on...
4/ A day later, each poor soul then sips the first 10 bottles in each group. That is, sipper 1 sips bottles 110, 101110, 201210, etc..
5/ The following day, each sipper sips the first bottle of each group of 10. That is, sipper 1 sips bottles 1, 11, 21, 31, ...., 991. Sipper 2 sips bottles 2, 12, 22, etc.
The result is that every sipper sips no more than 300 times. Four weeks later, one, two or three sippers will die from poisoning. If sipper 2, 7 and 9 die, in that order, then bottle 279 contains the poisoned wine. If only sipper 5 dies then bottle 555 is the bad one. If sipper 4 and 3 die in that order, then chuck out bottles 43, 433 and 434.
Two dying sippers is the only case where three bottles will have to be disposed. But at least only a maximum of three prisoners will only have to die, which is a good tradeoff for saving a few more lives.
Alan Bainbridge
Monday, June 17, 2002
Recent Topics
Fog Creek Home
