Topic RSS | Reply to topic
Author Post

Drokles


Member

Posted Tue May 15th, 2012 11:59pm Post subject: Three Prisoners

We a need a good solid riddle in here.

Three prisoners have been newly ushered into prison. The warden tells
them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst each other. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch.
The prisoner will be able to observe the current state of the light bulb. If he wishes, he can toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed.
The warden leaves, and the prisoners huddle together to discuss their fate. Can they agree on a protocol that will guarantee their freedom?

Note: The original riddle is with 100 prisoners. Both riddles have solutions that make pretty good sense, but with the 100 prisoner one, it is difficult to find a protocol that is efficient enough to give an expected jail time of less than a hundred years.


Back to top

Stefi


Member

Posted Wed May 16th, 2012 8:07pm Post subject: Three Prisoners

Hm I would probably do something like let every prisoner bind a small thread on the toggle switch when they are in the room, and when a prisoner sees two threads on there he knows that both have been there

But I don't think that's really the answer... more of an idea

We are talking of the idea of beauty, and the beauty of ideas.

@Giggi_1

Back to top

Drokles


Member

Posted Fri Jun 1st, 2012 4:16pm Post subject: Three Prisoners

Sadly, it is not that easy ;). But nice idea, I wouldn't have thought of it. Some of my friends came up with the idea that you could smash the light bulb at some point, giving you an extra degree of freedom.
Of course, you could do that, but there's no reason to. It is a riddle that encourages logical thinking - there are no tricks.


Back to top

Desideria


Member

Posted Tue Jun 5th, 2012 4:25pm Post subject: Three Prisoners

It's a fascinating riddle but I'm really bad at logical thinking. Perhaps they could agree that Prisoner 1 always switches the light on, Prisoner 2 switches it off and that Prisoner 3 never touches the toggle switch. However, I have no idea what would happen if, say, Prisoner 2 would be placed in the interrogation room on two consecutive days because that would mean that he wouldn't be allowed to touch the toggle switch, an action which is only allowed to Prisoner 3. Hm.

However, what I am very sure of is that they must try to communicate via the toggle switch. There doesn't seem to be a way around that.

A hint, perhaps?

@AvenidaMK on Twitter

Back to top

Popeye


Member

Posted Tue Jun 5th, 2012 4:45pm Post subject: Three Prisoners

Assuming the room in which the light bulb is has just four walls, they could agree to each move the toggle in the direction of a different wall. Once one of them had seen it in the other two positions to their own then they would know everyong had visited the room.

Is this in any way close or am I talking gobbledegook!?!


Everyday should be Fryday!
Soupy Twist!

Back to top

Drokles


Member

Posted Tue Jun 5th, 2012 7:36pm Post subject: Three Prisoners

That's not quite it, although I can see the appeal of having four independent indicators of who has been there (the four walls) instead of just one (the light bulb). It is possible though, communicating only through the light bulb :).

Desideria said:
It's a fascinating riddle but I'm really bad at logical thinking. Perhaps they could agree that Prisoner 1 always switches the light on, Prisoner 2 switches it off and that Prisoner 3 never touches the toggle switch. However, I have no idea what would happen if, say, Prisoner 2 would be placed in the interrogation room on two consecutive days because that would mean that he wouldn't be allowed to touch the toggle switch, an action which is only allowed to Prisoner 3. Hm.

However, what I am very sure of is that they must try to communicate via the toggle switch. There doesn't seem to be a way around that.

A hint, perhaps?

You are on the right track :D. Here's a hint:

[spoiler]
Think about how you plan to assign the roles of prisoner #1, #2 and #3. Do they decide who gets to be who from the beginning? Or are roles assigned dynamically?
Remember that when a prisoner enters the room, he knows


    What the current state of the light bulb is
    Whether he himself has been there already or not (and how many times if any)
    How many days have passed

The actions he takes inside the room should depend on this information, and possibly his role as either prisoner #1, #2 or #3.
I hope I haven't just made it confusing now :D.
[/spoiler]

Edit: Oh, spoiler tags don't work? Oh well.


Back to top

Stefi


