PDA

View Full Version : math riddle: King and His Prisoners (no content, long)


11-18-2005, 02:45 PM
Had some fun with this couple weeks ago. Enjoy if you like this kind of stuff:

There is a king and he has 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 any 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.

The prisoners have a brief amount of time to come up with a strategy before they are put into their seperate cells. But while they plan, the king can plainly overhear them. What strategy should they choose to correctly answer the king's question and gain their freedom?

Tom1975
11-18-2005, 03:19 PM
bum rush the king and beat him to death with the chalice?

jman220
11-18-2005, 03:23 PM
[ QUOTE ]
Had some fun with this couple weeks ago. Enjoy if you like this kind of stuff:

There is a king and he has 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 any 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.

The prisoners have a brief amount of time to come up with a strategy before they are put into their seperate cells. But while they plan, the king can plainly overhear them. What strategy should they choose to correctly answer the king's question and gain their freedom?

[/ QUOTE ]

Everyone says yes, and at least one of them is going free.

11-18-2005, 03:27 PM
Remember, if one prisoner answers incorrectly, they are all killed. There is a way for the prisoners to win.

TomCollins
11-18-2005, 04:50 PM
Do the prisioners know what k is?

11-18-2005, 05:11 PM
[ QUOTE ]
Do the prisioners know what k is?

[/ QUOTE ]

Yes.

11-18-2005, 07:09 PM
I got a PM asking if the prisoners can mark the chalice or rotate it, or otherwise use it communicate other than flipping it up or down. The answer is no, they can only flip it.

11-18-2005, 07:11 PM
Do the cells share doors?

11-18-2005, 07:16 PM
[ QUOTE ]

Do the cells share doors?

[/ QUOTE ]

They do not; and there is no way for the prisoners to communicate between the cells.

SteamingFish
11-18-2005, 07:32 PM
[ QUOTE ]
[ QUOTE ]
Do the prisioners know what k is?

[/ QUOTE ]

Yes.

[/ QUOTE ]
They know k? Or did you mean n? If it's k, I might just freak out. /images/graemlins/wink.gif

11-18-2005, 08:07 PM
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Do the prisioners know what k is?

[/ QUOTE ]

Yes.

[/ QUOTE ]
They know k? Or did you mean n? If it's k, I might just freak out. /images/graemlins/wink.gif

[/ QUOTE ]

The prisoners know n and k. So does the king.

11-18-2005, 08:07 PM
Before getting out pencil and pad, I wanted to be certain
the prisoners' pass through the central rooms to their
cells didn't qualify as having been in the room. Your
answer and a re-read eliminate such a solution.

The prisoners know k; do they know n?

Are the chalice and the cup the same object? That is, are
the prisoners and the king manipulating the same object?

11-18-2005, 08:15 PM
[ QUOTE ]
Are the chalice and the cup the same object? That is, are the prisoners and the king manipulating the same object?

[/ QUOTE ]

Yes, the chalice is the cup. They are one and the same.

SumZero
11-18-2005, 08:26 PM
Take the answer for k=0 (which is the typical problem). Now have each prisoner do what they have do once in the k=0 solution k more times. And have the "special" prisoner change his counting scheme to account for the (k+1)*n chalices. I think that works. There might need to be a tweak since the king can turn the chalice each direction or can not do anything, but I think it is just a wrinkle of what I've (intentionally vaguely) described.

11-19-2005, 01:52 AM
I thought this post was a joke. I gave up after 30 minutes and said "there is no way you can solve this"

I figured the only solution is something riddle-esque like "they were all in the room in the beginning, so the answer is always Yes" or "the prisoners are siamese n-tuplets" something stupid.

Anyway, I found the solution doing a google search and now I feel like a moron. Nothing like a good puzzle to make you hate yourself.

Great post!

Luzion
11-19-2005, 04:13 AM
Is this even possible? I know of a solution if the King doesnt get to mess with the chalice from a variant of this riddle. But the ability of the King to mess with, or NOT to mess with the chalice seems to make this impossible.

11-19-2005, 07:02 AM
Since you know the solution when k=0, just alter it slightly...

