Fog Creek Software
Discussion Board




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 non-issue.

    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 08, 2002

How is this for a simpler solution. 

1/ Number each prisoner to be sippers 1 to 10. 
2/ Number each bottle 1-1000.
3/ Each prisoner then sips 100 bottles each.  That is, sipper 1 sips bottles 1-100, sipper 2 sips bottles 101-200, 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 1-10, 101-110, 201-210, 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 trade-off for saving a few more lives.

Alan Bainbridge
Monday, June 17, 2002

*  Recent Topics

*  Fog Creek Home