How many prisoners?
Moderators: jestingrabbit, Moderators General, Prelates
How many prisoners?
You, together with a finite number n1 of other ideal mathematicians, have been arrested on a whim by a generic evil dictator and are about to be locked up in a prison. The prison is circular, with n identical windowless cells arranged in a ring around a central court. There are some problems with the lighting system  the light switch in each cell controls the light in the next cell clockwise around the ring. Even worse, electric power is only provided to the lights for one tenth of a second each night, just after midnight.
The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.
The warden visits you in your cell, and explains that if you are able to communicate despite these precautions he will consider you all worthy of release. At any time, any prisoner who believes he has discovered how many prisoners there are may petition the warden for release. That prisoner will be allowed one guess at the number of prisoners; if they guess correctly, then all the prisoners will be released, but if they guess incorrectly then all the prisoners will be executed.
You have been chosen to devise a strategy by means of which you will be able to discover the number of prisoners. You may compose a single email outlining your strategy, which will be passed to all the prisoners. However, your strategy must be foolproof, as the warden (who has a deep hatred of ideal mathematicians) will also read your email.
Is there a strategy which will guarantee your release? If so, give one. If not, why not?
The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.
The warden visits you in your cell, and explains that if you are able to communicate despite these precautions he will consider you all worthy of release. At any time, any prisoner who believes he has discovered how many prisoners there are may petition the warden for release. That prisoner will be allowed one guess at the number of prisoners; if they guess correctly, then all the prisoners will be released, but if they guess incorrectly then all the prisoners will be executed.
You have been chosen to devise a strategy by means of which you will be able to discover the number of prisoners. You may compose a single email outlining your strategy, which will be passed to all the prisoners. However, your strategy must be foolproof, as the warden (who has a deep hatred of ideal mathematicians) will also read your email.
Is there a strategy which will guarantee your release? If so, give one. If not, why not?
Re: How many prisoners?
Might be possible.
You can distinguish between the case of 1 other prisoner and more than 1 other prisoner by seeing if you can receive responses from the prisoner in the next room with a latency of 1. Thus the warden cannot trick you into thinking that there is 1 other prisoner when there is more. If we find that it is possible to sequentially attempt to prove that there are more than N prisoners for each N, then we can solve the problem successfully.
The strategy you email out will then simply be for each prisoner to set the switch to the same state their light was on the previous night. Everything else is up to you.
You can distinguish between the case of 1 other prisoner and more than 1 other prisoner by seeing if you can receive responses from the prisoner in the next room with a latency of 1. Thus the warden cannot trick you into thinking that there is 1 other prisoner when there is more. If we find that it is possible to sequentially attempt to prove that there are more than N prisoners for each N, then we can solve the problem successfully.
The strategy you email out will then simply be for each prisoner to set the switch to the same state their light was on the previous night. Everything else is up to you.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: How many prisoners?
Assuming the email cannot name specific prisoners, so that they all use the same strategy:
Spoiler:
Last edited by Pelli on Mon Apr 25, 2011 9:19 pm UTC, edited 1 time in total.
Re: How many prisoners?
What does the 1/10th of a second limit mean for the prisoners?
Can they react in this time and turn their switch? Or do they just find out whether the switch in the room next to them is on or off?
Even if they cannot react in this time, can they switch the switch over in this 1/10th of a second?
Do the prisoners have time to change the switch in their room after this before they are moved rooms? Do they have time to move a switch in the new room before midnight?
Do they know when midnight is if nothing happens at all to their light?
Can they react in this time and turn their switch? Or do they just find out whether the switch in the room next to them is on or off?
Even if they cannot react in this time, can they switch the switch over in this 1/10th of a second?
Do the prisoners have time to change the switch in their room after this before they are moved rooms? Do they have time to move a switch in the new room before midnight?
Do they know when midnight is if nothing happens at all to their light?
Re: How many prisoners?
sfwc wrote:The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.
sfwc wrote:all the cells cleaned to prevent prisoners leaving messages
I presume this to mean that the light switches are removed from the cells immediately. Since the warden is worried about the prisoners using them to communicate, and everything that could be used to communicate is cleaned out of the cells, the light switches are removed as well.
Or at the very least, the polarity of the switches are randomized everyday (so up may be on or off in each cell independently) and the positions of the switches are randomized as well. Thus, every time you are put in a new cell, you have no information about whether the light is on or off until midnight happens, and that doesn’t tell you anything about the previous occupant of the room because the wardens played with the switches before you were put there.
So…yeah. No possible way to communicate, because the problems statement specifically mentions that anything that could be used to send messages gets cleaned out.
wee free kings
Re: How many prisoners?
So, each night each prisoner can send one bit of information to one other prisoner, with the recipient determined by a malicious Warden. Not possible. The low bandwidth combined with the total lack of control over who receives each bit is way too much.
It might be possible if the nightly reshuffling of prisoners between cells were removed, but that lack of control over who receives or consumes any given bit of information completely kills any possibility of a solution.
It might be possible if the nightly reshuffling of prisoners between cells were removed, but that lack of control over who receives or consumes any given bit of information completely kills any possibility of a solution.
 t1mm01994
 Posts: 299
 Joined: Mon Feb 15, 2010 7:16 pm UTC
 Location: San Francisco.. Wait up, I'll tell you some tales!
