How many prisoners?

[tomtom2357]

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.

[BlueSoxSWJ]

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.

[skeptical scientist]

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.

[tomtom2357]

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

[Tuinkabouter]

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

[Tuinkabouter]

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

[tomtom2357]

The thing I think you don't understand is that you don't have to know who P₁ and P₂ 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₁, P₂, etc. They are not assigned based on what cell they are in, but based on what signals they received on previous nights. P₁ may be in the cell before P₂ 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.

[ElPresidente]

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.

[sfwc]

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.

[BlueSoxSWJ]

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.

[sfwc]

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.

[tomtom2357]

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₃, then two people know about it, if there are two P₃'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 P₃'s, and therefore the two people don't exist or b) There is only 1 P₃, 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₃ (note: this may be nobody, as it is still possible that there are 2 P₃'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 P₃ 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₁, P₂, P₃, and we know they are unique.
Night 18: P₁, P₂, P₃ all send a signal.

Night 19: P₄ is now classified as the person(s) that receive a signal from Night 18 that are not P₁, P₂ or P₃. Now P₁, P₂, P₃ and the P₄('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 P₁, P₂, P₃ or a P₄ 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.

[BlueSoxSWJ]

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 P₁, P₂, P₃ or a P₄ 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₄s. 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.

[tomtom2357]

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 P₁, P₂, P₃ or a P₄ 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₄s. 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.

[BlueSoxSWJ]

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 P₁, P₂, P₃ or a P₄ 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₄s. 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.

[tomtom2357]

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:

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 P₁, P₂, P₃ 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₁, P₂ or P₃, 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 P₄('s) send a signal. If one of the P₄'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₄, and there are 2 people that will send a signal the next night, or there are 5 prisoners, 2 P₄'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₄('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₄), 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₄, and either a) all four people received a signal on nights 30-31 or are P₄, or b) 3 people either received a signal on nights 30-31 or are P₄, and 1 person didn't receive a signal and they aren't P₄. 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.

[l_n_hughes]

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.

[jestingrabbit]

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.

[bentomat]

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.

[tomtom2357]

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

[douglasm]

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.

[tomtom2357]

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

[bentomat]

worst case scenario for your strategy

Ah, I see the objection. In this case, I see no way to further develop my previous solution.

[tomtom2357]

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.

[Jérôme ^]

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, more-or-less 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,

Spoiler:

