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
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
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.
how is it fundamentally different? the only thing different (that i can see) is that the counter adds k to n to be sure to have ruled out any meddling done by the king.
this is a good problem, btw, direct application to embedded system where all you might have is a single flip-flop . . .
On the Berkeley site, they say that one solution takes 27-28 years. The solution that everyone has been talking about here is the one where there is a leader and 99 followers. Each time a follower sees the bulb off, he will turn the bulb on if he hasn't turned it on already. The leader will always turn the bulb off when it is on. When the leader turns it off 99 times, he knows that everyone has visited the room. I ran a simulation using this algorithm and it takes on average about 10440 days, or 28.6 yea
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
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, Informative)
http://www.ocf.berkeley.edu/~wwu/riddles/hard.sht
http://www.ocf.berkeley.edu/~wwu/papers/100prison
(the latter paper mentions a slashdotting, btw)
also see:
http://www.ocf.berkeley.edu/~wwu/riddles/hard.sht
Re:The King and the Chalice (only for Experts!) (Score:2)
Re:The King and the Chalice (only for Experts!) (Score:1)
this is a good problem, btw, direct application to embedded system where all you might have is a single flip-flop . . .
mr c
Re:The King and the Chalice (only for Experts!) (Score:1)
I think I have solved it:
http://slashdot.org/comments.pl?sid=165444&cid=13
Re:The King and the Chalice (only for Experts!) (Score:1)
I ran a simulation using this algorithm and it takes on average about 10440 days, or 28.6 yea
Re:The King and the Chalice (only for Experts!) (Score:1)
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaB
Re:The King and the Chalice (only for Experts!) (Score:2)