Re: How many prisoners?
Let's take a stab at this and see how far I get.
So seeing how it is possible for 3, I'd say it is possible for more too... Who can expand this?[/spoiler]
I took 1/10th of a second to mean no light signals across more than 1 cell, so you can program your switch at the start of the day, and the receiver knows that at that split second. They do have clocks, and normal lights, but cannot see eachother, and there is a flashlight going on if the switch is pressed.
Correct me if this interpretation is incorrect.
Spoiler:
So seeing how it is possible for 3, I'd say it is possible for more too... Who can expand this?[/spoiler]
I took 1/10th of a second to mean no light signals across more than 1 cell, so you can program your switch at the start of the day, and the receiver knows that at that split second. They do have clocks, and normal lights, but cannot see eachother, and there is a flashlight going on if the switch is pressed.
Correct me if this interpretation is incorrect.
Re: How many prisoners?
The prisoners can find an upper limit on their population:
A potential avenue from this:
Spoiler:
A potential avenue from this:
Spoiler:
Re: How many prisoners?
So the prisoners all find an upper limit for their population, lets say they know there are at least 10,000 of them. Now every 10,000 nights the first prisoner (you?) sends out 1 bit of information, this is propagated throughout by all the prisoners, if they see a light on they switch all the following nights, if not they just leave the switch off. 9,999 nights later everyone will have this bit of information, due to the layout of the rooms. Repeating this the first prisoner can send arbitrary messages to the group, bitwise.
Not so, the warden can control the path of the message through the prisoners. They could loop it back to you in any amount of time they choose including as many or few of the prisoners as they chose. I believe as stated the problem is equivalent to the warden rewiring the switches however they wish so that all prisoners remain in the same single loop, and never moving the prisoners from room to room.
I'm fairly sure any solution will involve all other prisoners acting as bit propagators, and you sending out sequences to rule out populations less than N for each N. Note that this category of solutions provides maximum concealment of information from the warden  the warden cannot predict what sequences you will send out, or how you will interpret what you receive. As such, we may be able to show that the warden can do no better than rearranging the prisoners at random.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: How many prisoners?
WarDaft wrote:Not so, the warden can control the path of the message through the prisoners. They could loop it back to you in any amount of time they choose including as many or few of the prisoners as they chose. I believe as stated the problem is equivalent to the warden rewiring the switches however they wish so that all prisoners remain in the same single loop, and never moving the prisoners from room to room.
Ah but the message will propagate to at least one new prisoner at every stage, if it didn't then the current group of prisoners with the message would all have to be in a loop for one night. We know that the prisoners are actually arranged in one large loop so a smaller loop is not possible. If they message propagates to at least one new prisoner every night then it must reach all of them by the end of our 10,000 nights.
edit: Are there as many mathematicians as there are cells?
Re: How many prisoners?
I think you've mostly latched on to the problem as I intended it, but I'll add some clarifications to be on the safe side.
They can't react  they just find out the state of the switch next door.gcoope wrote:What does the 1/10th of a second limit mean for the prisoners?
Can they react in this time and turn their switch? Or do they just find out whether the switch in the room next to them is on or off?
Again, no.Even if they cannot react in this time, can they switch the switch over in this 1/10th of a second?
Yes, but all the switches will be turned off by the cleaners if the cells are cleaned.Do the prisoners have time to change the switch in their room after this before they are moved rooms?
Yes, they always have time to do this.Do they have time to move a switch in the new room before midnight?
Yes, they can tell. That is, they are able to judge this well enough that they know each day how many nights have passed and what message was intended for them on each night.Do they know when midnight is if nothing happens at all to their light?
No, none of this happens. The cleaners want to stop the prisoners leaving behind messages in the cells, so that the only way they can communicate is via the lights. The only way the cleaners interact with the light switches is to turn them off.Qaanol wrote:I presume this to mean that the light switches are removed from the cells immediately. Since the warden is worried about the prisoners using them to communicate, and everything that could be used to communicate is cleaned out of the cells, the light switches are removed as well.
Or at the very least, the polarity of the switches are randomized everyday (so up may be on or off in each cell independently) and the positions of the switches are randomized as well.
I'm happy with that interpretation.t1mm01994 wrote:I took 1/10th of a second to mean no light signals across more than 1 cell, so you can program your switch at the start of the day, and the receiver knows that at that split second. They do have clocks, and normal lights, but cannot see eachother, and there is a flashlight going on if the switch is pressed.
Correct me if this interpretation is incorrect.
Yes.gcoope wrote:Are there as many mathematicians as there are cells?

 Posts: 1
 Joined: Tue Apr 26, 2011 11:18 am UTC