instead of sending one bit/day to its neighbour, is allowed to send an integer number. Also for reasons that will be apparent later I will call the time period one “month” instead of one day. To defeat both strategies by the warden, we proceed as follow: one prisoner is the “boss”, all others become “henchmen”. Each month, each henchman shouts a number equal to the maximum of all numbers he previously heard; the boss shouts 1 + the same maximum. (The first month, the boss shouts 1 and all henchmen shout 0. The second month, if the boss heard 1, then he knows he's alone; else he heard 0 and still shouts 1, while the henchman who heard him shouts 1, and all other henchmen shout 0). In this way, the warden will be unable to stop the progression of larger numbers in the cells (the “maximum” operation takes care of this).

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

Spoiler:

using binary encoding: split each months in a number of days and broadcast the numbers as bit sequences, with one bit/day. However, the warden may now completely break up this by rearranging the prisoners; since he may add an arbitrarily large number of errors, he can defeat any error-correcting coding. Well, save for one encoding, which is the naive encoding: at month n, all numbers x that circulate are smaller than [imath]n[/imath]. We then declare the month [imath]n[/imath] to have [imath]n[/imath] days and transmit a number [imath]x[/imath] as a sequence of [imath]x[/imath] ones, followed by [imath](n-x)[/imath] zeroes. At the end of the month, each prisoner will assume that the number he received is given by the last day of the month where he received a one. This way, it is easy to prove that, if the number [imath]n[/imath] was transmitted by somebody, then somebody else will have received that same number; if the numbers [imath]n[/imath] and [imath]n-1[/imath] were transmitted, then at least somebody has heard [imath]n[/imath] and somebody else (probably two somebodies else, actually) has heard [imath]n-1[/imath]; and so on.

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

[Nitrodon]

Unless I'm missing something, your solution to the "reduced problem" doesn't work.

Spoiler:

Under that strategy as written, if n is at least 3, the warden can always make the "boss" prisoner receive the sequence 0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,...

[DrZiro]

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:

On night 1, the special prisoner is "positive" and the others are all "negative". Each night, anyone who is positive sends a signal (the others don't), and anyone who receives a signal becomes positive (the others don't change). As long as there are still negatives, at least one negative will become positive. After k nights, if there are k or fewer prisoners, everyone will be positive.

After k nights, we change the rules, so that instead anyone who does not receive a signal becomes negative, and those that do receive a signal stay unchanged. If there are still negatives, the negativity will spread, as before. In that case, after another k nights, everyone will be negative. But if there were k or fewer prisoners, they are all still positive.

Thus, with a predetermined k, we can check in 2k nights whether there are k or fewer prisoners.

Now we repeat that for a predetermined sequence of k. One obvious sequence is 1, 2, 3, 4... That should solve it, but it will take quadratic time.

Perhaps a better sequence would be 1, 2, 4, 8, 16..., and then after we've determined an interval, do a binary search in that interval.

For example, suppose we've tested up to k=8, always getting a negative result (there are more than k prisoners). When we reach k=16, we get a positive (there are k or fewer prisoners). Now we know that the number of prisoners n is in the interval 8 < n <= 16. Next we test the middle of the interval, so k=12. Let's say that's negative; 12 < n <= 16. Then we try k=14. Let's say that's positive; 12 < n <= 14. Then we try with k=13. Let's say that's negative; 13 < n <= 14, so n=14.

This should always work in O(n log n) time. Or did I miss something?

[tomtom2357]

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:

On night 1, the special prisoner is "positive" and the others are all "negative". Each night, anyone who is positive sends a signal (the others don't), and anyone who receives a signal becomes positive (the others don't change). As long as there are still negatives, at least one negative will become positive. After k nights, if there are k or fewer prisoners, everyone will be positive.

After k nights, we change the rules, so that instead anyone who does not receive a signal becomes negative, and those that do receive a signal stay unchanged. If there are still negatives, the negativity will spread, as before. In that case, after another k nights, everyone will be negative. But if there were k or fewer prisoners, they are all still positive.

Thus, with a predetermined k, we can check in 2k nights whether there are k or fewer prisoners.

Now we repeat that for a predetermined sequence of k. One obvious sequence is 1, 2, 3, 4... That should solve it, but it will take quadratic time.

Perhaps a better sequence would be 1, 2, 4, 8, 16..., and then after we've determined an interval, do a binary search in that interval.

For example, suppose we've tested up to k=8, always getting a negative result (there are more than k prisoners). When we reach k=16, we get a positive (there are k or fewer prisoners). Now we know that the number of prisoners n is in the interval 8 < n <= 16. Next we test the middle of the interval, so k=12. Let's say that's negative; 12 < n <= 16. Then we try k=14. Let's say that's positive; 12 < n <= 14. Then we try with k=13. Let's say that's negative; 13 < n <= 14, so n=14.

This should always work in O(n log n) time. Or did I miss something?

Spoiler:

What you missed is that the order changes every night. So after your scheme with k positive nights and k negative nights, if everyone is a negative prisoner, then you do know that the number of prisoners is greater than n+1 (after the first night there are two positives, the special one, and the one who received the light). However, if everyone is positive, all you know is that the number of prisoners is at most 2^k. So, say that n=14, as in you example. What could happen (and would if I was warden), is that you would try k=1, negative. Trying k=2, you would still get negative. However, when you tried k=4, I would arrange the prisoners in this way:

Night 1: P N N N N N N N N N N N N N
Night 2: P N P N N N N N N N N N N N
Night 3: P N P N P N P N N N N N N N
Night 4: P P P N P N P N P N P N P N
Night 5: P P P P P P P P P P P P P P

Oops, now everyone thinks there are 4 or fewer prisoners. They do the search for k=3, and it turns up negative. So you go to the warden and say: "I know the answer! There are four prisoners!", and you all die.

This method does not give you the answer to "Is the number of prisoners less than k?" In fact, with the warden trying his hardest to mess up your plans, your upper bound could be as high as 2^n-1

[DrZiro]

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:

Spoiler:

As established, we can get an upper bound on the number of prisoners (n), which is no more than 2^n. We can also, in 2^n time, answer any question on the form "does the statement q hold for any prisoner", or equivalently "does the statement q hold for all prisoners".

In the first round, only the special prisoner is "numbered", with number 1.

In each following round, each numbered prisoner nondeterministically decides whether to send a signal or not, with probability of sending 1/r. The probability of a given numbered prisoner being the only one who does is (1/r)*((r-1)/r)^(r-1). There is at least one numbered prisoner whose recipient is not numbered, so the probability of such a prisoner being the only sender is at least the above.

Then you ask "did p1 send", "did p2 send" etc. Each question takes at most 2^n, and you need to ask r times, so it takes at most r*2^n time to find out how many senders there were. Then you can similarly ask how many numbered recipients there were, and thus find out if there was exactly one unnumbered recipient. If that was the case, that prisoner gets added to the list of numbered ones. We ask one additional question, "is there still any unnumbered prisoner" (the time is negligible, since it's just one question), and as long as there is, we move to the next round.

Each round has an expected time no greater than
2r*2^n*(1/r)*((r-1)/r)^(r-1) =
= 2^(n+1)*((r-1)/r)^(r-1)
and since r is no more than n,
<= 2^(n+1)*((n-1)/n)^(n-1)
This needs to be repeated n times, so in total
n*2^(n+1)*((n-1)/n)^(n-1)
which I think is O(2^n), or something.

It's not pretty, but it has a limit, anyway.

[tomtom2357]

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.

[TakenItEasy]

Before reading any other posts, My guess is It's not possible to create a fool proof system.

Spoiler:

Information can travel at one cell/day, so we would count the number of days for that information to complete the circle.

However, if al prisoners are randomly reassigned to cells every day, we would need to set the switches to define the state of that cell.

The problem is that we need to have three states to designate cell counted, cell not counted and the original cell.

Presumably cells cannot leave behind any signal other than the switch itself but a two state switch can't account for the three states required. Unless the original person can break his switch or something to that effect.

[booka800]

Would this work?

Spoiler:

Each day, you turn on your light. If a prisoner gets a light, and has gotten a light before, they turn on their light. If they get a light, and have not gotten a light before, they do nothing. If I'm correct you should receive a light yourself on day n.

[tomtom2357]

Unfortunately, booka800's solution doesn't work.

Spoiler:

If there are three prisoners, and they are arranged 123 every night (person 1 is you), then you will only receive a light on night 5. Interesting strategy though, it might serve to narrow down the number of prisoners very quickly.