[unreality]

A logic-loving and merciful king gathers a meeting of all of his death row inmates. The room can only fit 11 max (and all prisoners know this and know that all prisoners know this), so including the king, it means that the number of prisoners is 10 at most, but each prisoner can only see 2 other prisoners since they are all in a line.

"There are no less than three of you," the king confirms. "And no more than ten- however, I will not say the exact number of prisoners. Now, since I am a kind and merciful king, I have devised a little game that will test your skills to the limit. If you succeed, all of you will be released. But if somebody makes a false guess, everyone is executed. If nobody makes a guess within 5000 hours, everyone is executed anyway. You cannot risk the lives of you and your fellow prisoners, so you may only make a guess that you know is 100% correct... even if the chances are 99.9%, and even if it's the 4999th hour and everyone dies the next hour anyway. That is, you must give me reasoning with your guess to show that it is, for sure, 100% correct. Is that clear?"

The prisoners nodded obediently, excited at their chance for freedom.

"Good," continued the king. "Now for the game... but first, I must warn you. I do not know if there is a successful method. This is a little test of mine, to test your skills. Maybe it's possible, maybe it's not. Maybe you can think of a way, maybe not. But thank me for being such a merciful king and giving you such a chance."

"Thank you," they mumbled.

"Now," said the king, smiling a little. "Here is the game: I have a room, nearby, which has three knobs. The knob's original use is long gone, but you can still see their settings: 0, 1 or 2. Each hour starting 1 hour from now, a random prisoner will be selected, with no regards to previous selections, and sent into the room. The prisoner will be watched, and thus is only allowed to change one knob. The knob can be set to any of the three values, though there is no between-states, the knob clicks between those three values only (0,1,2). And remember, you are being watched. There can be no modification of the room in any other way, it will be reset. The only thing you can do is to pick ONE knob and change it. The knobs are clearly labeled A, B and C, and these labels will not change in any way. The knobs will not change in any way other than a prisoner adjusting it to 0,1,2, and nobody else will tamper with the knobs. You guys win the game if someone, anyone, can guess when every single prisoner has been in the room. It has to be foolproof, 100% correct. If the guess is made [correctly], everyone goes free... seem impossible? However," the king said. "You will be allowed to plan your strategy through anonymous letters via me. I will make sure there is no way to discern how many prisoners there are via the letters - that could be anything from 3 to 10, nobody knows. But in the letters, you CAN discuss strategy, so that everybody knows what to do."

The prisoners attempt a few ideas, but can't agree on anything.

You are the one of the prisoners. Do you have a brilliant plan that will save everyone?

1) Only a 100%-sure guess can be made, ie, a guess is made correctly, OR no guess is made until the 5000th hour, at which the prisoners are executed

2) Assume that the prisoners can keep track of time in their cells

3) No changing anything except those three knobs to three values each (0,1,2). And you can only change ONE knob in your visit

4) the prisoners cannot communicate in any way except for the knobs

5) There are two possible starting positions: (the king tells them [truthfully] which it is)

5a) the knobs start at all-zero (000)

5b) the knobs start randomly, ie, each knob has a 1/3 chance to be 0, 1/3 to be 1, and 1/3 to be 2

Can you make it work with 4b, let alone 4a?

Please use spoilers, thank you

edit: minor typo

Edited August 31, 2008 by unreality

[HoustonHokie]

May as well start with the really simple stuff...

Assuming the three knobs all start at 0, first time visitors turn knob A to 1 and then to 2. If a new visitor comes in and sees 2 on A and 0 on B, he turns B to 1. The next new visitor turns A to 0, then 1. If a new visitor sees 1 on A and 1 on B, he turns B to 2 and the next new visitors turn A to 2 and then to 0. The ninth new visitor, finding A at 2 and B at 0, turns A to 0. Any repeat visitors turn dial C. When a new visitor comes in and finds A & B turned to 0, they know they are the 10th visitor and the maximum has been reached; therefore they tell the king they know that there are 10 prisoners and everyone lives.

Unfortunately, there is no guarantee that all prisoners will enter the room - it is highly likely, but not guaranteed in the king's speech. I don't know if the king would accept this as 100% certainty, but the prisoner who enters at the 4999th hour could read the dials and know how many prisoners have entered and guess that number.

similar to my reasoning above, except it requires the first prisoner (or the second, if the first two prisoners are different) to enter after the last prisoner. The first prisoner turns C this time, and the others turn A & B at the same points. If the first (or first two) prisoners enter and find the dials the way they were at the start, they know 10 prisoners have entered and can make their guess.

Those are all my guesses. I think everyone dies otherwise. Unless someone's got a get out of jail free card...

[Guest]

Since the room can have only 11 men, that means the king, with out his royal guard, is alone in a room with 10 desperate convicts. He gets taken hostage and the prisoners demand a chopper and $10 Million in small bills and head off to the Bahamas.

I am assuming that each prisoner has to mandatorily turn a knob or all will be reset

One prisoner sends out the following instructions via letter:

The 2 prisoners,at the end of the line who can see only one neighbour will turn only the C Knob.

Each of the others, if entering the room for the first time, will turn the A or B knobs in the following order depending on the existing combination.

If they are entering the room for second time or more, the person will turn the C knob

5A

A B Move

first 0 0 B1

second 0 1 B2

third 0 2 A1

fourth 1 2 A2

fifth 2 2 B0

sixth 2 0 A0

seventh 0 0 A1

eighth 1 0 declare 10

5B

A B Move

first 1 2 A2

second 2 2 A0

third 0 2 B0

fourth 0 0 A1

fifth 1 0 A2

sixth 2 0 B1