Re: How many prisoners?
This could be a solution.
althou this requires the prisoners to have some basic physics knowledge (and some more):
althou this requires the prisoners to have some basic physics knowledge (and some more):
Spoiler:
 t1mm01994
 Posts: 299
 Joined: Mon Feb 15, 2010 7:16 pm UTC
 Location: San Francisco.. Wait up, I'll tell you some tales!
Re: How many prisoners?
Is this a problem to which the outcome is known to you or something that needs to be explored? The two require quite different approaches.
Carrying on with my spoiler  by the way, anyone mind to check it?
Carrying on with my spoiler  by the way, anyone mind to check it?
Spoiler:
Re: How many prisoners?
gcoope wrote:Ah but the message will propagate to at least one new prisoner at every stage, if it didn't then the current group of prisoners with the message would all have to be in a loop for one night. We know that the prisoners are actually arranged in one large loop so a smaller loop is not possible. If they message propagates to at least one new prisoner every night then it must reach all of them by the end of our 10,000 nights.
edit: Are there as many mathematicians as there are cells?
This is not at all the case. Suppose the first night, the sequence goes YOU, A, B, such that B will see A's message, and A will see yours.
So we have:
YOU, A, B; A gets the bit
YOU, A, B; B gets the bit
_,YOU,B,A; A gets the bit
_,_,YOU,A,B; B gets the bit
...
Where _ represents any person in the room. Now, as the rooms are all indistinguishable, this is equivalent too:
YOU, A, B; A gets the bit
YOU, A, B; B gets the bit
YOU, B, A; A gets the bit
YOU, A, B; B gets the bit
So the warden can choose up to around n/2 bits of your message that will simply never get back to you.
Likewise, the warden could do this:
YOU, A, B; A gets the bit
A, YOU, B; You get the bit back.
Solutions, if possible, will almost certainly take advantage of the fact that when the warden moves a bit back, they move (an) other bit(s) forward.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: How many prisoners?
t1mm01994 wrote:Is this a problem to which the outcome is known to you or something that needs to be explored?
The answer is known to me.
Re: How many prisoners?
WarDaft wrote:This is not at all the case. Suppose the first night, the sequence goes YOU, A, B, such that B will see A's message, and A will see yours.
So we have:
YOU, A, B; A gets the bit
YOU, A, B; B gets the bit
_,YOU,B,A; A gets the bit
_,_,YOU,A,B; B gets the bit
...
In the answer I gave the prisoners keep turning their light on, they don't just "pass it on" once. Thus each night the number of prisoners with the on message (if there is one) increases until everyone has it.
Haven't got any further with this problem, we can try the same tactic as the other problem where the warden creates large groups behaving the same as each other, in fact it is easy to pair up all but 2 or 3 of the prisoners and have every prisoner with a double who is receiving and giving the same information, can't quite stop any information from travelling though.
Re: How many prisoners?
Ah, yes, that will spread throughout, sorry.
AHA! Of course!
AHA! Of course!
Spoiler:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: How many prisoners?
A question that might be important (or not, I feel really schizophrenic, some parts of me want to demonstate that cannot work, and some other still believe in information transmission) : Are prisonners aware when they are moved ? If so, they can act differently depending on whether or not (or the number of times) they have been moved.
If not, the problem is indeed equivalent to the warden rearranging the wires each night in one single loop (which would make the story more realistic than being moved without seeing anything of the prison)
If not, the problem is indeed equivalent to the warden rearranging the wires each night in one single loop (which would make the story more realistic than being moved without seeing anything of the prison)

 Posts: 44
 Joined: Sun Feb 08, 2009 12:20 pm UTC
