Author |
Topic: Evil king (Read 1384 times) |
|
greatly_amuzed
Newbie
Posts: 4
|
 |
Evil king
« on: Sep 29th, 2002, 11:16pm » |
|
I'm absolutely clueless about the solution to evil king...
could someone give me a hint pls?
|
|
 IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Re: Evil king
« Reply #1 on: Sep 30th, 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.
|
|
IP Logged |
|
|
|
anonymous coward
Guest
|
|
Re: Evil king
« Reply #2 on: Sep 30th, 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?
|
|
IP Logged |
|
|
|
Boboar
Guest
|
|
Re: Evil king
« Reply #3 on: Oct 22nd, 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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Evil king
« Reply #4 on: Oct 22nd, 2002, 8:08pm » |
|
on Oct 22nd, 2002, 3:46pm, 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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Evil king
« Reply #5 on: Oct 24th, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print