seventh 2 1 A0

eighth 0 1 Declare 10

Ofcourse the last combination is not arrived at by the 4999th hour, the occupant can declare the number depending on the A & B Knob combination.

[Guest]

Oops! seems to have a formatting malfunction.

For 5A

first convict with 2 neighbours sees A0 B0 and turns B1

second sees A0 B1 and turns A1

third sees A1 B1 and turns A2

fourth sees A2 B1 and turns B2

fifth sees A2 B2 and turns A0

sixth sees A0 B2 and turns A1

seventh sees A1 B2 and turns B0

eighth sees A1 B0 declare 10

For 5B

first sees A1 B2 and turns A2

second sees A2 B2 and turns A0

third sees A0 B2 and turns B0

fourth sees A0 B0 and turns A1

fifth sees A1 B0 and turns A2

sixth sees A2 B0 and turns B1

seventh sees A2 B1 and turns A0

eighth sees A0 B1 declares 10

[Guest]

I don't think this is possible given the restrictions… there is a small*, but none zero, chance that one prisoner out of a group won't get to visit the knob room at all over the 5000 hour period. There's a chance that one poor prisoner** will visit the room 5000 (4999?) times, and thus will have no other information on the number of prisoners other than that he can see two.

But… if you're willing (and the king lets you) to take that small chance that someone hasn't been in, its fairly simple to use the first two knobs to keep a count of the number of prisoners that have gone through (you've got 9 settings for two knobs, and there are only eight different numbers of prisoners) and you can use the third knob as a 'do nothing' device.

Another possibility would be to only sending one letter each per hour (although the king seems to rule out the tactic of using the letters to send information on the number of prisoners)

I believe that if, and only if, all ten prisoners visit the room, then the counting method you are using will have reached maximum, and you can guarantee there are ten prisoners. If there are fewer prisoners then I don't think you will be able to distinguish between say 9 prisoners all visiting the room and only 9 out of ten prisoners visiting the room

* (9/10)^5000 (assuming ten prisoners)

** 1/(10^5000) (assuming ten prisoners)

[peace*out]

Since the room can have only 11 men, that means the king, with out his royal guard, is alone in a room with 10 desperate convicts. He gets taken hostage and the prisoners demand a chopper and $10 Million in small bills and head off to the Bahamas.

Well they do have cameras, but that's not unlikely.........

[peace*out]

Do you have to change a knob?

If not, take your stratages with the knobs starting at 000 and go up. if you've already been in the room, don't do anything.

just a thought

[Guest]

"Now," said the king, smiling a little. "Here is the game: I have a room, nearby, which has three knobs. The knob's original use is long gone, but you can still see their settings: 0, 1 or 2. Each hour starting 1 hour from now, a random prisoner will be selected, with no regards to previous selections, and sent into the room.

You guys win the game if someone, anyone, can guess when every single prisoner has been in the room.

Not possible.

Since it is a random selection, the king can cheat and not send a particular prisoner into the room ever, so they will wait till 5000 hrs and all the prisoners will get killed

[unreality]

clarifications:

1) You don't have to turn a knob if you don't want to

2) Yes, there is a chance that not all prisoners will go... if there are 7, the first 6 could even rotate without the 7th ever visiting. However, that doesn't affect your answer. Your answer would still be 100% certain if all have been to the room. If not all get to the room, your 100% answer opportunity will never come up. So even if it's the same prisoner over and over, your 100% correct answer would still be 100% correct answer if it got the opportunity to work. See what I mean?

3) So you can:

3a) just assume that all prisoners get sent to the room

3b) if you don't want to do that, if it hits 5,000 and not all have been to the room, the time limit goes to 10,000, etc, until all have been to the room, then the next multiple of 5,000 is the dead one. Can you do it now?

3c) another possibility: the king is lazy. He knows that if you have a dead-certain plan, he doesn't want to waste 5000 hours on the experiment. So if a prisoner comes to him with a plan that, if all prisoners go to the room, it will succeed, the king will just let them all go right away. So you just have to come up with a plan assuming all prisoners go to the room

4) is it possible?

some more points:

1) right now you have the option of turning no knobs or only one of the three knobs - what if you had the option to turn two knobs maximum?

2) remember that prisoners can keep track of time in their cells

[Guest]

If we can just assume that all prisoners visit the room then the problem is null – the king asks them to state “when every single prisoner has been in the room.” So if we can assume everyone visits the room, then we’re done.

Lets say there are 7 prisoners… and only 6 visit the room. Obviously we can use the three dials with three settings to count up to 7, or 10, or 27. So at least one of the six prisoners will know that 6 people have visited.

But, they have no way of knowing that there is a seventh:* say they are lined up:

1 2 3 4 [5] 6 7

And prisoner 5 hasn’t visited the room after 5000 hours. The other prisoners have no way of knowing that prisoner 5 exists. Prisoners 4 and 6 don’t know if they were looking at each other in the room at the start, or if they were both looking at prisoner 5.

So, ignoring the option where we can just assume the answer, I think the only way to be certain that everyone has visited, is when 10 prisoners have visited – that is the only situation when you can be certain that there is no extra prisoner who hasn’t visited the room yet.

Looking at it a slightly different way, you can only know if everyone has visited, if you know how many prisoners there are.

There is a possible tactic you could use where you stop writing letters once you’ve visited the room… but that would be using the letters to convey information about how many people there are, so I think would be disallowed by the King.

* unless he was at the end of the line

[unreality]

How about this then... the King announces the number of prisoners to the prisoners, but I, Unreality, won't say the number. You have to figure out a plan (whether basic or number-specific) basing on the fact that the prisoners know how many there are