Re: How many prisoners?
Possible working method:
Spoiler:
Re: How many prisoners?
Ermes Marana wrote:Possible working method:Spoiler:
Spoiler:
Re: How many prisoners?
Okay, solved.
Spoiler:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: How many prisoners?
WarDaft wrote:Spoiler:
I don't think that detail is right.
Spoiler:
 skeptical scientist
 closedminded spiritualist
 Posts: 6141
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
douglasm wrote:WarDaft wrote:Spoiler:
I don't think that detail is right.Spoiler:
Spoiler:
Last edited by skeptical scientist on Fri Apr 29, 2011 2:07 pm UTC, edited 1 time in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: How many prisoners?
magemax wrote:Are prisonners aware when they are moved ? If so, they can act differently depending on whether or not (or the number of times) they have been moved.
The prisoners can tell when there is a general movement of prisoners and cleaning of cells. But they can't tell whether the cell they are put in after the cleaning is the same as the one they were taken out of (they can't tell whether they were moved).
If not, the problem is indeed equivalent to the warden rearranging the wires each night in one single loop (which would make the story more realistic than being moved without seeing anything of the prison)
Yes, it is equivalent to that problem.
 skeptical scientist
 closedminded spiritualist
 Posts: 6141
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
WarDaft wrote:Okay, solved.Spoiler:
Not solved. You run into problems in the quoted section.
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: How many prisoners?
Hmm, that's right.
Spoiler:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 skeptical scientist
 closedminded spiritualist
 Posts: 6141
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
I've come up with a couple of strategies with interesting properties, one for the prisoners and one for the warden.
Strategy for the prisoners:
Strategy for the warden:
Strategy for the prisoners:
Spoiler:
Strategy for the warden:
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: How many prisoners?
It seems that whatever strategy is given, the warden is going to try to foil it using the best tool at his disposal, which is rearranging the prisoners.
Would it be possible to "play" the warden? In other words, could one develop a public strategy that appears to be an attempt at communication, but is actually a private strategy to get the warden to rearrange prisoners in a predictable way that would reveal to the planner the actual number of prisoners?
Would it be possible to "play" the warden? In other words, could one develop a public strategy that appears to be an attempt at communication, but is actually a private strategy to get the warden to rearrange prisoners in a predictable way that would reveal to the planner the actual number of prisoners?
So, you sacked the cocky khaki Kicky Sack sock plucker?
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.

 Posts: 44
 Joined: Sun Feb 08, 2009 12:20 pm UTC
Re: How many prisoners?
Nitrodon wrote:Ermes Marana wrote:Possible working method:Spoiler:Spoiler:
Possible fix for my method:
Spoiler:
Re: How many prisoners?
skeptical scientist wrote:This is a nondeterministic strategy the prisoners can use to free themselves with probability 1e, for arbitrary e>0.
Yes, that works. However, just as for the other question I asked, I'd like to know if there is a strategy which guarantees release  I take that as excluding even nondeterministic strategies which work almost surely but not surely. So I'll be explicit about it here: my question is whether there is a deterministic strategy.
JBJ wrote:Would it be possible to "play" the warden?
No. The warden knows your strategy.
Re: How many prisoners?
Here is a strategy my friend came up with, which solves the problem with probability 1 (so only "almost surely") provided each prisoner has a random number generator:
Spoiler:
Re: How many prisoners?
That's a very pleasant strategy, and it completely solves the nondeterministic version of the problem.
Re: How many prisoners?
Yes, it still works! I was actually jumping through hoops I didn't need to, and ended up pointing myself in the wrong direction.
Spoiler:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 skeptical scientist
 closedminded spiritualist
 Posts: 6141
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
Nice job on the probability 1 solution. I'm beginning to suspect there is no deterministic solution, but I don't have a proof.
No, you still don't have a complete solution.
This is false.
WarDaft wrote:Yes, it still works! I was actually jumping through hoops I didn't need to, and ended up pointing myself in the wrong direction.
No, you still don't have a complete solution.
Spoiler:
This is false.
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: How many prisoners?
Ah, but...
Spoiler:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 skeptical scientist
 closedminded spiritualist
 Posts: 6141
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
WarDaft wrote:Ah, but...Spoiler:
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: How many prisoners?
Ah, found it. Sorry, too many spoiler tags around.
Spoiler:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

 Posts: 54
 Joined: Wed Oct 27, 2010 9:08 pm UTC
Re: How many prisoners?
I'm not sure if anybody has taken this into account, but if there's n1 prisoners and n cells, doesn't that mean there is an empty cell somewhere? What if a critical message hits the empty cell in any of the strategies above?
 skeptical scientist
 closedminded spiritualist
 Posts: 6141
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
Scuttlemutt wrote:I'm not sure if anybody has taken this into account, but if there's n1 prisoners and n cells, doesn't that mean there is an empty cell somewhere? What if a critical message hits the empty cell in any of the strategies above?
There are n prisoners: you and n1 other prisoners.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 skeptical scientist
 closedminded spiritualist
 Posts: 6141
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
Okay, I have a full solution. (I'm pretty sure. It's sufficiently complex that I may have made a mistake. I'd be interested if anyone has a simpler solution, or a simpler proof of the necessary lemma. I'm also hoping sfwc will share his solution, now that we've found a solution.)
Proof of the lemma needed above:
Yes, I doubleposted. Hopefully finding a solution is a good enough excuse.
Spoiler:
Proof of the lemma needed above:
Spoiler:
Yes, I doubleposted. Hopefully finding a solution is a good enough excuse.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Who is online
Users browsing this forum: Google Feedfetcher and 7 guests