How many prisoners?
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
My idea of an inductive solution would be to find a way to distinguish between there being n prisoners in the cell and there being more than n prisoners for all n. Eventually you would find the exact number of prisoners.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 25
 Joined: Tue Apr 17, 2012 4:09 am UTC
Re: How many prisoners?
sfwc wrote:lordofthesnails wrote:Impressively complicated solution, but in practice:Spoiler:
Yes, that's right. I've been thinking for ages about whether there might be a quicker solution but I can't think of anything. Any ideas?
Idea 1: rephrase the question to cut down the cycle length. For example, the switch might control the color of the light in the adjacent room between red and blue, and you control when the pulse of electricity happens. Each prisoner knows when a "day" happens because the room does flash, and the 1 bit is conveyed by color instead of on/off. However, you can't send another pulse until after the warden gives you the go ahead, having rearranged the other prisoners (note that you can be held stationary without altering the substance of the problem).
NonQuestion Changing Idea 2:
Spoiler:
One nitpick with the solution itself, even if we assume robots with infinite lifespans as prisoners:
Spoiler:
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: How many prisoners?
One nitpick with the solution itself, even if we assume robots with infinite lifespans as prisoners:Spoiler:
Well, there's always bruteforce search. If you have a computable relation on a computably enumerable set, you can always computably enumerate the set of elements which satisfy the relation.
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

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
Here is my idea: I am P_{1}
Night 1: P_{1} sends a signal. If P_{1} receives a signal, then there is only one prisoner. If not, then whoever receives a signal is P_{2}.
Night 2: P_{1} and P_{2} both send a signal. If there are only two people, then P_{1} and P_{2} both receive a signal. However, if there are more than two people, then 1 or 2 people (that are not P_{1} and P_{2}) will receive a signal, they are P_{3}.
Night 3: If P_{1} or P_{2} receives a signal, then they send a signal. If there are only two people, then P_{1} and P_{2} both receive a signal on this night. If not, then at most one of them (P_{1} or P_{2}) received a signal on the second night, and that person (if he exists) will be the only one who sends a signal on this night. Obviously, since there is a third night, there is more than one person, so the person (if any) who sends a signal will not get it back. Therefore if there are more than 2 people, everybody will know on the third night. Now, if a signal was sent on the third night, then both the sender and the receiver know that there is only one P_{3}. If a signal was not sent on the third night, then there are two P_{3}'s, but nobody knows this.
Night 4: P_{1}, P_{2}, and the P_{3}('s) all send a signal
Night 57: P_{1}, P_{2}, and the P_{3}('s) send a signal if they received the signal all the nights since night 4. If all the people are classified as P_{1}, P_{2} or P_{3}, then they will all receive a signal on night 7. If there are more people, then everyone will know on night 7 because they did not receive a signal on one of the last four nights. Now this splits into two different scenarios.
Scenario 1: P_{1}, P_{2} and the P_{3}('s) are the only people in the prison. Now if there is only one P_{3}, then the two people mentioned in night 3 that know that there is only 1 P_{3}, go and tell the warden on day 8 that there are only three people and they are released by the end of the day. If not, then on day P_{1} goes and tells the warden that there are four people in the prison on day 9, and they are all released by the end of the day. Yes, I am cheating slightly here, because extra information is transmitted by whether the two hypothetical people exist and go to the warden, or not, but nobody said that wasn't allowed.
Scenario 2: I am still thinking on this one, but at least everybody knows by night 8 that there are at least 4 people, which is one better than I did on the previous answer.
Night 1: P_{1} sends a signal. If P_{1} receives a signal, then there is only one prisoner. If not, then whoever receives a signal is P_{2}.
Night 2: P_{1} and P_{2} both send a signal. If there are only two people, then P_{1} and P_{2} both receive a signal. However, if there are more than two people, then 1 or 2 people (that are not P_{1} and P_{2}) will receive a signal, they are P_{3}.
Night 3: If P_{1} or P_{2} receives a signal, then they send a signal. If there are only two people, then P_{1} and P_{2} both receive a signal on this night. If not, then at most one of them (P_{1} or P_{2}) received a signal on the second night, and that person (if he exists) will be the only one who sends a signal on this night. Obviously, since there is a third night, there is more than one person, so the person (if any) who sends a signal will not get it back. Therefore if there are more than 2 people, everybody will know on the third night. Now, if a signal was sent on the third night, then both the sender and the receiver know that there is only one P_{3}. If a signal was not sent on the third night, then there are two P_{3}'s, but nobody knows this.
Night 4: P_{1}, P_{2}, and the P_{3}('s) all send a signal
Night 57: P_{1}, P_{2}, and the P_{3}('s) send a signal if they received the signal all the nights since night 4. If all the people are classified as P_{1}, P_{2} or P_{3}, then they will all receive a signal on night 7. If there are more people, then everyone will know on night 7 because they did not receive a signal on one of the last four nights. Now this splits into two different scenarios.
Scenario 1: P_{1}, P_{2} and the P_{3}('s) are the only people in the prison. Now if there is only one P_{3}, then the two people mentioned in night 3 that know that there is only 1 P_{3}, go and tell the warden on day 8 that there are only three people and they are released by the end of the day. If not, then on day P_{1} goes and tells the warden that there are four people in the prison on day 9, and they are all released by the end of the day. Yes, I am cheating slightly here, because extra information is transmitted by whether the two hypothetical people exist and go to the warden, or not, but nobody said that wasn't allowed.
Scenario 2: I am still thinking on this one, but at least everybody knows by night 8 that there are at least 4 people, which is one better than I did on the previous answer.
Last edited by tomtom2357 on Tue May 01, 2012 1:31 am UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 6
 Joined: Fri Mar 13, 2009 5:20 pm UTC
Re: How many prisoners?
pimverkerk wrote:This could be a solution.
althou this requires the prisoners to have some basic physics knowledge (and some more):Spoiler:
After n nights you might not be in the same cell, so no...

 Posts: 6
 Joined: Fri Mar 13, 2009 5:20 pm UTC
Re: How many prisoners?
tomtom2357 wrote:Here is my idea: I am P_{1}
Night 1: P_{1} sends a signal. If P_{1} receives a signal, then there is only one prisoner. If not, then whoever receives a signal is P_{2}.
Night 2: P_{1} and P_{2} both send a signal. If there are only two people, then P_{1} and P_{2} both receive a signal. However, if there are more than two people, then 1 or 2 people (that are not P_{1} and P_{2}) will receive a signal, they are P_{3}.
Night 3: If P_{1} or P_{2} receives a signal, then they send a signal. If there are only two people, then P_{1} and P_{2} both receive a signal on this night. If not, then at most one of them (P_{1} or P_{2}) received a signal on the second night, and that person (if he exists) will be the only one who sends a signal on this night. Obviously, since there is a third night, there is more than one person, so the person (if any) who sends a signal will not get it back. Therefore if there are more than 2 people, everybody will know on the third night. Now, if a signal was sent on the third night, then both the sender and the receiver know that there is only one P_{3}. If a signal was not sent on the third night, then there are two P_{3}'s, but nobody knows this.
Night 4: P_{1}, P_{2}, and the P_{3}('s) all send a signal
Night 57: P_{1}, P_{2}, and the P_{3}('s) send a signal if they received the signal all the nights since night 4. If all the people are classified as P_{1}, P_{2} or P_{3}, then they will all receive a signal on night 7. If there are more people, then everyone will know on night 7 because they did not receive a signal on one of the last four nights. Now this splits into two different scenarios.
Scenario 1: P_{1}, P_{2} and the P_{3}('s) are the only people in the prison. Now if there is only one P_{3}, then the two people mentioned in night 3 that know that there is only 1 P_{3}, go and tell the warden on day 8 that there are only three people and they are released by the end of the day. If not, then on day P_{1} goes and tells the warden that there are four people in the prison on day 9, and they are all released by the end of the day. Yes, I am cheating slightly here, because extra information is transmitted by whether the two hypothetical people exist and go to the warden, or not, but nobody said that wasn't allowed.
Scenario 2: I am still thinking on this one, but at least everybody knows by night 8 that there are at least 4 people, which is one better than I did on the previous answer.
One problem with this view. How do you know who's P1 and who's P2 etc.? You can't assign people in order of cell since you switch. There's no way to decide when it's your turn to turn on the light.
The best you can achieve with such a tactic is that one person starts, and you flip your switch if you've seen the light last night, at most doubling the number of turned on switches each night giving some power of 2 as an upper limit when all lights are on.
I think the key is in not finding out how many people there are, but how many cells there are. The problem with that is that I assume you wouldn't be able to tell whether you've been in the cell you're in now already or not.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
The thing I think you don't understand is that you don't have to know who P_{1} and P_{2} are, and it has nothing to do with where they are in the cells and in relation to each other, except for the night where they are assigned as P_{1}, P_{2}, etc. They are not assigned based on what cell they are in, but based on what signals they received on previous nights. P_{1} may be in the cell before P_{2} on one night, and on the next they could be far apart. The person is classified, not the room.
Edit: About your last comment: How is the number of people different than the number of rooms? I think that they are the same. It is impossible to find out how many rooms there are without first finding out how many people there are. You don't need to know whether you've been in a room you've previously been in, all you need to know is how to follow the formula to find the number of people, and eventually how many people there are.
Edit: About your last comment: How is the number of people different than the number of rooms? I think that they are the same. It is impossible to find out how many rooms there are without first finding out how many people there are. You don't need to know whether you've been in a room you've previously been in, all you need to know is how to follow the formula to find the number of people, and eventually how many people there are.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 12
 Joined: Thu Jun 24, 2010 6:00 pm UTC
Re: How many prisoners?
The problem with all solutions depending upon transmission of information on bit form between prisoners is that the warden can simply prevent it. If we assume the transfer of prisoners is random, then that's one thing. Godel works. But what if it is nonrandom? What if, for instance, the pattern simply shifts prisoners one cell over, so that they always receive their own messages? No solution presents itself.
Re: How many prisoners?
It isn't possible for a prisoner to receive their own message. The reason is that the prisoners are not moved between the sending and the receiving of the messages. Instead, the rearrangement of the prisoners happens after one day's messages have all been received but before the next day's messages get sent.

 Posts: 25
 Joined: Tue Apr 17, 2012 4:09 am UTC
Re: How many prisoners?
sfwc wrote:It isn't possible for a prisoner to receive their own message. The reason is that the prisoners are not moved between the sending and the receiving of the messages. Instead, the rearrangement of the prisoners happens after one day's messages have all been received but before the next day's messages get sent.
I think he was addressing the "variant" someone tossed out that what if there's a one day lag between when you send and when the next cell receives. If the switching guarantees that prisoners won't receive their own signal, the problem is still solvable. If not, there's no way to guarantee any information is ever transmitted between the prisoners, so the problem cannot be solved.
Re: How many prisoners?
In that variant, there is only one switch with a lag. Because of that restriction, it isn't possible for all prisoners to get given the message they sent the previous day  only one. In fact, the modified problem is still soluble, as I showed earlier in the thread.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
Okay, I have done some thinking, and I have come up with an idea for what to do for scenario 2. To clarify, to send a signal on a night means simply to turn your light switch on that night, and to receive a signal means to see the light come on in your room that night. As always, if you spot an error, or I have missed something, or even if you think I am just spouting nonsense, let me know.
Scenario 2:
Night 8: If there is only one P_{3}, then two people know about it, if there are two P_{3}'s, then there are at least 5 people. Therefore, the two (possibly nonexistant) people mentioned above send a signal.
Night 9: The two people that sent a signal last night, send a signal again, and anybody that received a signal last night sends a signal also. This ensures that the only way that there could only be four people is if everyone received a signal on one of the last two nights, and/or was one of the two people. If anybody didn't receive a signal it was because either a) there is 2 P_{3}'s, and therefore the two people don't exist or b) There is only 1 P_{3}, therefore the two people do exist, but the signal didn't get to them because there was too many people. Both of these imply that there are at least 5 people, therefore whoever did not receive a signal knows that there are at least 5 people. Unfortunately, it is possible that everyone got a signal and there are more than 4 people (up to 8 people), if the warden lets the signal travel faster.
Night 10: All the people that know that there is only one P_{3} (note: this may be nobody, as it is still possible that there are 2 P_{3}'s), send a signal.
Nights 1117: All the people that sent a signal on night 10, and received a signal all nights from night 10 on, send a signal. This ensures that either a) everybody sent a signal on night 10 (and received a signal on night 17), which implies that there is a minimum of 4 people and a maximum of 8 people, and that there is only one P_{3} this is scenario 3 or b) everybody knows that not everybody sent a signal on night 10 and that there are at least 5 people, this is scenario 4.
Scenario 3: In this scenario, we have now classified P_{1}, P_{2}, P_{3}, and we know they are unique.
Night 18: P_{1}, P_{2}, P_{3} all send a signal.
Night 19: P_{4} is now classified as the person(s) that receive a signal from Night 18 that are not P_{1}, P_{2} or P_{3}. Now P_{1}, P_{2}, P_{3} and the P_{4}('s) all send a signal.
Nights 2024: All the people that sent a signal on night 19, and received a signal every night since then, send a signal. This ensures that either a) the only people in the prison are P_{1}, P_{2}, P_{3} or a P_{4} and everyone knows it, therefore there are at most 6 people, this is scenario 5, or b) there is at least one other, and everybody knows it, therefore there are at least 5 people, this is scenario 6.
Scenario 2:
Night 8: If there is only one P_{3}, then two people know about it, if there are two P_{3}'s, then there are at least 5 people. Therefore, the two (possibly nonexistant) people mentioned above send a signal.
Night 9: The two people that sent a signal last night, send a signal again, and anybody that received a signal last night sends a signal also. This ensures that the only way that there could only be four people is if everyone received a signal on one of the last two nights, and/or was one of the two people. If anybody didn't receive a signal it was because either a) there is 2 P_{3}'s, and therefore the two people don't exist or b) There is only 1 P_{3}, therefore the two people do exist, but the signal didn't get to them because there was too many people. Both of these imply that there are at least 5 people, therefore whoever did not receive a signal knows that there are at least 5 people. Unfortunately, it is possible that everyone got a signal and there are more than 4 people (up to 8 people), if the warden lets the signal travel faster.
Night 10: All the people that know that there is only one P_{3} (note: this may be nobody, as it is still possible that there are 2 P_{3}'s), send a signal.
Nights 1117: All the people that sent a signal on night 10, and received a signal all nights from night 10 on, send a signal. This ensures that either a) everybody sent a signal on night 10 (and received a signal on night 17), which implies that there is a minimum of 4 people and a maximum of 8 people, and that there is only one P_{3} this is scenario 3 or b) everybody knows that not everybody sent a signal on night 10 and that there are at least 5 people, this is scenario 4.
Scenario 3: In this scenario, we have now classified P_{1}, P_{2}, P_{3}, and we know they are unique.
Night 18: P_{1}, P_{2}, P_{3} all send a signal.
Night 19: P_{4} is now classified as the person(s) that receive a signal from Night 18 that are not P_{1}, P_{2} or P_{3}. Now P_{1}, P_{2}, P_{3} and the P_{4}('s) all send a signal.
Nights 2024: All the people that sent a signal on night 19, and received a signal every night since then, send a signal. This ensures that either a) the only people in the prison are P_{1}, P_{2}, P_{3} or a P_{4} and everyone knows it, therefore there are at most 6 people, this is scenario 5, or b) there is at least one other, and everybody knows it, therefore there are at least 5 people, this is scenario 6.
Last edited by tomtom2357 on Fri Apr 27, 2012 3:10 pm UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 25
 Joined: Tue Apr 17, 2012 4:09 am UTC
Re: How many prisoners?
tomtom2357 wrote:Nights 2024: All the people that sent a signal on night 19, and received a signal every night since then, send a signal. This ensures that either a) the only people in the prison are P_{1}, P_{2}, P_{3} or a P_{4} and everyone knows it, therefore there are at most 6 people, this is scenario 5, or b) there is at least one other, and everybody knows it, therefore there are at least 5 people, this is scenario 6.
You need one more night. Consider the case of 3 P_{4}s. Call the six people now labeled 16, and assume there are at least 7 people. Suppose the warden arranges them such that:
X > 1 > 2 > 3 > 4 > 5 > 6 > X' and leaves them like this for nights 2024.
On night 20, 1 doesn't see a signal. Night 21, 2 doesn't see a signal. Night 22, 3 doesn't get a signal. Night 23, 4 doesn't get one. Night 24, 5 doesn't get one. So 15 know they're in scenario 6, but 6 now believes they're in scenario 5.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
BlueSoxSWJ wrote:tomtom2357 wrote:Nights 2024: All the people that sent a signal on night 19, and received a signal every night since then, send a signal. This ensures that either a) the only people in the prison are P_{1}, P_{2}, P_{3} or a P_{4} and everyone knows it, therefore there are at most 6 people, this is scenario 5, or b) there is at least one other, and everybody knows it, therefore there are at least 5 people, this is scenario 6.
You need one more night. Consider the case of 3 P_{4}s. Call the six people now labeled 16, and assume there are at least 7 people. Suppose the warden arranges them such that:
X > 1 > 2 > 3 > 4 > 5 > 6 > X' and leaves them like this for nights 2024.
On night 20, 1 doesn't see a signal. Night 21, 2 doesn't see a signal. Night 22, 3 doesn't get a signal. Night 23, 4 doesn't get one. Night 24, 5 doesn't get one. So 15 know they're in scenario 6, but 6 now believes they're in scenario 5.
I think the way I worded that part confused you, here is what happens in that case: The warden leaves the prisoners in that configuration for nights 1924
X > 1 > 2 > 3 > 4 > 5 > 6 > X'
Night 19, 1 doesn't get a signal, Night 20, 2 doesn't get a signal, Night 21, 3 doesn't get a signal, Night 22, 4 doesn't get a signal Night 23, 5 doesn't see one, Night 24, 6 doesn't see one. What I meant was that for anyone to send a signal, they had to have gotten a signal on nights 1924, not 2024. Otherwise night 19 is useless. Thanks for helping me clarify that.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 25
 Joined: Tue Apr 17, 2012 4:09 am UTC
Re: How many prisoners?
tomtom2357 wrote:BlueSoxSWJ wrote:tomtom2357 wrote:Nights 2024: All the people that sent a signal on night 19, and received a signal every night since then, send a signal. This ensures that either a) the only people in the prison are P_{1}, P_{2}, P_{3} or a P_{4} and everyone knows it, therefore there are at most 6 people, this is scenario 5, or b) there is at least one other, and everybody knows it, therefore there are at least 5 people, this is scenario 6.
You need one more night. Consider the case of 3 P_{4}s. Call the six people now labeled 16, and assume there are at least 7 people. Suppose the warden arranges them such that:
X > 1 > 2 > 3 > 4 > 5 > 6 > X' and leaves them like this for nights 2024.
On night 20, 1 doesn't see a signal. Night 21, 2 doesn't see a signal. Night 22, 3 doesn't get a signal. Night 23, 4 doesn't get one. Night 24, 5 doesn't get one. So 15 know they're in scenario 6, but 6 now believes they're in scenario 5.
I think the way I worded that part confused you, here is what happens in that case: The warden leaves the prisoners in that configuration for nights 1924
X > 1 > 2 > 3 > 4 > 5 > 6 > X'
Night 19, 1 doesn't get a signal, Night 20, 2 doesn't get a signal, Night 21, 3 doesn't get a signal, Night 22, 4 doesn't get a signal Night 23, 5 doesn't see one, Night 24, 6 doesn't see one. What I meant was that for anyone to send a signal, they had to have gotten a signal on nights 1924, not 2024. Otherwise night 19 is useless. Thanks for helping me clarify that.
Okay, I see that now. It's probably a lot simpler to just find an upper bound first, then work on further refining it and differentiating your labeled groups. That way you don't have to worry about who knows what and can just make sure every piece of knowledge you're sending out gets to everyone.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
The problem is: it may be a lot less complicated to get a bound first, but it is a lot slower and I don't want my solution to be like this:
And in fact, their solution looks a lot more complicated to me than my solution. Also, my scenarios ensure that everyone knows what scenario they're in, because the only time I split into scenarios is if everyone knows about which scenario we are going into at the time of the split.
Scenario 5: If there is less than 6 people, then one of P_{1}, P_{2}, P_{3} know it, because they received a signal on night 18. Now if one person knows, then there are 5 people, and if 2 people know, then there are 4 people.
Night 25: Those that received a signal on night 18, that are P_{1}, P_{2} or P_{3}, send a signal.
Nights 2629: The person that sent a signal on night 25, and all those that received a signal on one of the nights 25now, send a signal. This ensures that if there are five people or less, everybody knows. If someone didn't receive a signal at all on nights 2529, he knows that there are 6 people, if everyone received a signal, then we have just narrowed it down to either 4 or 5.
Night 30: All the P_{4}('s) send a signal. If one of the P_{4}'s receives a signal, then that person knows that there are 5 people, and he tells the warden that on this night. This makes sure that either they are released or there are two possibilities: a) that there are 4 prisoners, one P_{4}, and there are 2 people that will send a signal the next night, or there are 5 prisoners, 2 P_{4}'s, and 4 people will send a signal the next night. I will not split into scenarios here, because nobody would know which scenario they are in.
Night 31: All the P_{4}('s), and everybody who received a signal on night 30, send a signal. If there are 5 people, then everybody will receive a signal by now (or be P_{4}), and there will be 3 people of the 4 that sent a signal this night that received a signal, I will refer to these later. If there are four people, then there is 1 P_{4}, and either a) all four people received a signal on nights 3031 or are P_{4}, or b) 3 people either received a signal on nights 3031 or are P_{4}, and 1 person didn't receive a signal and they aren't P_{4}. This person goes tells the warden that there are 4 people.The one person that sent a signal this night, and received a signal this night, cannot tell that to the warden because to him, he could be one of the 3 people, and there could be 5 people.
Night 32: The three (that don't exist if there are 4 people) people mentioned above now know that there are 5 people, tell the warden that, and are released. If there are 4 people, nothing happens.
Night 33: Since it has come to this, there must be four people, because if there were 5 people, then there would have been the 3 people that told that to the warden. So now they go tell the warden that there are 4 people, and they are released. I have now decided on four people in less than 2 months, whereas the other strategy took over 10000 years!
If you spot an error in the above post, please say so, I thought this up in my head and this is the first time I have written (typed) it down.
lordofthesnails wrote:Impressively complicated solution, but in practice:Spoiler:
I love it!
And in fact, their solution looks a lot more complicated to me than my solution. Also, my scenarios ensure that everyone knows what scenario they're in, because the only time I split into scenarios is if everyone knows about which scenario we are going into at the time of the split.
Scenario 5: If there is less than 6 people, then one of P_{1}, P_{2}, P_{3} know it, because they received a signal on night 18. Now if one person knows, then there are 5 people, and if 2 people know, then there are 4 people.
Night 25: Those that received a signal on night 18, that are P_{1}, P_{2} or P_{3}, send a signal.
Nights 2629: The person that sent a signal on night 25, and all those that received a signal on one of the nights 25now, send a signal. This ensures that if there are five people or less, everybody knows. If someone didn't receive a signal at all on nights 2529, he knows that there are 6 people, if everyone received a signal, then we have just narrowed it down to either 4 or 5.
Night 30: All the P_{4}('s) send a signal. If one of the P_{4}'s receives a signal, then that person knows that there are 5 people, and he tells the warden that on this night. This makes sure that either they are released or there are two possibilities: a) that there are 4 prisoners, one P_{4}, and there are 2 people that will send a signal the next night, or there are 5 prisoners, 2 P_{4}'s, and 4 people will send a signal the next night. I will not split into scenarios here, because nobody would know which scenario they are in.
Night 31: All the P_{4}('s), and everybody who received a signal on night 30, send a signal. If there are 5 people, then everybody will receive a signal by now (or be P_{4}), and there will be 3 people of the 4 that sent a signal this night that received a signal, I will refer to these later. If there are four people, then there is 1 P_{4}, and either a) all four people received a signal on nights 3031 or are P_{4}, or b) 3 people either received a signal on nights 3031 or are P_{4}, and 1 person didn't receive a signal and they aren't P_{4}. This person goes tells the warden that there are 4 people.The one person that sent a signal this night, and received a signal this night, cannot tell that to the warden because to him, he could be one of the 3 people, and there could be 5 people.
Night 32: The three (that don't exist if there are 4 people) people mentioned above now know that there are 5 people, tell the warden that, and are released. If there are 4 people, nothing happens.
Night 33: Since it has come to this, there must be four people, because if there were 5 people, then there would have been the 3 people that told that to the warden. So now they go tell the warden that there are 4 people, and they are released. I have now decided on four people in less than 2 months, whereas the other strategy took over 10000 years!
If you spot an error in the above post, please say so, I thought this up in my head and this is the first time I have written (typed) it down.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 1
 Joined: Sat May 12, 2012 4:50 am UTC
Re: How many prisoners?
I've got it! You just have to request a read receipt for the email from everybody lol j/k.
Seriously though, are we only able to communicate by the lights? Are the walls and doors so thick that you couldn't yell through them or tap on them and talk to the prisoner next to you? Perhaps then you could collect and swap names until you've heard all the names several time. I'm new, so perhaps I’m not understanding, but if I was stuck in the prison and had to be sure of my answer or risk death, I wouldn't be coming up with a mega complicated solution relying on math skills alone. If I'm way off base here and ruining the spirit of the game, then I apologize.
Seriously though, are we only able to communicate by the lights? Are the walls and doors so thick that you couldn't yell through them or tap on them and talk to the prisoner next to you? Perhaps then you could collect and swap names until you've heard all the names several time. I'm new, so perhaps I’m not understanding, but if I was stuck in the prison and had to be sure of my answer or risk death, I wouldn't be coming up with a mega complicated solution relying on math skills alone. If I'm way off base here and ruining the spirit of the game, then I apologize.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: How many prisoners?
Indeed, you are not understanding. The idea is to work out a communication method given the constraints, not to imagine a way around the restraints. imo the interesting thing is that this is possible. If we just imagine the constraints away, and manage to do something without those constraints, that is entirely unremarkable and dull imo.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: How many prisoners?
My solution may have been posted and definitely assumes some things from the question. Also, I didn't use any math. Sorry.
Spoiler:

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
bentomat wrote:This assumes that the switches are not switched off when the rooms are cleaned. It also assumes that the Warden does not catch on to the plan and just keep me out of one room.
Both of these assumptions are not valid for the original problem. The lights are turned to the off position in each room when the prisoners are moved, and the warden reads the email, so he would know your plan. This is so that we are forced to solve the worst case scenario in a solution
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: How many prisoners?
tomtom2357 wrote:bentomat wrote:This assumes that the switches are not switched off when the rooms are cleaned. It also assumes that the Warden does not catch on to the plan and just keep me out of one room.
Both of these assumptions are not valid for the original problem. The lights are turned to the off position in each room when the prisoners are moved, and the warden reads the email, so he would know your plan. This is so that we are forced to solve the worst case scenario in a solution
Actually, his plan does get around that particular stumbling block  it has a crucial part that only the one person needs to know, so he can omit that part from the email entirely and still have it followed because he's the one following it.
It still fails due to the other problems, but that one doesn't stop it.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
The reason that they put it in that the warden reads the email is so that he always moves the prisoners according to the worst case scenario for your strategy. Omitting a part of the email doesn't prevent the warden from reading between the lines and destroying your strategy. Any solution must find the exact number of prisoners no matter what the warden does
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: How many prisoners?
tomtom2357 wrote:worst case scenario for your strategy
Ah, I see the objection. In this case, I see no way to further develop my previous solution.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
I have another problem that is a lot harder than the original problem:
There are 2 prison loops (loops are where each person controls the next light in the loop). The first loop has m prisoners, the second has n prisoners. Every day, the prisoners are moved around and exactly one prisoner from loop one and one prisoner from loop 2 swap loops. This prisoner does not know that they swapped loops. Email all prisoners your strategy
Hard Version: The warden has some truth serum that he gives to the prisoner that comes to him with the correct value of m+n. He then askes the prisoner if they know what m and n are. If the prisoner knows m and n, all the prisoners are executed. If the prisoner does not know, all the prisoners are released. Assuming m,n>2, come up with a solution that guarantees that all prisoners are released.
I think that a more fundamental problem would be to, after classifying the first person (yourself) and the second person (the person who receives your signal on the first night), come up with a way to classify a unique third person.
There are 2 prison loops (loops are where each person controls the next light in the loop). The first loop has m prisoners, the second has n prisoners. Every day, the prisoners are moved around and exactly one prisoner from loop one and one prisoner from loop 2 swap loops. This prisoner does not know that they swapped loops. Email all prisoners your strategy
Hard Version: The warden has some truth serum that he gives to the prisoner that comes to him with the correct value of m+n. He then askes the prisoner if they know what m and n are. If the prisoner knows m and n, all the prisoners are executed. If the prisoner does not know, all the prisoners are released. Assuming m,n>2, come up with a solution that guarantees that all prisoners are released.
I think that a more fundamental problem would be to, after classifying the first person (yourself) and the second person (the person who receives your signal on the first night), come up with a way to classify a unique third person.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: How many prisoners?
I think I have a partial answer to this. The idea is that the worst the warden could do is to always make information travel in a cycle that is strictly smaller than the number [imath]n[/imath] of cells, to make the prisoners wrongly guess a number that is too small; or, moreorless equivalently, to make information travel in a “rho” pattern away from the first prisoner, to make him wrongly guess a number that is too large. But since the cells are always arranged in a circular pattern, this is impossible! so we have to take advantage of this.
1. First we consider the “reduced problem” where each prisoner,
I think that after about [imath]t^2[/imath] steps, the “boss” prisoners will know for sure if [imath]n < t[/imath], thus giving an answer in [imath]O(n^2)[/imath] steps. (We easily see that this works for at least 1, 2 and 3 cells).
2. to go from the reduced to the standard problem, the first idea that comes to mind is
Using both ideas above, I think that we can solve the problem in [imath]O(n^4)[/imath] days, but unfortunately my proof is not complete yet.
edit: added spoiler tags; corrected complexity (which is actually n^4, not n^3).
1. First we consider the “reduced problem” where each prisoner,
Spoiler:
2. to go from the reduced to the standard problem, the first idea that comes to mind is
Spoiler:
Using both ideas above, I think that we can solve the problem in [imath]O(n^4)[/imath] days, but unfortunately my proof is not complete yet.
edit: added spoiler tags; corrected complexity (which is actually n^4, not n^3).
Re: How many prisoners?
Unless I'm missing something, your solution to the "reduced problem" doesn't work.
Spoiler:
Re: How many prisoners?
I'm not sure I quite understand any of the previous solutions and attempts, but let me just try my own and see what you think.
This should always work in O(n log n) time. Or did I miss something?
Spoiler:
This should always work in O(n log n) time. Or did I miss something?

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
DrZiro wrote:I'm not sure I quite understand any of the previous solutions and attempts, but let me just try my own and see what you think.Spoiler:
This should always work in O(n log n) time. Or did I miss something?
Spoiler:
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: How many prisoners?
Right, of course. So, have we accepted that SS's solution was correct? Do we have a time limit?
Here's another attempt, hopefully correct, but slow and nondeterministic:
It's not pretty, but it has a limit, anyway.
Here's another attempt, hopefully correct, but slow and nondeterministic:
Spoiler:
It's not pretty, but it has a limit, anyway.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
There are probably quite a few problems with the algorithm being nondeterministic, and the warden could find some way to mess up your information (possibly make two prisoners think they have the same number and somehow not letting that information get through or something). However, the main issue is the same as has been discussed before, that the reason the warden is in the puzzle is to make it the "worst case". So if the worst case is that two prisoners keep being the same number every time, and your method never terminating, then that is the case we consider.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 1
 Joined: Tue Dec 08, 2015 2:22 am UTC
Re: How many prisoners?
Before reading any other posts, My guess is It's not possible to create a fool proof system.
Spoiler:
Re: How many prisoners?
Would this work?
Spoiler:

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: How many prisoners?
Unfortunately, booka800's solution doesn't work.
Spoiler:
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Who is online
Users browsing this forum: Google Feedfetcher and 3 guests