Given the strategy of the prisoners, understand there is a point when the count will no longer increase for the counter. With k=0 and the sol'n you know, this point is exactly n-1. When k is non-zero there is a lower/upper limit to this count depending on if the king works to increase/decrease/not effect the count. Call the limits on this range [A,B]

So what do we do...well...
For any other k, let the prisoners effect the chalice Y times (for k=0, Y=1), where Y makes the following true:

The lowest possible total count (A) when all n-people have been in the room is greater than the maximum possible total count (B) when fewer than n-people have been in the room.

From here you have some algebra to determine Y. Plus you have a point where the counter can be sure everyone has been in the room.

I hope I worded this correctly...but, yes it is still possible.

11-19-2005, 10:20 AM
[ QUOTE ]
Is this even possible? I know of a solution if the King doesnt get to mess with the chalice from a variant of this riddle. But the ability of the King to mess with, or NOT to mess with the chalice seems to make this impossible.

[/ QUOTE ]

It is possible, there is a solution. Drizzle is on the right track but hasn't gotten it yet.

11-19-2005, 11:18 AM
I guess I will add to my previous post.

Break the prisoners into two groups: one counter, and then everyone else (n-1).

The counter follows these rules when called:
1. If the cup is down, do nothing.
2. If the cup is up, flip it down and increment running total.

The (n-1) non-counters do this:
1. If the cup is up, do nothing.
2. If the cup is down, flip it unless you have flipped it Y times already.

We need to find some number where the counter can be certain that everyone has been in the room. If you analyze the strategy you see that the King can use his flips to drive the largest possible count up or down as he sees fit.

We are looking for the condition where all prisoners have been in the room. (1)

The largest count that can exist without (1) being met is A*(n-2) + k. This is all but 1 non-counting prisoner using the max. flips and the King using all of his moves to drive up the count.

When all prisoners have been in the room, the count will lie between [0,A*(n-1)+k] In fact, the count will never increase beyond A*(n-1)+k given the strategy we have defined. Given all of the King's strategies, the smallest UPPER bound is A*(n-1)-k. So the upper bound must lie on [A*(n-1)-k,A*(n-1)+k]

If we can find an A, such that A*(n-1)-k is greater than A*(n-2)+k then we have our solution. Why? Because we have found a count that we are guaranteed to eventually reach that is larger than any count where (1) is not met.

A(n-1)-k > A(n-2) + k
- A - k > - 2A + k
A > 2k
The smallest such A is 2k+1, but any A larger than that will also work.

(2k+1)(n-1) - k = 2kn + n - 3k - 1
When the count reaches '2kn + n - 3k - 1' the counter can say "Yes"

11-19-2005, 05:49 PM
I'm going to take a stab at this, and I haven't read any of the other posts. First, the prisoners have to appoint a counter. Next, the strategy has to be that the first K+1 times (where K = no. of times the King can touch the chalice) a non-counting prisoner enters the chamber and the chalice is up, they have to put it face down. If they enter the chamber and it's face down, or if they have already changed it to face up K+1 times, the non-counter will not touch the chalice. The counter's job will be to always change the chalice from face down to face up, and to count how many times he's done this. Once he has counted up to K+ N (N = total prisoners), he will know that all of the prisoners have entered the room. The first 1 is necessary because it's possible that the counter will be the first person into the room, and the chalice will start face down.

For example, if the king could mess with the chalice twice, and there were only 3 prisoners (a,b,c) and a was the counter, a possible sequence could go like this:

b enters and chalice is down
a enters, turns chalice up (1)
b enters, turns chalice down (1)
c enters
a enters, turns chalice up (2)
b enters, turns chalice down (2)
King enters, turns chalice up (1)
b enters, turns chalice down (3)
a enters, turns chalice up (3)
c enters, turns chalice down (1)
King enters, turns chalice up (2)
a enters
c enters, turns chalice down (2)
b enters
a enters, turns chalice up (4)
c enters, turns chalice down (3)
a enters, turns chalice up (5), and tells the king they've all been to the room.