Member

Posted Tue Jun 5th, 2012 7:38pm Post subject: Three Prisoners

Hmm ok with logical thinking I'd say they should demand a lawyer and try to sue the prison for this frankly very weird way of determining guilt or innocence...?

Maybe it's a trick question and that's the solution. It's worth a try.

We are talking of the idea of beauty, and the beauty of ideas.

@Giggi_1

Back to top

Drokles


Member

Posted Tue Jun 5th, 2012 8:02pm Post subject: Three Prisoners

In a fair and just world that would certainly work. Unfortunately the prisoners do not have lawyers to represent them, and the warden values game theory over justice.


Back to top

Desideria


Member

Posted Wed Jun 6th, 2012 4:22pm Post subject: Three Prisoners

I'm on the right track? Never thought that I could actually be on the right track with something that involves logical thinking.

Thank you for the hints! Quite helpful, although I don't think I will find the correct solution. However, this is what I can come up with at this point:

I think that the position of the toggle switch can be used to indicate if someone has been in the interrogation room more than once. Therefore, they will need a counting system of some sorts and they will have to take notice of the status of the light bulb (on/off).

They can perhaps decide that the first person who goes into the room on the first day switches the light on and the light has to stay switched on for as long as the person who came into the interrogation room on the first day goes in there for a second time. Then this person will have to switch the light off as a signal to the others. And then the counting starts anew with another prisoner ... Or not.

Now I'm lost.

@AvenidaMK on Twitter

Back to top

Drokles


Member

Posted Wed Jun 6th, 2012 4:36pm Post subject: Three Prisoners

You've actually almost solved it now. So to sum up your protocol thus far:

You've got the first prisoner coming in there to turn on the light, and the light will stay on as long as it is this same guy who is called in. When a new prisoner then is called in, this new prisoner will see the light is on and think 'one of the others has been here before me. I'm the second prisoner to enter the room.' The new prisoner then turns off the light.
This can also be formulated as a set of instructions to the prisoners:
If you enter the room and it is the first day, turn on the light, and if you reenter the room on subsequent days, do nothing.

If you enter the room for the first time and it is not the first day and the light bulb is on, turn off the light.

So. You now have three distinct prisoners at this point. One who came in there on the first day and turned on the light. One who came in there as the second one to enter the room for the first time who turned off the light. One who hasn't been in the room yet.


Back to top

Desideria


Member

Posted Wed Jun 6th, 2012 9:02pm Post subject: Three Prisoners

Ah! So the third one who enters the room for the first time will see that the light is switched off. He therefore knows that he can't be the second one to enter the room because if that were the case the light would still be switched on. However, the light is switched off when he enters the room, therefore he knows that the second prisoner has also already been there. This means that he can now announce that all three prisoners, himself included, have been in the interrogation room.

This protocol, however, does only work, when those who have been in the room several times do nothing and just leave the light switched off.

@AvenidaMK on Twitter

Back to top

Drokles


Member

Posted Wed Jun 6th, 2012 9:15pm Post subject: Three Prisoners

A winner is you!


Back to top

Desideria


Member

Posted Thu Jun 7th, 2012 10:53am Post subject: Three Prisoners

But only with your help! I had been thinking in the wrong direction again but your summary got me back on track.

Thank you for the riddle, I enjoyed trying to solve it.

@AvenidaMK on Twitter

Back to top

Stefi


Member

Posted Thu Jun 7th, 2012 6:12pm Post subject: Three Prisoners

Great riddle!
Although, how does the third prisoner know that he is not, in fact, the first to be called in?
And how would it work with 100 prisoners?

We are talking of the idea of beauty, and the beauty of ideas.

@Giggi_1

Back to top

Drokles


Member

Posted Fri Jun 8th, 2012 8:30pm Post subject: Three Prisoners

He knows he is not the first prisoner because he knows that it is no longer the first day of their sentence when he enters the room. Therefore the first prisoner must have already been there :).
With a hundred prisoners there are a few different strategies. An article was written about the different solutions and the expected jail times :D. It can be found here:
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf

Thanks for playing guys


Back to top