## How many prisoners?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### Re: How many prisoners?

tomtom2357 wrote:
skeptical scientist wrote:
tomtom2357 wrote:An inductive solution would (probably) be easier to understand though!

Which part of my solution don't you understand?

I thought that your solution was solving a class of equations to find the correct number of prisoners, and that is not inductive.

That is one step in my solution, yes. When you said that an inductive solution would be easier to understand, I assumed you meant that you found my solution hard to understand, and was wondering what was hard to understand, so that maybe I could clarify.

Also, to be honest, I'm not quite sure what you mean by an "inductive" solution.
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

skeptical scientist
closed-minded spiritualist

Posts: 6135
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

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

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: How many prisoners?

sfwc wrote:
lordofthesnails wrote:Impressively complicated solution, but in practice:
Spoiler:
If we have 16 prisoners (not unreasonable), the warden is strong enough that we can spend a lifetime playing this game, and have narrowed it down to somewhere in the 15 - 32768 range. I suppose it's progress.

If we have 4 prisoners, and I understand correctly, we will know we have 4-8 prisoners (because the warden is horrible and won't let it be 3-4). Unfortunately, it's taken us 20 days to find out, and it takes over 10,000 years to decide on 4.

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

Non-Question Changing Idea 2:
Spoiler:
Have the prisoners track their history as we do the "spread" stage to find an upper bound (which we're doing anyways). Assuming it takes k days of spreading, we know our range is [k+1,2^k].
Labeling convention (established in another location discussing this puzzle): If you first turn on your switch on day x of spreading, you're an "Mx." By definition, you're the only M1. The person who gets your signal on night 1 is the only M2.

There might be 1 or 2 M3s, depending on whether or not you hit M2 or M2 hit you on the second spreading day. So ask "Did M1 or M2 get re-hit on spreading day 2?" [Answer yes or no questions by pinging if the answer is yes.] If yes, there's only 1 M3, and we can lower our upper bound by 2^(k-2), saving that many days every time we have to ping while following the grouping procedure.

Next, we can still find the exact number of M4s: Ask "Did M1 get re-hit on spreading day 3?", "Did M2 get re-hit on spreading day 3?", and "Did M3 get re-hit on spreading day 3?" if there's one M3, or "Are you an M3 and got re-hit on spreading day 3?" and "Are you an M3 and did NOT get re-hit on spreading day 3?" to find out exactly how many people got re-hit on day 3. For each that got re-hit, we can subtract 2^(k-3) from the upper bound, and shorten our pings a little more.

Once a group has at least 3 members, we won't necessarily be able to determine the exact number in the next group, but by asking every known subdivision that were spreading on day x if at least one member got re-hit on day x, we can get a minimum number of rehits on round x, and subtract 2^(k-x) for each one from the upper bound. (We can increase the subdivisions any time a group of size >=3 (or unknown size) has at least one member re-hit and at least one member not re-hit. For example, if there are 3 M4s, and at least 1 got re-hit and at least 1 didn't during some spreading stage, call the ones who got re-hit M4As and the ones who didn't M4Bs. One of those groups has 2 and one has 1, but even if we never find out which is which, we can increase the number of re-hits we may detect in future spreads by asking them separately if any got re-hit from that day on. Additionally, if one of those two groups does split, we can go back and figure out which group had 2 and which had 1, potentially solving other group sizes and further lowering the upper bound, or even solving the total if the warden got careless).

By following this procedure, we force the warden into a choice, assuming he's trying to prolong our stay - if he strings out the initial spread so it only hits a 1 or 2 new people each spreading day, he maximizes 2^k ... only to open the door for us to completely solve the problem by being able to figure out exactly how many new people were hit each day. If he lets it spread too freely, he minimizes k, and our pings reach everyone fairly quickly. If he aims for the middle track, we get a good number of people getting "re-hit" during the initial spread, and that provides a nice variety to everyone's history, breaking down the groups into a nice initial distribution that won't take as many "outcome 2" steps before we achieve victory.

One nitpick with the solution itself, even if we assume robots with infinite lifespans as prisoners:
Spoiler:
You've proven that the resulting system of equations has a unique solution. Does this extend to imply that the prisoners have enough information to find that solution? Or is this like the old mathematician in a burning house joke - a mathematician wakes up in the middle of the night to find a small fire has ignited in the corner of his bedroom. He gets up, walks to the kitchen, opens the cabinets, notes the presence of several pots, then turns on the kitchen sink, and notes that the water is running normally. He returns to his bedroom, declares "A solution exists!," and goes back to bed.
BlueSoxSWJ

Posts: 25
Joined: Tue Apr 17, 2012 4:09 am UTC

### Re: How many prisoners?

One nitpick with the solution itself, even if we assume robots with infinite lifespans as prisoners:
Spoiler:
You've proven that the resulting system of equations has a unique solution. Does this extend to imply that the prisoners have enough information to find that solution? Or is this like the old mathematician in a burning house joke - a mathematician wakes up in the middle of the night to find a small fire has ignited in the corner of his bedroom. He gets up, walks to the kitchen, opens the cabinets, notes the presence of several pots, then turns on the kitchen sink, and notes that the water is running normally. He returns to his bedroom, declares "A solution exists!," and goes back to bed.

Well, there's always brute-force 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

skeptical scientist
closed-minded spiritualist

Posts: 6135
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: How many prisoners?

Here is my idea: I am P1
Night 1: P1 sends a signal. If P1 receives a signal, then there is only one prisoner. If not, then whoever receives a signal is P2.
Night 2: P1 and P2 both send a signal. If there are only two people, then P1 and P2 both receive a signal. However, if there are more than two people, then 1 or 2 people (that are not P1 and P2) will receive a signal, they are P3.
Night 3: If P1 or P2 receives a signal, then they send a signal. If there are only two people, then P1 and P2 both receive a signal on this night. If not, then at most one of them (P1 or P2) 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 P3. If a signal was not sent on the third night, then there are two P3's, but nobody knows this.
Night 4: P1, P2, and the P3('s) all send a signal
Night 5-7: P1, P2, and the P3('s) send a signal if they received the signal all the nights since night 4. If all the people are classified as P1, P2 or P3, 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: P1, P2 and the P3('s) are the only people in the prison. Now if there is only one P3, then the two people mentioned in night 3 that know that there is only 1 P3, 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 P1 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.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am 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:
On the first day You turn on your switch.

On any subsequent day You turn on your switch
On any subsequent day any prisons who has ever seen his light on should rig his light and switch in such a way they would complete the circuit.
This way the light of the next room will light in stead of his.

On the night your lamp goes on You can call the number of prisons equals to the number of nights.

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 P1
Night 1: P1 sends a signal. If P1 receives a signal, then there is only one prisoner. If not, then whoever receives a signal is P2.
Night 2: P1 and P2 both send a signal. If there are only two people, then P1 and P2 both receive a signal. However, if there are more than two people, then 1 or 2 people (that are not P1 and P2) will receive a signal, they are P3.
Night 3: If P1 or P2 receives a signal, then they send a signal. If there are only two people, then P1 and P2 both receive a signal on this night. If not, then at most one of them (P1 or P2) 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 P3. If a signal was not sent on the third night, then there are two P3's, but nobody knows this.
Night 4: P1, P2, and the P3('s) all send a signal
Night 5-7: P1, P2, and the P3('s) send a signal if they received the signal all the nights since night 4. If all the people are classified as P1, P2 or P3, 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: P1, P2 and the P3('s) are the only people in the prison. Now if there is only one P3, then the two people mentioned in night 3 that know that there is only 1 P3, 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 P1 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: 6
Joined: Fri Mar 13, 2009 5:20 pm UTC

### Re: How many prisoners?

The thing I think you don't understand is that you don't have to know who P1 and P2 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 P1, P2, etc. They are not assigned based on what cell they are in, but based on what signals they received on previous nights. P1 may be in the cell before P2 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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am 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.
ElPresidente

Posts: 12
Joined: Thu Jun 24, 2010 6:00 pm UTC

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

Posts: 216
Joined: Tue Mar 29, 2011 1:41 pm 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.
BlueSoxSWJ

Posts: 25
Joined: Tue Apr 17, 2012 4:09 am UTC

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

Posts: 216
Joined: Tue Mar 29, 2011 1:41 pm 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 P3, then two people know about it, if there are two P3's, then there are at least 5 people. Therefore, the two (possibly non-existant) 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 P3's, and therefore the two people don't exist or b) There is only 1 P3, 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 P3 (note: this may be nobody, as it is still possible that there are 2 P3's), send a signal.

Nights 11-17: 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 P3 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 P1, P2, P3, and we know they are unique.
Night 18: P1, P2, P3 all send a signal.

Night 19: P4 is now classified as the person(s) that receive a signal from Night 18 that are not P1, P2 or P3. Now P1, P2, P3 and the P4('s) all send a signal.

Nights 20-24: 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 P1, P2, P3 or a P4 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.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: How many prisoners?

tomtom2357 wrote:Nights 20-24: 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 P1, P2, P3 or a P4 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 P4s. Call the six people now labeled 1-6, 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 20-24.
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 1-5 know they're in scenario 6, but 6 now believes they're in scenario 5.
BlueSoxSWJ

Posts: 25
Joined: Tue Apr 17, 2012 4:09 am UTC

### Re: How many prisoners?

BlueSoxSWJ wrote:
tomtom2357 wrote:Nights 20-24: 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 P1, P2, P3 or a P4 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 P4s. Call the six people now labeled 1-6, 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 20-24.
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 1-5 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 19-24
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 19-24, not 20-24. 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.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: How many prisoners?

tomtom2357 wrote:
BlueSoxSWJ wrote:
tomtom2357 wrote:Nights 20-24: 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 P1, P2, P3 or a P4 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 P4s. Call the six people now labeled 1-6, 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 20-24.
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 1-5 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 19-24
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 19-24, not 20-24. 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.
BlueSoxSWJ

Posts: 25
Joined: Tue Apr 17, 2012 4:09 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:
lordofthesnails wrote:Impressively complicated solution, but in practice:
Spoiler:
If we have 16 prisoners (not unreasonable), the warden is strong enough that we can spend a lifetime playing this game, and have narrowed it down to somewhere in the 15 - 32768 range. I suppose it's progress.

If we have 4 prisoners, and I understand correctly, we will know we have 4-8 prisoners (because the warden is horrible and won't let it be 3-4). Unfortunately, it's taken us 20 days to find out, and it takes over 10,000 years to decide on 4.

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 P1, P2, P3 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 P1, P2 or P3, send a signal.

Nights 26-29: The person that sent a signal on night 25, and all those that received a signal on one of the nights 25-now, 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 25-29, 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 P4('s) send a signal. If one of the P4'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 P4, and there are 2 people that will send a signal the next night, or there are 5 prisoners, 2 P4'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 P4('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 P4), 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 P4, and either a) all four people received a signal on nights 30-31 or are P4, or b) 3 people either received a signal on nights 30-31 or are P4, and 1 person didn't receive a signal and they aren't P4. 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.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 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.
l_n_hughes

Posts: 1
Joined: Sat May 12, 2012 4:50 am UTC

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

jestingrabbit

Posts: 5386
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### 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:
The email directs every prisoner, me included, to turn on the light switch in his or her room. I will then turn off the light switch in any room I enter (as a result of the Warden's room change thing). Given an infinite amount of time, I am assuming I would have been placed in every room. By counting the number of switches I switched off, I could count the number of rooms and therefore the number of prisoners.
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.
bentomat

Posts: 4
Joined: Tue May 29, 2012 2:11 pm 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.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

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

Posts: 499
Joined: Mon Apr 21, 2008 4:53 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.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

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

Posts: 4
Joined: Tue May 29, 2012 2:11 pm 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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

Previous