There is a king and there are his n prisoners. The king has a dungeon in his castle that is shaped like a circle, and has n cell doors around the perimeter, each leading to a separate, utterly sound proof room. When within the cells, the prisoners have absolutely no means of communicating with each other.
The king sits in his central room and the n prisoners are all locked in their sound proof cells. In the king's central chamber is a table with a single chalice sitting atop it. Now, the king opens up a door to one of the prisoners' rooms and lets him into the room, but always only one prisoner at a time! So he lets in just one of the prisoners, any one he chooses, and then asks him a question, "Since I first locked you and the other prisoners into your rooms, have all of you been in this room yet?" The prisoner only has two possible answers. "Yes," or, "I'm not sure." If any prisoner answers "yes" but is wrong, they all will be beheaded. If a prisoner answers "yes," however, and is correct, all prisoners are granted full pardons and freed. After being asked that question and answering, the prisoner is then given an opportunity to turn the chalice upside down or right side up. If when he enters the room it is right side up, he can choose to leave it right side up or to turn it upside down, it's his choice. The same thing goes for if it is upside down when he enters the room. He can either choose to turn it upright or to leave it upside down. After the prisoner manipulates the chalice (or not, by his choice), he is sent back to his own cell and securely locked in.
The king will call the prisoners in any order he pleases, and he can call and recall each prisoner as many times as he wants, as many times in a row as he wants. The only rule the king has to obey is that eventually he has to call every prisoner in an arbitrary number of times. So maybe he will call the first prisoner in a million times before ever calling in the second prisoner twice, we just don't know. But eventually we may be certain that each prisoner will be called in ten times, or twenty times, or any number you choose.
Here's one last monkey wrench to toss in the gears, though. The king is allowed to manipulate the cup himself, k times, out of the view of any of the prisoners. That means the king may turn an upright cup upside down or vice versa up to k times, as he chooses, without the prisoners knowing about it. This does not mean the king must manipulate the cup any number of times at all, only that he may.
Assume that both the king and the prisoners have a complete understanding of the game as I have just explained it to you, and that the prisoners were given time beforehand to come up with a strategy. The king was able to hear the prisoners discuss, however, so also assume that if there is a way to foil a strategy, the king will know it and exploit the weakness. The prisoners must utilize a strategy that works in absolutely every single possible case.
Now you must figure out not only how to keep the prisoners alive, but how to also ensure their eventual freedom. When can any one of them be certain they've all been in the central chamber of the dungeon at least once? And how? Don't try to imagine any trickery like scratching messages in the soft gold of the chalice. The problem is as simple as it sounds. The prisoners have absolutely no way of communicating with each other except through the two orientations of the chalice. If any of them attempts any trickery at all they will all be beheaded. All the prisoners can do is turn the chalice upside down or right side up, as they choose, whenever they are called into the chamber.
It's a terribly written version of the "warden and his prisoners" problem, which you can google. The only difference other than confusing language is the original problem has two on/off switches, and each prisoner must flip one, rather than one that can be left alone.
*Spoiler* Don't read the following if you don't wanna know the answer:
1) The prisoners elect one of their own to be a counter, the rest we will call non-counters.
2) When a non-counter comes into the chalice room, if he can he will put the chalice right side up. If it's already right side up, he'll leave it alone. However, each non-counter will only do this once. If he's already flipped it in the past, and it's upside down, he'll leave it upside down.
3) Every time the counter comes in, he checks the chalice. If it's upside down, he'll do nothing. If it's right side up, he'll flip it, and add one to his count. Once he's flipped it n times (n being the prisoner count), he knows everyone has done it. If the original state of the chalice is known, the problem can be modified so he only needs to flip it n-1 times.
I don't see how this can work. In the problem the king can listen to the prisoner's strategy. With this solution all the king must do is keep calling the counter, and keep flipping the chalice until the counter is convinced all have been called, at which point he is wrong and everyone dies.
No, he can't. The counter was given as a value that the counter (that is, the prisoner doing the counting) has in their head and that they only increase under certain circumstances but never decrease. So unless the king is able to do a lobotomy on the counting prisoner, he won't be able to decrease it.:)
Oh, I didn't mean to imply that a counting solution is feasible; it's just the argument that the king would be able to decrease the counter that's not true. That nonwithstanding, I am reasonably sure that an attempt to use counting for the solution must fail, for the reasons you give.
But there are other ways to solve the problem. I posted an idea of mine here [slashdot.org], and while it could probably be refined, I don't see any immediate problems with it that would render it infeasible.
Read the original problem. The king may change the cup k times. It doesn't mean he has to.
Also, he could use his ability to change the cup every time a non-counter changes the cup. If he did that, then the prisoners would remain imprisoned forever as the counter would never reach n.
And then if the king refuses to flip the cup at all? They will never get to n+k. You need a count that is reachable if the king doesn't touch the chalice and one that can be messed with up to k times.
Except you will eventually get to n+k flips. The king may never flip the chalice but as long as the prisoners keep being called you can reach any number. It isn't the most efficient way to escape, which would require n flips, but it will work.
Like I said, the original is better written and includes the supposition that the warden will pick randomly, but without malice so it will eventually even out, and you have to assume the king/warden won't interfere, or the answer becomes mu.
What if the king flips the cup every time a non-counter flips the cup? Lets say there are 10 prisoners and the king can flip it 6 times. The King can keep the counter at 4.
What if there are 20 prisoners and he only lets each in there twice, but brings in everyone in a row. Then the counter gets to two and its game over.
This seems to be a derivation of a riddle given to my friend's math professor when he interviewed at the NSA... One person is appointed the leader. He always turns the cup upside down. Everyone else enters. If the cup is right side up, they leave it, if it upside down, they put it right side up, but only if they previously have not flipped the cup. So the only time the leader would flip the cup is if another prisoner had already been in the room.
So how to deal with the fact that the King can flip the c
How about instead of each prisoner only flipping the chalice once, they flip it the first k+1 times they get the opportunity? Then once the leader gets to n(k+1) flips, he knows everyone has been in the room and flipped it at least once.
Of course this still suffers from the potential problem of the leader going insane and losing count, only now it is increased by a factor of n because the same can now happen to any of the prisoners.
The problem is that the king could choose to negate or add to any or some of the signal or not. You have n(k+1)-k=Resultant Signal=n(k+1)+k. The number of flips was significant previously, because it was telling the leader that everyone had been out. The leader could count them all, and know the moment everyone was out. But the key that made it work was everyone flipping it only once, otherwise the leader would overcount and get himself / herself killed. I suspect that playing with this possible negation
" The problem is that the king could choose to negate or add to any or some of the signal or not. "
Doesn't matter. Assume the king flips it k times and calls everyone but one guy so often that they each flip it their maximum number of times. Then you will have (using my previous correction that it should be (n-1)(k+1)) (n-2)(k+1)+k flips (or (nk+n-k-2)), which is one less than the (n-1)(k+1) (or nk+n-k-1) that they are looking for. Now since everyone other than the last prisoner has already flipped it
I was under the impression he had to eventually call everyone x number of times for any arbitrary number x, including those greater than n(k+1). Then again its late and I should be asleep (but I can't because I'm thinking about those damn chalices).
This problem is fundamentally different from that one. It won't help you much to know how to do that one, and is more likely to make you sure of a wrong solution than to get you to a right solution.
The only method of communicating is the chalice. We must assume the chalice is able to be manipulated by the king, flipped or not, every time a prisoner is sent back. Therefore, the chalice essentialy randomizes itself, and we have to assume that it may do it as the king wishes. This means that each new prisoner is potentially coming back into the room with no trace of the previous prisoner's presence, no indication of how many have been there before. If their only method of communication erases itself
" Pain in the neck...wanted to go to sleep an hour ago, but now I have to figure this one out:)"
I brought the productivity of the entire student work force at Sandia Natl Labs down to zero this summer by posting this problem on their message boards.:)
Just so you know, the only person who I know legitimately solved this problem (none of the students at SNL could get it) worked at it for a couple weeks before getting the solution, albeit not the optimal solution.
I thought about that. The problem is the king doesn't have to flip it over at all. Thus when he hears this strategy, he can just never flip it (or just flip it less than k times) and the leader will never be able to say yes. At least not until he goes insane from sitting in a cell all day and imagines he sees the cup flipped.
The only thing I can add to this is that the number of meddlings the king can do is actually k+1, as he gets to set the default chalice position (up / down). So, much like N = n - 1, K should equal k+1.
Very nice! Nicely written and explained. I don't think it's hand wavy. If anyone is paranoid about whether you might be off by one anywhere in your count, then fine, give each non-counter more tokens...
Is this just a word riddle? So the answer could be: They are not explicitly locked BACK into their rooms after they are asked the question so they can just count to make sure all the members are back?
Obviously, the most devious thing that the king can do is to always make sure the chalice is rightside up. Therefore, it will always be rightside up. Therefore, the chalice can provide no information. Therefore, it is a red-herring.
With all other avenues of gathering information forbidden, there seems no information left to base an answer on.
Obviously, the most devious thing that the king can do is to always make sure the chalice is rightside up. Therefore, it will always be rightside up. Therefore, the chalice can provide no information. Therefore, it is a red-herring. No, since he can only move it k times.
Unless worded wrong the number of times the king can turn the chalice K is never limited in anyway. So it becomes useless as you say.
When the numbers become meaningless look at the meaning behind words.
The setup is a central room (the king room) with cells around it. Basically a lot of the story keeps pointing out that the room with the king is central to the setup with the cells surrounding it. Since cells are typically only build with 1 door it then becomes logic to assume that each prisoner as he was l
The king can only change it k times. The value of k influences how long it will take before the prisoners can be confident of a yes answer. This is a thinly disguised scenario for a "zero-knowledge" cryptographic authentication protocol.
well, that's exactly what the previous poster has suggested -- force the king to flip it. That is, put him in a situation that if he does not flip the chalice, it would be obvious to at least one of the prisoners that all of them have been to the room already. If we can prove that the king could be forced to flip the chalice once, we can prove that the prisoners can go free. I believe the opposite is also true -- if the king cannot be forced to flip the chalice, the prisoners at best will spend life in priso
Yes, he can. If he can flip the chalice an arbitrary number of times, then unless the inmates can wait an infinite amount of time we should treat that number as infinite. Therefore the chalice cannot retain information. As the question states the orientation of the chalice is the only method of communication, we can therefore assume the prisoners cannot communicate. Therefore they have no way of knowing if everyone has been in the room. This is of course assuming that the prisoners are not able to wait an in
You don't seem to know that much about statistics. Neither do I, of course, but your comment has some rather blatant errors in it. First of all, the inmates cannot wait an *infinite* time, but they can wait an arbitrary time - that is, for any finite amount of time t, they can wait for that amount.
The part about "what if the prisoners have waited for an infinite amount of time" is rubbish, too - the state the whole system is in simply isn't well-defined if you attempt to take the limit. In fact, considering
That means the king may turn an upright cup upside down or vice versa up to k times
Up to K times means K or less. Therefore, K is any number. Therefore, the king can do whatever the hell he wants, and the calice provides no information.
Or let's suppose it has to be EXACTLY k times. Either K or zero. Fine. I declare K to be 1.
In this case, if the challice is upside down, the king chooses to flip it K times. If it is rightside up, then the king chooses to f
I think the key here is that while the prisoners don't know what K is, we, as the omniscient puzzle solvers, do. So we can come up with a strategy. I guess you could say there is a theoretical solution - if for some reason this was happening in real life, then yeah, the prisoners are screwed because they don't know what K is.
k is not undefined. k is a number that the king and prisoners know ahead of time. This should be obvious, as the problem does indeed say there is a solution.
So what you're saying is that you wrote the problem ambiguously, and to resolve ambiguities we ought to choose the interpretation that yields a solution?
Your description of the problem does not say when k is fixed. A perfectly valid reading of the problem is to suppose that the prisoners are told that the king will decide k when the game begins.
You ought to admit that the problem was unclear, instead of insulting everyone who interprets your ambiguity the wrong way.
"arbitrary" is not the same as "infinite" or "unlimited" - the former means that while the number can be, well, arbitrary (that is, any natural number whatsoever), it will still be a fixed finite number for any given instance of the game.
The real question is whether the prisoners know the value of k in advance or not.
"up to k times" means k or less times. k is not any number, it is constant, an it can be assumed this constant is know to the prisoners berforehand. So when all prisoners work out not to change the chalice, when a prisoner has seen the chalice been turned k times, he can safely assume the king has spent his turning actions and then the chalice can start conferring information.
However, since the king may decide never ever to turn the chalice, prisoners might still stay pretty much indefinitely, same if the ki
This sounds very much like a similar problem I solved in college, involving a light switch instead of the chalice and omitting the king's ability to manipulate the communications tool of the prisoners. I have the following questions:
1. Do the prisoners know k?
2. Define "arbitrary number of times."
These are my sticking points. Based on my questions, I'm sure you can guess the strategy I'm going after from the problem I solved before. My other question is this: Am I on the right track by iterating
This puzzle makes no sense. Either you didn't word it correctly, or it's just plainly wrong. Imagine the case where k is larger than the number n, the times each prisoner needs to be called eventually. All the king needs to do is pick a random prisoner, say "Jack", call him in n times, and undo the cup whenever Jack flips it. After n times, just forget about Jack and call others any way he wants. As far as Jack is concerned, he will never have a chance to answer questions again; for others, Jack never left
I think he means every prisoner must be called in an infinite number of times (if the thing goes on forever), and was trying to appear clever by using fancy words.
The answer is simple. The first prisoner called in must kill the king and take his keys, then free his comrades./Sorry, I'm a run-n-gun type of guy//You didn't say anything about GUARDS
1)Is the value of k known (in advance) by the prisoners?
2)"The only rule the king has to obey is that eventually he has to call every prisoner in an arbitrary number of times." Does this mean that at some point, all prisoners have been called in the same number, n, of times? [Where n is unknown, but is at some point equal for all prisoners]
It's a comms theory problem. Assume the simple case where n=2. Prisoner 0 (p0) needs to communicate an "I've been in the room" message to prisoner 1 (p1). Once p1 receives that message he can answer "yes" and both prisoners go free.
However the only communication method is a chalice which is a lossy channel because the King can introduce k errors per message. In other words, for every k+1 bits communicated, only 1 bit is reliably transmitted. Fortunately the problem of transmitting data over a lossy channe
I'm sorry, this is just dumb. I'm only repeating what others have said so far but maybe that will help drive in the point that this is Worst. Puzzle. Evar.
With the king able to manipulate the chalice, there is absolutely no way for them to communicate to eachother, because the king can always turn the chalice back to the way it was before the prisoner entered the room. So every prisoner will always see the exact same thing. Stupid, stupid.
(based on an AC comment above and my bug fix to it) They choose a watcher If the watcher is called and the cup is upside down he flips it right side up If anyone else is called and the cup is right side up they flip it to be upside down, unless they've done it previously in which case they leave it alone. When the watcher has flipped the cup n+k+1 times he says yes.
Since the King can only interfere k times, you have to out wait him, hence +k. The +1 is because the cup may not be right side up on first time.
This doesn't work because everone will just flip the chalice once. If the king flips it back before the watcher gets to see it, they will not be able to confer the information again.
I suppose you could have the watcher flip the chalice at some point to tell the other to report gain, but the lack of limits on the number of times someone can be called makes it hard to specify any strategy.
... unless there are other constraints, such as the king having to turn the chalice k times, eventually. The description specifically states that the king may do so, though.
If there only is a solution that relies on the king flipping the chalice k times, then the prisoners are boned, since the king is not obliged to flip it at all.
If there is a solution that does not rely on the king flipping the chalice k times, then the king (knowing the solution and the complete state of the game) can simply wait unt
One person will always flip the cup from up to down. The other prisoners will only flip the cup from down to up. If it's not in the state they want on entering, they leave it be. There's two main problems here: 1. You don't know the initial state of the cup. 2. You don't know what the king has been screwing with.
These are actually the same problem, in that the state of the cup might have been tampered with and you have to route around it.
In the simplest problem (uncertain initial state only), you could have ea
I think I have a solution. First of all, you need a code that can correct about O(k) raw bit errors in a transmitted raw message (k is probably sufficient, but I'm not an expert in coding theory, and this is a detail, anyway ^_~). The prisoners will use this code to send logical bits to each other. The choice of code guarantees that the king's ability to introduce k errors into the raw communication channel (the chalice) will not affect the logical bits transmitted.
Quoting Lynx-Effect above: If the King has effectively unlimited flips, he simply ensures the chalice is upright every time he calls a prisoner, there is no communication stream, and therefore no way for the chalice to signal anything to the others.
As long has you have a malicious interception and corruption of the information medium, the King can manipulate the message any way he sees fit, including sending his own "I've seen it" messages from any prisoner(s) that he never has to call to any prisoner(s) he
First, here is a proof by counterexample that there is no general solution to this problem. The problem has 3 parameters, n the number of prisoners, k the number of allowed flips, and a, the arbitrary number of times the king must call each prisoner. Proof: no solution for k > n * a
Let k > n * a
This means the king can flip the challice once for every time a prisoner is called in to see him. So he can, for example, always turn the challice up before each prisoner is called in. He will select a permutat
I had a conversation with Brian0918 on AIM this morning, in which he revealed he's really trolling when I pointed out to him there is no solution (see my other posts) on this topic. Here's a little tidbit: ". i usually just post the problem to get people into big disputes, which so far has worked 2 out of 2 times". If you want the full conversation, email me at sbartaNOSPAM_at_MAPSONgmail.com.
I came up with this solution in the shower. It has no pretense of being the optimal solution. Don't just say it's wrong; please reply with disproofs (especially the poster of the problem).
This solution requires that each prisoner is guaranteed to be called to the room infinite number of times. Otherwise, if there's a maximum number of times t that a prisoner can be called to the room, then the king could select k = number of prisoners, call each one t times in a row, resetting the chalice to original pos
The problem with that is King doesn't need to turn the challice himself, he only needs to call a prisoner (a non watcher) out to turn it over. Since he can call them an infinite number of times there is no K cap with that strategy. "2) Everyone else, upon finding an upright chalice, turns it upside down. Otherwise, they leave it. They each must turn it over exactly 3k+1 times, where k is the number of times the king can move the chalice."
I've only had one coffee, so I'm not going to work the numbers, but if
The king can only flip the chalice k times, so you just need a solution that can be messed with up to k times. So if you have one guy flipping it rightside up each time he sees it upside down and all the other guys flipping it down the first k+1 times they find it up, the first guy can just count the number of times he has to flip it. Once he gets to (n-1)(k+1), I believe he knows everyone else has been in there.
Close, but the problem with the riddle - and why I agree that this is a hoax riddle that's been made up - or very poorly expressed - is that the king can flip the chalice (0..k) times. Knowing k is useless information. The chalice cannot provide information because the king may flip it just once, or not at all. The "only two people have ever solved it" seems nonsense to me too. If this is genuinely the case, and the solution is as hideously complex as the OP seems to take such glee in stating, either the
"Close, but the problem with the riddle - and why I agree that this is a hoax riddle that's been made up - or very poorly expressed - is that the king can flip the chalice (0..k) times. Knowing k is useless information. The chalice cannot provide information because the king may flip it just once, or not at all."
But this solution takes that into account. If the king never flips it, we still will get to (n-1)(k+1) on our own once everyone has flipped it the maximum number of times. If he does flip it k t
Assuming that the prisoners know k, that they will be called sufficiently randomly over time (the constraints on the king's choices are not clear from the way the riddle is stated - can he call one guy over and over again or what?), and that they are aware of when another prisoner is called to the central room without knowing who got called, here is a solution:
1. The prisoners number themselves sequentially from 1 to n; call the prisoners P.1 to P.n
2. The prisoners all keep track of the number of priso
Yes, I have taken that into account. Read practically every other response I have written on this thread. This count is reachable if the king never uses a flip.
I believe that you might be able to set the number of times each prisoner is called in yourself. You could say that if you knew n=10 and k=1000000000, then you could set "m" or whatever the number of times each prisoner is called in, to be something like 10^10 or something. Just as long as you set it to a finite number.
I think there's a fault (now that I'm caffinated I can tie my shoe laces too!). He doesn't need to keep calling them. The puzzle is that he only needs to call them the same arbitrary number of times. So he could call them only once each and that would defeat this. It's a nice solution otherwise.
"The king will call the prisoners in any order he pleases, and he can call and recall each prisoner as many times as he wants, as many times in a row as he wants. The only rule the king has to obey is that eventually
Ok, you want real world? No matter the solution, the king and prisoners will live at least a day longer than after the prisoners solve the puzzle and are set free. I never said these were humans.:)
Here again, you are demonstrating that you can't articulate your thoughts. What does "...at least a day longer than after the prisoners solve the puzzle..." mean?
In your original posting the language leaves much open to speculation because you spend several sentences clarifying one point and casually make another point. Ex: You dwell on the point that the cells are sound proof but make no mention of other senses such as sight. Is there a window from the cells to the central room? You dwell on the m
Premature optimization is the root of all evil.
-- D.E. Knuth
The King and the Chalice (only for Experts!) (Score:3, Interesting)
The king sits in his central room and the n prisoners are all locked in their sound proof cells. In the king's central chamber is a table with a single chalice sitting atop it. Now, the king opens up a door to one of the prisoners' rooms and lets him into the room, but always only one prisoner at a time! So he lets in just one of the prisoners, any one he chooses, and then asks him a question, "Since I first locked you and the other prisoners into your rooms, have all of you been in this room yet?" The prisoner only has two possible answers. "Yes," or, "I'm not sure." If any prisoner answers "yes" but is wrong, they all will be beheaded. If a prisoner answers "yes," however, and is correct, all prisoners are granted full pardons and freed. After being asked that question and answering, the prisoner is then given an opportunity to turn the chalice upside down or right side up. If when he enters the room it is right side up, he can choose to leave it right side up or to turn it upside down, it's his choice. The same thing goes for if it is upside down when he enters the room. He can either choose to turn it upright or to leave it upside down. After the prisoner manipulates the chalice (or not, by his choice), he is sent back to his own cell and securely locked in.
The king will call the prisoners in any order he pleases, and he can call and recall each prisoner as many times as he wants, as many times in a row as he wants. The only rule the king has to obey is that eventually he has to call every prisoner in an arbitrary number of times. So maybe he will call the first prisoner in a million times before ever calling in the second prisoner twice, we just don't know. But eventually we may be certain that each prisoner will be called in ten times, or twenty times, or any number you choose.
Here's one last monkey wrench to toss in the gears, though. The king is allowed to manipulate the cup himself, k times, out of the view of any of the prisoners. That means the king may turn an upright cup upside down or vice versa up to k times, as he chooses, without the prisoners knowing about it. This does not mean the king must manipulate the cup any number of times at all, only that he may.
Assume that both the king and the prisoners have a complete understanding of the game as I have just explained it to you, and that the prisoners were given time beforehand to come up with a strategy. The king was able to hear the prisoners discuss, however, so also assume that if there is a way to foil a strategy, the king will know it and exploit the weakness. The prisoners must utilize a strategy that works in absolutely every single possible case.
Now you must figure out not only how to keep the prisoners alive, but how to also ensure their eventual freedom. When can any one of them be certain they've all been in the central chamber of the dungeon at least once? And how? Don't try to imagine any trickery like scratching messages in the soft gold of the chalice. The problem is as simple as it sounds. The prisoners have absolutely no way of communicating with each other except through the two orientations of the chalice. If any of them attempts any trickery at all they will all be beheaded. All the prisoners can do is turn the chalice upside down or right side up, as they choose, whenever they are called into the chamber.
(written by a former roomate)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
I'll ponder it some - just so I'm sure, you can't bash the kings brains in out of frustration using the chalice, right?
Re:The King and the Chalice (only for Experts!) (Score:3, Funny)
The king knows Kung Fu.
Re:The King and the Chalice (only for Experts!) (Score:3, Funny)
Shouldn't that be King Fu?
-ba-dum-dum!-
Re:The King and the Chalice (only for Experts!) (Score:4, Informative)
*Spoiler* Don't read the following if you don't wanna know the answer:
1) The prisoners elect one of their own to be a counter, the rest we will call non-counters.
2) When a non-counter comes into the chalice room, if he can he will put the chalice right side up. If it's already right side up, he'll leave it alone. However, each non-counter will only do this once. If he's already flipped it in the past, and it's upside down, he'll leave it upside down.
3) Every time the counter comes in, he checks the chalice. If it's upside down, he'll do nothing. If it's right side up, he'll flip it, and add one to his count. Once he's flipped it n times (n being the prisoner count), he knows everyone has done it. If the original state of the chalice is known, the problem can be modified so he only needs to flip it n-1 times.
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
But there are other ways to solve the problem. I posted an idea of mine here [slashdot.org], and while it could probably be refined, I don't see any immediate problems with it that would render it infeasible.
Re:The King and the Chalice (only for Experts!) (Score:2)
Also, he could use his ability to change the cup every time a non-counter changes the cup. If he did that, then the prisoners would remain imprisoned forever as the counter would never reach n.
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2, Informative)
Re:The King and the Chalice (only for Experts!) (Score:2)
What if there are 20 prisoners and he only lets each in there twice, but brings in everyone in a row. Then the counter gets to two and its game over.
Re:The King and the Chalice (only for Experts!) (Score:2, Informative)
One person is appointed the leader. He always turns the cup upside down. Everyone else enters. If the cup is right side up, they leave it, if it upside down, they put it right side up, but only if they previously have not flipped the cup. So the only time the leader would flip the cup is if another prisoner had already been in the room.
So how to deal with the fact that the King can flip the c
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
One other change (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
I suspect that playing with this possible negation
Re:The King and the Chalice (only for Experts!) (Score:2)
Doesn't matter. Assume the king flips it k times and calls everyone but one guy so often that they each flip it their maximum number of times. Then you will have (using my previous correction that it should be (n-1)(k+1)) (n-2)(k+1)+k flips (or (nk+n-k-2)), which is one less than the (n-1)(k+1) (or nk+n-k-1) that they are looking for. Now since everyone other than the last prisoner has already flipped it
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
No, because they will get to (n-1)(k+1) on their own eventually, once all the non-leaders have flipped the chalice k+1 times.
Re:The King and the Chalice (only for Experts!) (Score:2, Informative)
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtm l#100prisonersLightBulb [berkeley.edu]
http://www.ocf.berkeley.edu/~wwu/papers/100prisone rsLightBulb.pdf [berkeley.edu]
(the latter paper mentions a slashdotting, btw)
also see:
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtm l#100prisoners2LightBulbs [berkeley.edu]
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Not even close.
Re:The King and the Chalice (only for Experts!) (Score:2)
I brought the productivity of the entire student work force at Sandia Natl Labs down to zero this summer by posting this problem on their message boards.
Just so you know, the only person who I know legitimately solved this problem (none of the students at SNL could get it) worked at it for a couple weeks before getting the solution, albeit not the optimal solution.
Re:The King and the Chalice (only for Experts!) (Score:2)
One minor modification (Score:2)
The only thing I can add to this is that the number of meddlings the king can do is actually k+1, as he gets to set the default chalice position (up / down). So, much like N = n - 1, K should equal k+1.
Re:The King and the Chalice: full solution (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:3, Interesting)
Obviously, the most devious thing that the king can do is to always make sure the chalice is rightside up. Therefore, it will always be rightside up. Therefore, the chalice can provide no information. Therefore, it is a red-herring.
With all other avenues of gathering information forbidden, there seems no information left to base an answer on.
Re:The King and the Chalice (only for Experts!) (Score:2)
No, since he can only move it k times.
I think it is a word puzzle (Score:2)
When the numbers become meaningless look at the meaning behind words.
The setup is a central room (the king room) with cells around it. Basically a lot of the story keeps pointing out that the room with the king is central to the setup with the cells surrounding it. Since cells are typically only build with 1 door it then becomes logic to assume that each prisoner as he was l
MOD PARENT UP (Score:2)
Re:MOD PARENT UP (Score:3, Insightful)
The chalice is not a red herring . . . (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
If we can prove that the king could be forced to flip the chalice once, we can prove that the prisoners can go free. I believe the opposite is also true -- if the king cannot be forced to flip the chalice, the prisoners at best will spend life in priso
Re:The King and the Chalice (only for Experts!) (Score:2)
This is of course assuming that the prisoners are not able to wait an in
Re:The King and the Chalice (only for Experts!) (Score:2)
Neither do I, of course, but your comment has some rather blatant errors in it. First of all, the inmates cannot wait an *infinite* time, but they can wait an arbitrary time - that is, for any finite amount of time t, they can wait for that amount.
The part about "what if the prisoners have waited for an infinite amount of time" is rubbish, too - the state the whole system is in simply isn't well-defined if you attempt to take the limit. In fact, considering
Re:The King and the Chalice (only for Experts!) (Score:3, Insightful)
Sure he can. Read your own damn problem.
That means the king may turn an upright cup upside down or vice versa up to k times
Up to K times means K or less. Therefore, K is any number. Therefore, the king can do whatever the hell he wants, and the calice provides no information.
Or let's suppose it has to be EXACTLY k times. Either K or zero. Fine. I declare K to be 1.
In this case, if the challice is upside down, the king chooses to flip it K times. If it is rightside up, then the king chooses to f
Re:The King and the Chalice (only for Experts!) (Score:2)
MOD PARENT DOWN (Score:2)
MOD PARENT DOWN (Score:3, Insightful)
Your description of the problem does not say when k is fixed. A perfectly valid reading of the problem is to suppose that the prisoners are told that the king will decide k when the game begins.
You ought to admit that the problem was unclear, instead of insulting everyone who interprets your ambiguity the wrong way.
Re:The King and the Chalice (only for Experts!) (Score:2)
The real question is whether the prisoners know the value of k in advance or not.
Re:The King and the Chalice (only for Experts!) (Score:2)
So when all prisoners work out not to change the chalice, when a prisoner has seen the chalice been turned k times, he can safely assume the king has spent his turning actions and then the chalice can start conferring information.
However, since the king may decide never ever to turn the chalice, prisoners might still stay pretty much indefinitely, same if the ki
Questions (Score:2)
1. Do the prisoners know k?
2. Define "arbitrary number of times."
These are my sticking points. Based on my questions, I'm sure you can guess the strategy I'm going after from the problem I solved before. My other question is this: Am I on the right track by iterating
Re:The King and the Chalice (only for Experts!) (Score:2, Insightful)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
What's the difference in this case? Does it have any relevance to the problem?
The OP's description may be accurate but it adds nothing and simply confuses the nonmathematical reader.
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
1)Is the value of k known (in advance) by the prisoners?
2)"The only rule the king has to obey is that eventually he has to call every prisoner in an arbitrary number of times."
Does this mean that at some point, all prisoners have been called in the same number, n, of times? [Where n is unknown, but is at some point equal for all prisoners]
Re:The King and the Chalice (only for Experts!) (Score:2)
It's a comms theory problem. Assume the simple case where n=2. Prisoner 0 (p0) needs to communicate an "I've been in the room" message to prisoner 1 (p1). Once p1 receives that message he can answer "yes" and both prisoners go free.
However the only communication method is a chalice which is a lossy channel because the King can introduce k errors per message. In other words, for every k+1 bits communicated, only 1 bit is reliably transmitted. Fortunately the problem of transmitting data over a lossy channe
Worst puzzle evar (Score:2)
With the king able to manipulate the chalice, there is absolutely no way for them to communicate to eachother, because the king can always turn the chalice back to the way it was before the prisoner entered the room. So every prisoner will always see the exact same thing. Stupid, stupid.
Re:Worst puzzle evar (Score:2)
Yes, you are. k is not undefined. k is a number that the king and prisoners know ahead of time.
So the solution is (Score:2)
They choose a watcher
If the watcher is called and the cup is upside down he flips it right side up
If anyone else is called and the cup is right side up they flip it to be upside down, unless they've done it previously in which case they leave it alone.
When the watcher has flipped the cup n+k+1 times he says yes.
Since the King can only interfere k times, you have to out wait him, hence +k.
The +1 is because the cup may not be right side up on first time.
Being
this doesn't work (Score:2)
I suppose you could have the watcher flip the chalice at some point to tell the other to report gain, but the lack of limits on the number of times someone can be called makes it hard to specify any strategy.
Sounds reasonable (Score:2)
Re: Seems to be it cannot be solved (Score:2)
If there only is a solution that relies on the king flipping the chalice k times, then the prisoners are boned, since the king is not obliged to flip it at all.
If there is a solution that does not rely on the king flipping the chalice k times, then the king (knowing the solution and the complete state of the game) can simply wait unt
Solution (Score:2)
There's two main problems here:
1. You don't know the initial state of the cup.
2. You don't know what the king has been screwing with.
These are actually the same problem, in that the state of the cup might have been tampered with and you have to route around it.
In the simplest problem (uncertain initial state only), you could have ea
Re:The King and the Chalice (only for Experts!) (Score:2)
First of all, you need a code that can correct about O(k) raw bit errors in a transmitted raw message (k is probably sufficient, but I'm not an expert in coding theory, and this is a detail, anyway ^_~). The prisoners will use this code to send logical bits to each other. The choice of code guarantees that the king's ability to introduce k errors into the raw communication channel (the chalice) will not affect the logical bits transmitted.
Now, the basic idea is that, starting with
Re:The King and the Chalice (only for Experts!) (Score:2)
If the King has effectively unlimited flips, he simply ensures the chalice is upright every time he calls a prisoner, there is no communication stream, and therefore no way for the chalice to signal anything to the others.
As long has you have a malicious interception and corruption of the information medium, the King can manipulate the message any way he sees fit, including sending his own "I've seen it" messages from any prisoner(s) that he never has to call to any prisoner(s) he
Proofs: No general solution, no "watcher" solution (Score:2)
Proof: no solution for k > n * a
Let k > n * a
This means the king can flip the challice once for every time a prisoner is called in to see him. So he can, for example, always turn the challice up before each prisoner is called in. He will select a permutat
MOD PARENT TROLL (Score:4, Informative)
Re:The King and the Chalice (only for Experts!) (Score:2)
"Since I first locked you and the other prisoners into your rooms, have all of you been in this room yet?"
RTFP (Score:2)
"Since I first locked you and the other prisoners into your rooms, have all of you been in this room yet?"
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice - Answer?? (Score:2)
You're the 3rd person to suggest that. You might want to try reading the problem again.
Re:The King and the Chalice (only for Experts!) (Score:2)
Nope.
Re:The King and the Chalice (only for Experts!) (Score:2)
One thing I notice everyone doing is assuming that the chalice starts out rightside up.
Re:The King and the Chalice (only for Experts!) (Score:3, Insightful)
This solution requires that each prisoner is guaranteed to be called to the room infinite number of times. Otherwise, if there's a maximum number of times t that a prisoner can be called to the room, then the king could select k = number of prisoners, call each one t times in a row, resetting the chalice to original pos
Maybe this variation is a better solution (Score:2)
"2) Everyone else, upon finding an upright chalice, turns it upside down. Otherwise, they leave it. They each must turn it over exactly 3k+1 times, where k is the number of times the king can move the chalice."
I've only had one coffee, so I'm not going to work the numbers, but if
Not exactly (Score:2)
Re:Not exactly (Score:2)
The "only two people have ever solved it" seems nonsense to me too. If this is genuinely the case, and the solution is as hideously complex as the OP seems to take such glee in stating, either the
Re:Not exactly (Score:2)
But this solution takes that into account. If the king never flips it, we still will get to (n-1)(k+1) on our own once everyone has flipped it the maximum number of times. If he does flip it k t
Re:Not exactly (Score:2)
1. The prisoners number themselves sequentially from 1 to n; call the prisoners P.1 to P.n
2. The prisoners all keep track of the number of priso
Re:Not exactly (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:Solution? (Score:2)
Re:The King and the Chalice solution(hopefully) (Score:2)
I can see a fault (?) (Score:2)
It's a nice solution otherwise.
"The king will call the prisoners in any order he pleases, and he can call and recall each prisoner as many times as he wants, as many times in a row as he wants. The only rule the king has to obey is that eventually
Not happy (Score:2)
I can see what you mean, but only if I ignore this sentence:
"and he can call and recall each prisoner as many times as he wants"
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2, Funny)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:3, Insightful)
In your original posting the language leaves much open to speculation because you spend several sentences clarifying one point and casually make another point. Ex: You dwell on the point that the cells are sound proof but make no mention of other senses such as sight. Is there a window from the cells to the central room? You dwell on the m