11-19-2005, 06:18 PM
Using your numbers 3 prisoners, King 2moves.

b enters and chalice is down
a enters, turns chalice up (1)
King turns chalice down
a enters, turns chalice up (2)
King turns chalice down
a enters, turns chalice up (3)
b enters, turns chalice down
a enters, turns chalice up (4)
b enters, turns chalice down
a enters, turn chalice up (5) And everyone dies!

11-19-2005, 06:21 PM
I just realized this is wrong, because the counter, A, could be faced with 6 down chalices which he flips up and C could not have even entered the room (given N =3 and K =2):

A enters, chalice down, flips up (1).
King enters, flips down (1).
A enters, flips up (2).
King enters, flips down (2).
A enters, flips up (3).
B enters, flips down (1).
A enters, flips up (4).
B enters, flips down (2).
A enters, flips up (5).
B enters, flips down (3).
A enters, flips up (6).


This leaves me with a problem.... If the counter toggles the cup 7 times -- generally NK - K + N times -- he can confidently say that all the prisoners have visited the room. However, sometimes the chalice will only be toggled by the counter (N-2)(K+1)+1 times, or with K=2 and N=3 4 times:

B flips down (1)
K flips up (1)
B flips down (2)
K flips up (2)
B flips down (3)
A flips up (1)
C flips down(1)
A flips up (2)
C flips down (2)
A flips up (3)
C flips down (3)
A flips up (4)

So, if the counter flips the chalice up NK - 2K +N +1 times, and the chalice never moves again, can he ever be sure? This is an interesting problem....

11-19-2005, 07:01 PM
Sorry to clog this thread -- this will be my last addition. If A has flipped the chalice between NK - 2K + N - 1 and NK - K + N - 1 times and he returns to the room 5 times and the chalice is still up, he can flip the chalice sideways to the left. Then, each of the non-counting prisoners, when they see the chalice is sidways to the left AND they have already flipped the chalice face down K + 1 times, can flip the chalice sideways to the right the first to K+1 times they find it pointing left and not touch it again. This way, the counter will start a new count (number of toggles from left to right). If he started the sideways signal prematurely, he will be faced with a chalice moved down, which he can toggle up and add to his original count. If not, he will count to NK - K + N number of left toggles before telling the king they've all been to the room.

Example: (K = 2; N = 1)

