wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Evil king
        
(Message started by: greatly_amuzed on Sep 29^th, 2002, 11:16pm)

Title: Evil king
Post by greatly_amuzed on Sep 29^th, 2002, 11:16pm

I'm absolutely clueless about the solution to evil king...

could someone give me a hint pls?

Title: Re: Evil king
Post by S. Owen on Sep 30^th, 2002, 8:37am

This is about the "Criminal Cupbearers" problem? There is a thread in this section called "Hard: Criminal Cupbearers" that has some good answers.

Title: Re: Evil king
Post by anonymous coward on Sep 30^th, 2002, 4:01pm

have a solution that actually gets done in 4 weeks with 10 prisoners and wipes out at most 10 of them:

each prisoner provides one bit of information (i.e, either lives or dies). ten prisoners provide 10 bits of information.
10 bits can encode 1024 choices.

i) label each bottle in binary: 00..00, 00..01, 00...10, ...
ii) make prisoner k drink all bottles that have the k-th bit set to 0
(each prisoner drinks about half the bottles)
iii) if prisoner k dies, then the k-th bit is 0, else 1

construct the resulting bit string using the information of deaths
and this gives the the label of the posioned bottle.

on average half the prisoners (i.e 5) will die and this exercise only takes a month to accomplish.

is there something i'm missing? why does the question provide 5 weeks?

Title: Re: Evil king
Post by Boboar on Oct 22^nd, 2002, 3:46pm

The problem with that idea is that it takes a month for the symptoms to show up, so you would take a lot longer than 5 weeks to solve it.

Title: Re: Evil king
Post by Icarus on Oct 22^nd, 2002, 8:08pm

on 10/22/02 at 15:46:30, Boboar wrote:

The problem with that idea is that it takes a month for the symptoms to show up, so you would take a lot longer than 5 weeks to solve it.

Your are misreading A.C.s solution. All the prisoners drink a little from every one of their assigned bottles on day 1. A month later, those who drank from the poisoned bottle are all dead. By seeing which prisoners died, the king reconstructs the binary number corresponding to the poisoned bottle.

The 5th week is not necessary.

Title: Re: Evil king
Post by Chronos on Oct 24^th, 2002, 11:55am

I think that "five weeks" was just so we don't have to worry about the ambiguity in the definition of "one month". If the ball were in four weeks (28 days), and it took 1 month (up to 31 days) for the poison to show up, then there would be no solution.

But I'll still argue that the best solution is one prisoner per bottle. The only thing we know about the number of prisoners available is that the dungeons are "vast", which to me implies that he has as large a finite number of prisoners as we might need. One per bottle means only one prisoner dies, so the rest can be used for future taste tests or whatever other evil the King has planned for them, and this solution also uses up the smallest possible amount of wine. Furthermore, it also gives you a margin of safety in case more than one bottle was actually poisoned, or some prisoners die of other causes in the interim.

The only reason I can see for restricting ourselves to using ten prisoners is if that's all the prisoners he has in the dungeon, and I don't see that that's implied at all in the problem.