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

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!

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....

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]

[ 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]

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]

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

[ 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! [img]/images/graemlins/smile.gif[/img]

[jedi]

[ 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 [img]/images/graemlins/smile.gif[/img]

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

[/ QUOTE ]

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