B enters and flips down. (1)
K enters flips up. (1)
B enters and flips down. (2)
K enters and flips up (2)
B enters and flips down (3)
A enters and flips up (1)
C enters and flips down (1)
A enters and flips up (2)
C enters and flips down (2)
A enters and flips up (3)
C enters and flips down (3)
A enters and flips up (4) -- equal to the lower bound of NK - 2K + N - 1.
C, B, A, B, A, C, C, A, B, C, B, A, B, and A enter and do nothing. Chalice still up.
After reaching a count between NK - 2K + N -1 and NK - K + N, AND seeing the chalice still up after 5 visits, A flips the chalice sideways to the left and starts a new count to NK - K + N sideways flips. If the chalice were to be flipped down (meaning one of the prisoners hadn't reached their K + 1 quota of down flips), then the counter will erase his new count and resume the first count.

One possible sequence:

B enters flips down (1).
A enters flips up (1).
B enters flips down (2)
A enters flips up (2)
B enters flips down (3)
A enters flips up (3)
C enters flips down (1)
A enters flips up (4)
A enters 5 times in a row seeing the up-facing chalice.
A flips chalice left (1)
K flips chalice right (1)
A flips chalice left (2)
K flips chalice right (2)
A flips chalice left (3)
C flips chalice down (2)
A flips chalice up, resumes count (5)
C flips down (3)
A flips up (6) --- (upper bound of the uncertainty zone of counter's flips (F), such that NK - 2K + N - 1 <= F <= NK - K + N - 1)
A visits 5 times, seeing up chalice. Resumes sideways count left (1)
B flips right (1)
A left (2)
B right (2)
A left (3)
B right (3)
A left (4)
C right (1)
A left (5)
C right (2)
A left (6)
C right (3)
A right (7) -- tells king they've all been there, as he reached NK - K + N sideways "all clear" left flips.

chunk
11-21-2005, 04:17 AM
[ QUOTE ]
The prisoners have a brief amount of time to come up with a strategy before they are put into their seperate cells. But while they plan, the king can plainly overhear them. What strategy should they choose to correctly answer the king's question and gain their freedom?

[/ QUOTE ]

Are you sure?
If the king knows who the counter is then would't he be the first one invited into the center room and then left forever in his cell?

SteamingFish
11-21-2005, 04:02 PM
Perhaps they all need to be counters? How do they know k? Couldn't the king simply set the chalice to whatever state it was in before calling in each prisoner? That way, it would always look like it was untouched by anyone else to the current prisoner. Or is that not true if they know k? My brain hurts.

mosdef
11-21-2005, 04:06 PM
[ QUOTE ]
If the king knows who the counter is then would't he be the first one invited into the center room and then left forever in his cell?

[/ QUOTE ]

No. The "rules" stipulate that each of the prisoners must be called out at least x times for all x. So the counter must be called as many times as he wants.

11-21-2005, 04:07 PM
[ QUOTE ]
Perhaps they all need to be counters? How do they know k? Couldn't the king simply set the chalice to whatever state it was in before calling in each prisoner? That way, it would always look like it was untouched by anyone else to the current prisoner. Or is that not true if they know k? My brain hurts.

[/ QUOTE ]

K is known by the prisoners. The king can change it after he calls in the prisoner, up to a maximum of k times. The king must call every prisoner any arbitrary number of times, so we can always set that number of times to be greater than K.

11-21-2005, 04:44 PM
[ QUOTE ]
(2k+1)(n-1) - k = 2kn + n - 3k - 1
When the count reaches '2kn + n - 3k - 1' the counter can say "Yes"

[/ QUOTE ]

This is correct, congratulations! /images/graemlins/smile.gif

jedi
11-21-2005, 07:55 PM
[ QUOTE ]
I thought this post was a joke. I gave up after 30 minutes and said "there is no way you can solve this"

I figured the only solution is something riddle-esque like "they were all in the room in the beginning, so the answer is always Yes" or "the prisoners are siamese n-tuplets" something stupid.

Anyway, I found the solution doing a google search and now I feel like a moron. Nothing like a good puzzle to make you hate yourself.

Great post!

[/ QUOTE ]

Knowing that I woudln't solve this on my own, I googled it as well. The first hit was this thread /images/graemlins/smile.gif

11-21-2005, 08:33 PM
[ QUOTE ]
Knowing that I woudln't solve this on my own, I googled it as well. The first hit was this thread /images/graemlins/smile.gif

[/ QUOTE ]

Ha, makes me feel bad, I got the puzzle from slashdot.

chunk
11-22-2005, 02:31 AM
[ QUOTE ]
[ QUOTE ]
If the king knows who the counter is then would't he be the first one invited into the center room and then left forever in his cell?

[/ QUOTE ]

No. The "rules" stipulate that each of the prisoners must be called out at least x times for all x. So the counter must be called as many times as he wants.

[/ QUOTE ]

that's not how I read it.

[ QUOTE ]
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 any 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.

[/ QUOTE ]

Lets say John is the counter. King calls john on day 1 ( and each consecutive day until our arbitrary number has been met). John then stays in his cell until he his dead never having counted at all. Game over.

mosdef
11-22-2005, 08:09 AM
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
If the king knows who the counter is then would't he be the first one invited into the center room and then left forever in his cell?

[/ QUOTE ]

No. The "rules" stipulate that each of the prisoners must be called out at least x times for all x. So the counter must be called as many times as he wants.

[/ QUOTE ]

that's not how I read it.

[ QUOTE ]
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 any 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.

[/ QUOTE ]

Lets say John is the counter. King calls john on day 1 ( and each consecutive day until our arbitrary number has been met). John then stays in his cell until he his dead never having counted at all. Game over.

[/ QUOTE ]

You're missing the point. The arbitrary number can never be met. It isn't set in advance. We're saying that each prisoner will be called out an infinite number of times.