How many prisoners?

[sfwc]

You, together with a finite number n-1 of other ideal mathematicians, have been arrested on a whim by a generic evil dictator and are about to be locked up in a prison. The prison is circular, with n identical windowless cells arranged in a ring around a central court. There are some problems with the lighting system - the light switch in each cell controls the light in the next cell clockwise around the ring. Even worse, electric power is only provided to the lights for one tenth of a second each night, just after midnight.

The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.

The warden visits you in your cell, and explains that if you are able to communicate despite these precautions he will consider you all worthy of release. At any time, any prisoner who believes he has discovered how many prisoners there are may petition the warden for release. That prisoner will be allowed one guess at the number of prisoners; if they guess correctly, then all the prisoners will be released, but if they guess incorrectly then all the prisoners will be executed.

You have been chosen to devise a strategy by means of which you will be able to discover the number of prisoners. You may compose a single email outlining your strategy, which will be passed to all the prisoners. However, your strategy must be foolproof, as the warden (who has a deep hatred of ideal mathematicians) will also read your email.

Is there a strategy which will guarantee your release? If so, give one. If not, why not?

[WarDaft]

Might be possible.

You can distinguish between the case of 1 other prisoner and more than 1 other prisoner by seeing if you can receive responses from the prisoner in the next room with a latency of 1. Thus the warden cannot trick you into thinking that there is 1 other prisoner when there is more. If we find that it is possible to sequentially attempt to prove that there are more than N prisoners for each N, then we can solve the problem successfully.

The strategy you email out will then simply be for each prisoner to set the switch to the same state their light was on the previous night. Everything else is up to you.

[Pelli]

Assuming the e-mail cannot name specific prisoners, so that they all use the same strategy:

Spoiler:

Even if the strategy contains randomness, there is always a non-zero chance that up to day k, all prisoners have done the exact same thing. So no matter what strategy, they will not in finite time be able to exclude the possibility that n=1?

Edit: Oh, "I" am a distinguished prisoner...

[gcoope]

What does the 1/10th of a second limit mean for the prisoners?

Can they react in this time and turn their switch? Or do they just find out whether the switch in the room next to them is on or off?

Even if they cannot react in this time, can they switch the switch over in this 1/10th of a second?

Do the prisoners have time to change the switch in their room after this before they are moved rooms? Do they have time to move a switch in the new room before midnight?

Do they know when midnight is if nothing happens at all to their light?

[Qaanol]

The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.

all the cells cleaned to prevent prisoners leaving messages

I presume this to mean that the light switches are removed from the cells immediately. Since the warden is worried about the prisoners using them to communicate, and everything that could be used to communicate is cleaned out of the cells, the light switches are removed as well.

Or at the very least, the polarity of the switches are randomized everyday (so up may be on or off in each cell independently) and the positions of the switches are randomized as well. Thus, every time you are put in a new cell, you have no information about whether the light is on or off until midnight happens, and that doesn’t tell you anything about the previous occupant of the room because the wardens played with the switches before you were put there.

So…yeah. No possible way to communicate, because the problems statement specifically mentions that anything that could be used to send messages gets cleaned out.

[douglasm]

So, each night each prisoner can send one bit of information to one other prisoner, with the recipient determined by a malicious Warden. Not possible. The low bandwidth combined with the total lack of control over who receives each bit is way too much.

It might be possible if the nightly re-shuffling of prisoners between cells were removed, but that lack of control over who receives or consumes any given bit of information completely kills any possibility of a solution.

[t1mm01994]

Let's take a stab at this and see how far I get.

Spoiler:

Small steps first. Reckon there are at max 2 prisoners; either there is just you or there is just you and someone else. This way it is quite easy, as your lightswitches toggle eachothers rooms, and as such you can spot if someone turns the light on. The email is simple: If you exist, turn on the light.
Now on to 3 at max. To differentiate this from the 1 prisoner case isn't as hard, as proven before, but to differentiate 2 from 3 takes a bit more thought.
Just an idea:
Protocol:
First day, you (A) flip the switch. The one who receives that (B) will flip his switch. If there is a 3rd person, he will not have seen light on day 2, and as such can call 3 prisoners. If there is no call on day 2, B can call 2 prisoners. If there is no call on day 3, A can call 1 prisoner.

Below here a start to the process of developing this process. If
[spoiler]The first day, you will turn on your light. Someone will receive that, he is now called the Lightman (L, title changes each day). You yourself are the counter (C) and the other one's cell has not lit up, so D for darkness. One night has passed, and all spaces have moved. Now noone but L turns on their light, and either C or D gets their light turned on.
Say it is C. He will know now there are at least 2 prisoners; this is a nice thing. Seeing as the situation now is CFD (You, one who has not seen light and a Finished(F), who has taken and given), something has to happen with D to make sure he gives out a signal; otherwise the Warden can easily spoil this plan by alternating C and F in rooms, signalling to eachother, not being able to differentiate from 2. D on this day turns on his switch; this will cause 2 person's lights to go on; D and either C or F. Either way, this is impossible in the 2person case, so there are 3.
Say it is D.

So seeing how it is possible for 3, I'd say it is possible for more too... Who can expand this?[/spoiler]
I took 1/10th of a second to mean no light signals across more than 1 cell, so you can program your switch at the start of the day, and the receiver knows that at that split second. They do have clocks, and normal lights, but cannot see eachother, and there is a flashlight going on if the switch is pressed.
Correct me if this interpretation is incorrect.

[gcoope]

The prisoners can find an upper limit on their population:

Spoiler:

At first only prisoner 1 (that's me) is an Alpha, the rest are Betas. The prisoners alternate between "spreading" and "zeroing". The "spreading" round lasts only one night, in it anyone who is an Alpha will turn on the light of the next cell, anyone who's light comes on will be an Alpha from now on, anyone who's light does not come on will stay the same.

Now the number of Alphas will increase since the rooms are in one nice big loop, so will be at least k and will be at most 2^k where k is the number of rounds of spreading that have occurred.

In the first night of the zeroing round anyone who is an Alpha will turn the light on, anyone who is a Beta will not. On subsequent nights of the zeroing round anyone who has seen their light off at all before will turn it off on all following nights until the next spreading round (but Alphas do not become Betas). Anyone who has only seen lights on will keep turning their light on. There are 2^k nights of zeroing.

If any of the prisoners are Betas then the off lights will propagate throughout the population "mopping up" all of the on lights of the Alphas. After 2^k nights everyone's light will be off.

If all of the prisoners are Alphas then all of the prisoners lights will be on after 2^k nights.

But we have already said that there are at least k and at most 2^k Alphas, so there must be at least k and at most 2^k prisoners, and this is information that everyone has access to.

A potential avenue from this:

Spoiler:

So the prisoners all find an upper limit for their population, lets say they know there are at least 10,000 of them. Now every 10,000 nights the first prisoner (you?) sends out 1 bit of information, this is propagated throughout by all the prisoners, if they see a light on they switch all the following nights, if not they just leave the switch off. 9,999 nights later everyone will have this bit of information, due to the layout of the rooms. Repeating this the first prisoner can send arbitrary messages to the group, bitwise.

Now he sends the message, "the next person to receive a light switch is prisoner number 2". Thus we have exactly one prisoner who knows themselves to be number 2. Now both of these prisoners can communicate with the group, being careful to say when it is the other's turn to speak.

I can't see how to sensibly define a third prisoner though, I'm stumped.

[WarDaft]

So the prisoners all find an upper limit for their population, lets say they know there are at least 10,000 of them. Now every 10,000 nights the first prisoner (you?) sends out 1 bit of information, this is propagated throughout by all the prisoners, if they see a light on they switch all the following nights, if not they just leave the switch off. 9,999 nights later everyone will have this bit of information, due to the layout of the rooms. Repeating this the first prisoner can send arbitrary messages to the group, bitwise.

Not so, the warden can control the path of the message through the prisoners. They could loop it back to you in any amount of time they choose including as many or few of the prisoners as they chose. I believe as stated the problem is equivalent to the warden re-wiring the switches however they wish so that all prisoners remain in the same single loop, and never moving the prisoners from room to room.

I'm fairly sure any solution will involve all other prisoners acting as bit propagators, and you sending out sequences to rule out populations less than N for each N. Note that this category of solutions provides maximum concealment of information from the warden - the warden cannot predict what sequences you will send out, or how you will interpret what you receive. As such, we may be able to show that the warden can do no better than re-arranging the prisoners at random.

[gcoope]

Not so, the warden can control the path of the message through the prisoners. They could loop it back to you in any amount of time they choose including as many or few of the prisoners as they chose. I believe as stated the problem is equivalent to the warden re-wiring the switches however they wish so that all prisoners remain in the same single loop, and never moving the prisoners from room to room.

Ah but the message will propagate to at least one new prisoner at every stage, if it didn't then the current group of prisoners with the message would all have to be in a loop for one night. We know that the prisoners are actually arranged in one large loop so a smaller loop is not possible. If they message propagates to at least one new prisoner every night then it must reach all of them by the end of our 10,000 nights.

edit: Are there as many mathematicians as there are cells?

[sfwc]

I think you've mostly latched on to the problem as I intended it, but I'll add some clarifications to be on the safe side.

What does the 1/10th of a second limit mean for the prisoners?

Can they react in this time and turn their switch? Or do they just find out whether the switch in the room next to them is on or off?

They can't react - they just find out the state of the switch next door.

Even if they cannot react in this time, can they switch the switch over in this 1/10th of a second?

Again, no.

Do the prisoners have time to change the switch in their room after this before they are moved rooms?

Yes, but all the switches will be turned off by the cleaners if the cells are cleaned.

Do they have time to move a switch in the new room before midnight?

Yes, they always have time to do this.

Do they know when midnight is if nothing happens at all to their light?

Yes, they can tell. That is, they are able to judge this well enough that they know each day how many nights have passed and what message was intended for them on each night.

I presume this to mean that the light switches are removed from the cells immediately. Since the warden is worried about the prisoners using them to communicate, and everything that could be used to communicate is cleaned out of the cells, the light switches are removed as well.

Or at the very least, the polarity of the switches are randomized everyday (so up may be on or off in each cell independently) and the positions of the switches are randomized as well.

No, none of this happens. The cleaners want to stop the prisoners leaving behind messages in the cells, so that the only way they can communicate is via the lights. The only way the cleaners interact with the light switches is to turn them off.

I took 1/10th of a second to mean no light signals across more than 1 cell, so you can program your switch at the start of the day, and the receiver knows that at that split second. They do have clocks, and normal lights, but cannot see eachother, and there is a flashlight going on if the switch is pressed.
Correct me if this interpretation is incorrect.

I'm happy with that interpretation.

Are there as many mathematicians as there are cells?

Yes.

[pimverkerk]

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.

[t1mm01994]

Is this a problem to which the outcome is known to you or something that needs to be explored? The two require quite different approaches.
Carrying on with my spoiler - by the way, anyone mind to check it?

Spoiler:

Seeing how I solved max 2 and then max 3, max 4 would be the way to go. For ease, label the prisoners A, B, C and D, with A being you; the planmaker.
The first night, you, A again turn on your light, to identify a 2nd prisoner: wlog this is B.
Then here comes the random brainstorm again... Prepare!
So, we have to rule out the case in which there are 4, in that case we can just reduce to max 3. So, we need a way to identify D and let D know he has been identified. Thus, after A and B have been identified, let the 2 of them both turn on the light. This will either spark A and C (wlog)'s light, or B and C, or C and D. Since A and B's situation in this case still are symmetrical (or to be made so) either A and C or D and C get their light turned on.
Say A and C get their lights turned on. In this case D doesn't get his light turned on, something that is only possible in the 4-person case. D calls 4 persons. If A sees light and there is no call for 4 persons, he can conclude that there are at most 3 prisoners. This will return later.
Say C and D get their lights turned on. In this case both A and B do not get their lights turned on, something that is only possible in the 4-person case. A and B now need to communicate they both didnt get their lights turned on, or likewise, C and D that they did.
Main problem I encounter: How do 2 people communicate in this case... Not solved that yet. Work in progress!

[WarDaft]

Ah but the message will propagate to at least one new prisoner at every stage, if it didn't then the current group of prisoners with the message would all have to be in a loop for one night. We know that the prisoners are actually arranged in one large loop so a smaller loop is not possible. If they message propagates to at least one new prisoner every night then it must reach all of them by the end of our 10,000 nights.

edit: Are there as many mathematicians as there are cells?

This is not at all the case. Suppose the first night, the sequence goes YOU, A, B, such that B will see A's message, and A will see yours.

So we have:
YOU, A, B; A gets the bit
YOU, A, B; B gets the bit
_,YOU,B,A; A gets the bit
_,_,YOU,A,B; B gets the bit
...

Where _ represents any person in the room. Now, as the rooms are all indistinguishable, this is equivalent too:
YOU, A, B; A gets the bit
YOU, A, B; B gets the bit
YOU, B, A; A gets the bit
YOU, A, B; B gets the bit

So the warden can choose up to around n/2 bits of your message that will simply never get back to you.

Likewise, the warden could do this:
YOU, A, B; A gets the bit
A, YOU, B; You get the bit back.

Solutions, if possible, will almost certainly take advantage of the fact that when the warden moves a bit back, they move (an) other bit(s) forward.

[sfwc]

Is this a problem to which the outcome is known to you or something that needs to be explored?

The answer is known to me.

[gcoope]

This is not at all the case. Suppose the first night, the sequence goes YOU, A, B, such that B will see A's message, and A will see yours.

So we have:
YOU, A, B; A gets the bit
YOU, A, B; B gets the bit
_,YOU,B,A; A gets the bit
_,_,YOU,A,B; B gets the bit
...

In the answer I gave the prisoners keep turning their light on, they don't just "pass it on" once. Thus each night the number of prisoners with the on message (if there is one) increases until everyone has it.

Haven't got any further with this problem, we can try the same tactic as the other problem where the warden creates large groups behaving the same as each other, in fact it is easy to pair up all but 2 or 3 of the prisoners and have every prisoner with a double who is receiving and giving the same information, can't quite stop any information from travelling though.

[WarDaft]

Ah, yes, that will spread throughout, sorry.



AHA! Of course!

Spoiler:

Godel encoding! In a predetermined period of N nights, a prisoner may be sure of communicating log(N) bits to exactly one other prisoner by turning on their light once on the night whose value expressed in binary represents the information they wish to send.

This allows the mathematicians to gradually accrue and transmit more and more information. They will of course need to live practically forever, but if they do then they should be able to get out.

[magemax]

A question that might be important (or not, I feel really schizophrenic, some parts of me want to demonstate that cannot work, and some other still believe in information transmission) : Are prisonners aware when they are moved ? If so, they can act differently depending on whether or not (or the number of times) they have been moved.

If not, the problem is indeed equivalent to the warden rearranging the wires each night in one single loop (which would make the story more realistic than being moved without seeing anything of the prison)

[Ermes Marana]

Possible working method:

Spoiler:

1. Get an upper bound for the number of prisoners. For the first k days, anyone who has ever seen a light always turns on their light (I turn mine on on the first day). After k days, at most 2^k have seen lights. For the next 2^k days, anyone who hasn't seen a light on the first k days turns on their lights, and anyone who sees a light now joins them. After those 2^k days, either all of the lights will be on (which means everyone knows we start over with a bigger k), or all the lights will be off (which means everyone knows there are at most 2^k prisoners).

Once we have an upper bound M we can make sure information gets spread completely by waiting M days while everyone who sees a light turns their light on.

2. The plan now is to test if there is exactly one prisoner, then 2, and so on.

To test if there are P prisoners, I start by turning my light on on day 1. Each day everyone who has seen a light turns their light on, until P days have passed. If there are exactly P prisoners, then on day P we all turn the lights on. Consider yourself responsible for a recruit if you turned your light on, but the person counterclockwise from you did not. There are exactly P prisoners iff there are P-1 recruits in P days.

There are 2^(P+1) sequences in which 1 means you were either recruited or got a recruit that day, and 0 means you didn't (consider the first spot day -1). We can go through them all in order and if anyone has that sequence they say so.

For example, if there are in reality 3 prisoners the test for 3 prisoners must give us back:

1100 ...or... 1110
0110 ......... 0100
0010 ......... 0010

And we will be able to say there are 3 prisoners, because no more than 1 prisoner could have any of those sequences.

If the repeated rows (if any) are written in:

1. the sum of each column after the first must be even
2. the sum of column n can be at most 2^(n-1)
3. the sum of column n can be at most 1 more than the sum of previous columns combined
4. the total sum must be at least 2P - 1 when testing for P (equality means you are done)

For example, if there are 6 prisoners, here is a possible result for the 6-prisoner test.

1110000
0110000
0011000
0001000

The third and fourth sequences occur twice each, which is easy to discover using rules 1-4, showing that there are exactly 6 prisoners.

I'm guessing it will always be easy (at least for perfect mathematicians), but I'll think some more about how to show that (if it is true).

[Nitrodon]

Possible working method:

Spoiler:

1. Get an upper bound for the number of prisoners. For the first k days, anyone who has ever seen a light always turns on their light (I turn mine on on the first day). After k days, at most 2^k have seen lights. For the next 2^k days, anyone who hasn't seen a light on the first k days turns on their lights, and anyone who sees a light now joins them. After those 2^k days, either all of the lights will be on (which means everyone knows we start over with a bigger k), or all the lights will be off (which means everyone knows there are at most 2^k prisoners).

Once we have an upper bound M we can make sure information gets spread completely by waiting M days while everyone who sees a light turns their light on.

2. The plan now is to test if there is exactly one prisoner, then 2, and so on.

To test if there are P prisoners, I start by turning my light on on day 1. Each day everyone who has seen a light turns their light on, until P days have passed. If there are exactly P prisoners, then on day P we all turn the lights on. Consider yourself responsible for a recruit if you turned your light on, but the person counterclockwise from you did not. There are exactly P prisoners iff there are P-1 recruits in P days.

There are 2^(P+1) sequences in which 1 means you were either recruited or got a recruit that day, and 0 means you didn't (consider the first spot day -1). We can go through them all in order and if anyone has that sequence they say so.

For example, if there are in reality 3 prisoners the test for 3 prisoners must give us back:

1100 ...or... 1110
0110 ......... 0100
0010 ......... 0010

And we will be able to say there are 3 prisoners, because no more than 1 prisoner could have any of those sequences.

If the repeated rows (if any) are written in:

1. the sum of each column after the first must be even
2. the sum of column n can be at most 2^(n-1)
3. the sum of column n can be at most 1 more than the sum of previous columns combined
4. the total sum must be at least 2P - 1 when testing for P (equality means you are done)

For example, if there are 6 prisoners, here is a possible result for the 6-prisoner test.

1110000
0110000
0011000
0001000

The third and fourth sequences occur twice each, which is easy to discover using rules 1-4, showing that there are exactly 6 prisoners.

I'm guessing it will always be easy (at least for perfect mathematicians), but I'll think some more about how to show that (if it is true).

Spoiler:

Suppose you're testing for 9 prisoners, and get the following result:

111100000
011100000
001100000
000100000
000110000
000010000

The prisoners can determine that there are 2 of the third row, K of the fourth row, and 4-K each for the fifth and sixth rows. However, there is no way to determine the exact value of K from this information alone. The number of prisoners is either 9, 10, or 11.

[WarDaft]

Okay, solved.

Spoiler:

First, we determine the upper bound of the number of prisoners, we will call this B.

Then using Gödel transmissions as I described before, I transmit the string "You are the first person to receive a message from the plotter". Something shorter would also work, but for now we just want to prove it's possible.

We now have two distinguished prisoners, ourselves and the first other prisoner.

Then we transmit "You are the second person to receive a message from the plotter" and the first other prisoner transmits "You are the first person to receive a message from the first other prisoner". This obviously allows the individual or individuals who receive these messages to know who they got them from. The aggregate knowledge amongst all the prisoners who have sent or received messages is now enough to determine whether 3 or 4 prisoners have communicated. We perform this B times with each prisoner deriving a unique name based on the chain that was taken to notify them. Then, each prisoner will transmit everything they know B times.

It will take a long time, but if every prisoner always transmits the entirety of their knowledge, then the warden cannot possibly contain any given subset of knowledge to a subset of the prisoners, and it will eventually all reach every prisoner, including you, and you will be able to announce the exact number of prisoners. This should not take longer than 2↑↑2B days. This bound may be high though, I did not give it as much thought.

Since you have N ideal mathematicians, surely they have already solved the complex algorithms necessary to fully describe protein folding and you all have derived immortality serums. Perhaps that's even why you're in prison! After all, you couldn't let just anyone be immortal, that would cause chaos. Clearly only people clever enough to derive the formulas themselves can handle the responsibility of living forever.

[douglasm]

Spoiler:

It will take a long time, but if every prisoner always transmits the entirety of their knowledge, then the warden cannot possibly contain any given subset of knowledge to a subset of the prisoners

I don't think that detail is right.

Spoiler:

The Gödel encoding uses when the message is sent to encode the information. If you and another prisoner are sending different messages, that means the two messages are sent on different nights - and the Warden can control who they go to independently. In particular, he can send your message to the first guy and the first guy's message to you, which prevents any knowledge from spreading beyond the two of you. If you want guaranteed spread of knowledge to at least one additional prisoner, the total body of knowledge in question must all be transmitted on the same night.

[skeptical scientist]

Spoiler:

It will take a long time, but if every prisoner always transmits the entirety of their knowledge, then the warden cannot possibly contain any given subset of knowledge to a subset of the prisoners

I don't think that detail is right.

Spoiler:

The Gödel encoding uses when the message is sent to encode the information. If you and another prisoner are sending different messages, that means the two messages are sent on different nights - and the Warden can control who they go to independently. In particular, he can send your message to the first guy and the first guy's message to you, which prevents any knowledge from spreading beyond the two of you. If you want guaranteed spread of knowledge to at least one additional prisoner, the total body of knowledge in question must all be transmitted on the same night.

Spoiler:

No, that part works. The result is that the total number of people knowing X increases by at least one on any day corresponding to message X, and the total number of people knowing Y increases by at least one on any day corresponding to message Y, so eventually everyone knows everything. In your example, only people who already knew something at the beginning of round 1 receive information on round 1. But the point is that they receive new information, and after round 1 that information will spread, because now both are transmitting X on the day corresponding to X, and both are transmitting Y on the day corresponding to Y.

However, there is another problem, and this is related. See my later post.

[sfwc]

Are prisonners aware when they are moved ? If so, they can act differently depending on whether or not (or the number of times) they have been moved.

The prisoners can tell when there is a general movement of prisoners and cleaning of cells. But they can't tell whether the cell they are put in after the cleaning is the same as the one they were taken out of (they can't tell whether they were moved).

If not, the problem is indeed equivalent to the warden rearranging the wires each night in one single loop (which would make the story more realistic than being moved without seeing anything of the prison)

Yes, it is equivalent to that problem.

[skeptical scientist]

Okay, solved.

Spoiler:

Then we transmit "You are the second person to receive a message from the plotter" and the first other prisoner transmits "You are the first person to receive a message from the first other prisoner". This obviously allows the individual or individuals who receive these messages to know who they got them from. The aggregate knowledge amongst all the prisoners who have sent or received messages is now enough to determine whether 3 or 4 prisoners have communicated. We perform this B times with each prisoner deriving a unique name based on the chain that was taken to notify them. Then, each prisoner will transmit everything they know B times.

Not solved. You run into problems in the quoted section.

Spoiler:

You can't show that everyone eventually gets a name this way. The reason for this is that different people are communicating on different days in order to communicate the name they have (and consequently the name that the recipient will get. So you could potentially have the plotter always transmitting to the first other prisoner whenever he transmits, and the first other person always transmitting to the plotter whenever he transmits, and so nobody beyond those two ever gets a name.

[WarDaft]

Hmm, that's right.

Spoiler:

It seems that there is no way to reliably identify a unique 3rd prisoner. Does the fact that we can eventually propagate all information still allow us to determine the total prisoner count?

It seems as if it should... if the information chains are detailed enough, then we should be able to see where each name originated. If there are two prisoners using the same name, then information should propagate differently than if only one of them were there. If the warden tries to hide them by placing one after another, we will have one of them propagating information that they were signaled by someone sharing their name. Then, so long as a group of N people sharing a name cannot inject their names into a group of less than N people sharing names identically to a group of N-1 injecting, then we should still be able to discern the total number of prisoners.

But it's more complicated now, and this isn't a sufficient description of a solution.

[skeptical scientist]

I've come up with a couple of strategies with interesting properties, one for the prisoners and one for the warden.

Strategy for the prisoners:

Spoiler:

This is a non-deterministic strategy the prisoners can use to free themselves with probability 1-e, for arbitrary e>0.

First, obtain an upper bound B on the number of prisoners. (A way of doing this was outlined above.) Now, determine the minimal N so that if B N-bit strings of 0s and 1s are generated, the probability that two are the same is less than 1-e. All prisoners randomly flick or don't flick their switches for the next N nights, and memorize the sequence they received, treating on as 1 and off as 0. The next 2^NB nights consist of 2_N rounds of B nights each. Each round corresponds to one possible N-bit sequence of 0s and 1s. On every night of the round, everyone with that particular sequence of 0s and 1s flicks their switch, as does anyone who's seen a light turn on during the round. On the last night of the round, if anyone saw the particular sequence corresponding the round, everyone's light will be on, and otherwise, everyone's off. After 2^N rounds, everyone will know how many of the possible N-digit sequences were seen. This is the same as the number of prisoners with probability at least 1-e, since it is only different than the number of prisoners if two prisoners received the same randomly generated sequence.

Strategy for the warden:

Spoiler:

This is a strategy the warden can use with at least 2N prisoners, assuming the prisoners follow a deterministic strategy. It will ensure that N of the prisoners have always perceived identical sequences of 0s and 1s. The existence of this strategy shows that no deterministic variant of the above prisoner strategy is possible, since there is no deterministic way to ensure the prisoners all have unique labels.

Since the strategy is deterministic, the warden knows what all prisoners will do on night k, given their histories. He wants N of the prisoners (the "treatment group") to always experience the same thing, and there are at least N other prisoners (the "control group"). Assuming the warden has been successful through night k-1, all prisoners in the treatment group will be doing the same thing on night k, either turning the switch on, or turning it off. If there is at least one prisoner in the control group matching the treatment group, the warden can put all treatment group prisoners together, following that particular prisoner. Then all members of the treatment group perceive the same thing on night k. Otherwise, everyone in the control group is doing one thing, and everyone in the treatment group is doing the opposite on night k. Since there are at least as many members in the control group as there are in the treatment group, the warden can arrange the circle so that no two members of the treatment group are adjacent, which ensures that they all receive the same signal on night k.

[JBJ]

It seems that whatever strategy is given, the warden is going to try to foil it using the best tool at his disposal, which is re-arranging the prisoners.

Would it be possible to "play" the warden? In other words, could one develop a public strategy that appears to be an attempt at communication, but is actually a private strategy to get the warden to rearrange prisoners in a predictable way that would reveal to the planner the actual number of prisoners?

[Ermes Marana]

Possible working method:

Spoiler:

1. Get an upper bound for the number of prisoners. For the first k days, anyone who has ever seen a light always turns on their light (I turn mine on on the first day). After k days, at most 2^k have seen lights. For the next 2^k days, anyone who hasn't seen a light on the first k days turns on their lights, and anyone who sees a light now joins them. After those 2^k days, either all of the lights will be on (which means everyone knows we start over with a bigger k), or all the lights will be off (which means everyone knows there are at most 2^k prisoners).

Once we have an upper bound M we can make sure information gets spread completely by waiting M days while everyone who sees a light turns their light on.

2. The plan now is to test if there is exactly one prisoner, then 2, and so on.

To test if there are P prisoners, I start by turning my light on on day 1. Each day everyone who has seen a light turns their light on, until P days have passed. If there are exactly P prisoners, then on day P we all turn the lights on. Consider yourself responsible for a recruit if you turned your light on, but the person counterclockwise from you did not. There are exactly P prisoners iff there are P-1 recruits in P days.

There are 2^(P+1) sequences in which 1 means you were either recruited or got a recruit that day, and 0 means you didn't (consider the first spot day -1). We can go through them all in order and if anyone has that sequence they say so.

For example, if there are in reality 3 prisoners the test for 3 prisoners must give us back:

1100 ...or... 1110
0110 ......... 0100
0010 ......... 0010

And we will be able to say there are 3 prisoners, because no more than 1 prisoner could have any of those sequences.

If the repeated rows (if any) are written in:

1. the sum of each column after the first must be even
2. the sum of column n can be at most 2^(n-1)
3. the sum of column n can be at most 1 more than the sum of previous columns combined
4. the total sum must be at least 2P - 1 when testing for P (equality means you are done)

For example, if there are 6 prisoners, here is a possible result for the 6-prisoner test.

1110000
0110000
0011000
0001000

The third and fourth sequences occur twice each, which is easy to discover using rules 1-4, showing that there are exactly 6 prisoners.

I'm guessing it will always be easy (at least for perfect mathematicians), but I'll think some more about how to show that (if it is true).

Spoiler:

Suppose you're testing for 9 prisoners, and get the following result:

111100000
011100000
001100000
000100000
000110000
000010000

The prisoners can determine that there are 2 of the third row, K of the fourth row, and 4-K each for the fifth and sixth rows. However, there is no way to determine the exact value of K from this information alone. The number of prisoners is either 9, 10, or 11.

Possible fix for my method:

Spoiler:

Start a new sequence, beginning with all the 4th rows turning on their lights on day 1. Then everyone attaches the new sequence to the end of their last one and declares their full sequence.

It is not possible for none of the 4th rows to get a recruit on day 1, so either we will get new information by dividing the 4th rows into 2 smaller groups, or all of them get recruits on day 1.

If they recruit only uniquely identified prisoners, then we have counted them. If they recruit part of a repeated row, that gives us new information by breaking up that row. If they recruit only full (all repetitions) rows of known size, we have counted them.

The last possibility is that none of the above happen and they recruit full rows of unknown repetitions. This gives us an equation R1 = R2 + R3 + ... + Rk + C, where the Ri's are unknown #'s of row repetitions and C is a known constant.

We can keep repeating this technique with every row of unknown repetitions, so we can assume the only situation happening anymore is getting these equations. We can also get extra equations from the later days of a sequence.

If there are 10 prisoners in your example we might get extended sequences:

R1 00010
R2 00010
R3 00100
R4 11110
R5 01100
R6 00100

Giving us the equations:

R4 + R5 = 4 (from day 3 of 1st sequence)
R5 - R6 = 0 (from day 4 of 1st sequence)
R4 - R5 = 0 (from day 1 of 2nd sequence)
R4 + R5 - R6 = 2 (from day 2 of 2nd sequence)
R4 = 2 (from day 3 of 2nd sequence)

Which is more than enough to solve.

I'm still not sure this always works though.

[sfwc]

This is a non-deterministic strategy the prisoners can use to free themselves with probability 1-e, for arbitrary e>0.

Yes, that works. However, just as for the other question I asked, I'd like to know if there is a strategy which guarantees release - I take that as excluding even nondeterministic strategies which work almost surely but not surely. So I'll be explicit about it here: my question is whether there is a deterministic strategy.

Would it be possible to "play" the warden?

No. The warden knows your strategy.

[Pelli]

Here is a strategy my friend came up with, which solves the problem with probability 1 (so only "almost surely") provided each prisoner has a random number generator:

Spoiler:

First, find an upper bound B for the number of prisoners, as described earlier.

We also use the method to "ping" everybody as described earlier, i.e. during B days: The prisoner(s) that want to send the ping start as "activated". The activated prisoners send out ones, while not activated prisoners send out zeroes. If you receive a one then you become activated. After the 2^k days we have that either everyone is activated (someone pinged) or nobody is (nobody pinged).

Then do this:

Code: Select all

We shall identify prisoners in order, calling them Prisoner 1, Prisoner 2, etc. Everybody that has been identified knows their own number.
Let k be the number of identified prisoners. We shall make sure that everybody knows k all the time.

We start off with the first person ("me") being "identified" as Prisoner 1. Everybody knows this.
Loop {
   //Check if we're done
   Everybody that is not yet identified sends a ping. (B days)
   If there is no ping, then we are done and the answer is k, known to everybody.

   //Find a candidate set for new prisoners to identify, and calculate its size
   Day A: Everybody that has been identified sends a one. (1 day)
   Let P the set of unidentified prisoners that received a one during Day A.
   (Everyone knows if they belong to P or not.)
   For i = 1 to k {
      Prisoner i sends a ping if and only if it received a one during Day A. (B days)
   }
   Now everybody knew k and can count the number of pings. The difference is the number of prisoners in P.
   (The number of prisoners in P is at least 1, or else we would have been done already.)

   //Perform the identification
   If P contains one prisoner, then he becomes Prisoner (k+1) and we can then repeat with k = k+1.
   Otherwise, we need to differentiate between the different prisoners of P, and we do it like this:
   Loop {
      Everybody in P chooses a random number a_i between 1 and |P|.
      For i = 1 to |P| {
         If you chose i, then ping. (B days)
      }
      If there was a ping every time {
         Everybody knows the prisoners in P chose different a_i.
         The prisoner who chose a_i now identifies themself as Prisoner (k+a_i), and we repeat with k = k+|P|.
      }
      //Otherwise, we try again.
   }
}


The random number generator is only needed to differentiate between prisoners in the last bit of the main loop. Each time, with probability 1 the prisoners will eventually generate different random numbers and thus succeed in identifying themselves. Note that the warden cannot stop the prisoners even if he from the start knows all the random numbers that are going to be generated.

[sfwc]

That's a very pleasant strategy, and it completely solves the nondeterministic version of the problem.

[WarDaft]

Yes, it still works! I was actually jumping through hoops I didn't need to, and ended up pointing myself in the wrong direction.

Spoiler:

Once we have an upper bound on the number of prisoners, we send out a single chain of lights to assign a number (not uniquely) to all of the prisoners, there may be anywhere from 1 to 2^k people with k as a name.

Then, each prisoner simply prefaces their transmission of everything they know along with a statement of their number. Let X be the highest number of any prisoner who shares a label with another prisoner, N be the number of prisoners labeled X, and M be the largest set of indistinguishable prisoners. It is impossible for the warden to ensure that any of the N prisoners labeled X receive the same input for more than |M| rounds - necessarily, each round reduces |M| by one, because one of M must receive an input from someone not in M up the chain and they become distinguishable from M (this would not be true if M was the set of all of the prisoners, but thankfully we know it's not!) - after which point, they may each distinguish themselves from other prisoners labelled X based on their received inputs so far. Thus, for any given X, we can eventually reduce the number of indistinguishable prisoners to those with labels less than X. Once we have done this for every X less than 2^k, every must have a unique input. We now use the input they have received as a second stage label. We then go into an information collection mode, where each prisoner transmits the roster as they know it. The length necessary to ensure success of each of these actions can be determined if we have an upper bound on the number of prisoners, and we do. After a very very long time, you can be sure you have the entire roster and can announce correctly.

[skeptical scientist]

Nice job on the probability 1 solution. I'm beginning to suspect there is no deterministic solution, but I don't have a proof.

Yes, it still works! I was actually jumping through hoops I didn't need to, and ended up pointing myself in the wrong direction.

No, you still don't have a complete solution.

Spoiler:

necessarily, each round reduces |M| by one, because one of M must receive an input from someone not in M up the chain and they become distinguishable from M

This is false.

Spoiler:

You only know that one of M receives an input from someone not in M if everyone not in M is sending on the same night. But if everyone not in M is sending on the same night, then everyone in M could be after someone who is sending, in which case everyone in M is still indistinguishable.

Did you see my above proof that it is impossible, through a deterministic strategy, to ensure that each prisoner eventually has a unique identity?

[WarDaft]

Ah, but...

Spoiler:

It does not matter when people not in M signal. We presume all members of M to be indistinguishable, thus, they will all signal on the same night. If not, they are not indistinguishable! The warden cannot create a closed loop of members of M. Because of this, necessarily, the number of indistinguishable prisoners must decrease in a predictable manner. Although the proof of this is indeed a bit more complicated than I first thought, if the warden arranges there to be multiple indistinguishable groups the size of M.

[skeptical scientist]

Ah, but...

Spoiler:

It does not matter when people not in M signal. We presume all members of M to be indistinguishable, thus, they will all signal on the same night. If not, they are not indistinguishable! The warden cannot create a closed loop of members of M. Because of this, necessarily, the number of indistinguishable prisoners must decrease in a predictable manner. Although the proof of this is indeed a bit more complicated than I first thought, if the warden arranges there to be multiple indistinguishable groups the size of M.

Spoiler:

No, the number of indistinguishable prisoners never needs to decrease beyond half of the total prisoners. Did you see my proof that the warden can ensure that with 2N prisoners, N of them are always indistinguishable, so long as they use a deterministic strategy?

[WarDaft]

Ah, found it. Sorry, too many spoiler tags around.

Spoiler:

So we have to assume that up to half of the prisoners are in the dark, as far as labeling is concerned

Hmm, in the method I described, no two distinguishable prisoners will signal on the same night. That means it must be done by interleaving the indistinguishable prisoners with the rest. That means that the rest as an aggregate will have one message from each indistinguishable prisoner.

By that proof, it looks like the warden can maintain almost as many indistinguishable groups as they wish so long as no group is larger than half, and no group needs to be split during the interleaving deception. However, the warden cannot maintain more than one group for each integer power of two, and each such group is bounded in size by that integer power, via the initial forking naming.

So it really is up to just the information aggregation to count the number of prisoners, if deterministically possible.

Let's suppose, whenever possible, that the warden does not make two indistinguishable prisoners distinguishable (otherwise, the prisoners may win by sheer tenacity, though I do not yet know if being absolute in this is a good strategy for the warden) So, in a group of N prisoners, N/2 will be indistinguishable, and their messages will go to groups of size N/4, N/8, .. 2, 1, 1, prisoners. Group N/4 will have to report to groups N/8, N/16 ... 2, 1, 1, or else group N/2 may be broken. Likewise, group N/8 may only report to smaller groups. Group 2 reporting to groups 1,1 will produce a unique path back to you (one of the 1s) for each member of group 2. Group four reporting to 2,1,1 thus also has a unique path, and group 8, and so on for each group.

So, we number each prisoner, then in a series of secondary rounds, the N/2 group announces themselves and what they know, followed by the N/4 group, the N/8 group, and so on. These groups can identify themselves because we have an upper bound on the number of prisoners, and thus, if announcing in reverse order to that upper bound, N/2 will go first naturally. With an upper bound of K prisoners, we repeat this at least K times. Throughout this process, the warden can maintain indistinguishable groups, but in doing so, they form a unique chain of communication down to the size 1 groups, and by our repetition, all information will have trickled down to you, and you can correctly determine the number of prisoners.

So, if the warden has some other strategy which defeats this prisoner strategy, then it is not in the wardens best interest to maintain the maximum amount of indistinguishable prisoners.

[Scuttlemutt]

I'm not sure if anybody has taken this into account, but if there's n-1 prisoners and n cells, doesn't that mean there is an empty cell somewhere? What if a critical message hits the empty cell in any of the strategies above?

[skeptical scientist]

I'm not sure if anybody has taken this into account, but if there's n-1 prisoners and n cells, doesn't that mean there is an empty cell somewhere? What if a critical message hits the empty cell in any of the strategies above?

There are n prisoners: you and n-1 other prisoners.

[skeptical scientist]

Okay, I have a full solution. (I'm pretty sure. It's sufficiently complex that I may have made a mistake. I'd be interested if anyone has a simpler solution, or a simpler proof of the necessary lemma. I'm also hoping sfwc will share his solution, now that we've found a solution.)

Spoiler:

There is a deterministic strategy that the prisoners can use to free themselves.

To show this strategy works, we need the following lemma.

Lemma: Suppose you have unknowns a₁ to a_n, except a₁=1. Moreover, for every nonempty proper subset A of {a₁, ..., a_n}, there is another subset B with B\A nonempty and an equation of the form "sum of A equals sum of B", and the resulting system of equations is solvable in the positive integers. Then the system of equations has a unique solution in the positive integers.

The proof of the lemma is rather involved, so I'm deferring the proof to the second spoiler. We can just take it as a black box, and the rest will make sense.

We will make use of the upper bound procedure established earlier, that the prisoners can use to establish an upper bound B on the number of prisoners. After the prisoners have done this, we will also use the ping procedure, described by Pelli:

We also use the method to "ping" everybody as described earlier, i.e. during B days: The prisoner(s) that want to send the ping start as "activated". The activated prisoners send out ones, while not activated prisoners send out zeroes. If you receive a one then you become activated. After the B days we have that either everyone is activated (someone pinged) or nobody is (nobody pinged).

Additionally, we will make use of a third procedure, the "group division procedure" which identifies the prisoners base on history. If this procedure is called on night n+1, each prisoner starts by turning their history, which can be thought of as an n-bit sequence of 0s and 1s, into a number between 1 and 2ⁿ. Then there are 2ⁿ rounds of pinging, where on round k, every prisoner (besides the plotter) with history k sends a ping. After the n rounds, the plotter is group 1, and everyone who sent a ping during the mth round with pings is group m+1. At the end, everyone knows which group they are in, as well as the total number of groups. Moreover, everyone in the same group had identical histories through the first n nights.

Subsequently to initially establishing an upper bound and performing initial group division, the strategy consists of a sequence of rounds. Each round starts with the prisoners to groups G₁...G_n by the group division procedure. The round will result in one of two outcomes:

1. The prisoners obtain a system of equations for the sizes of the groups which has a unique solution by my lemma. They can therefore compute the size of each group, and the total number of prisoners. (VICTORY!)
2. The prisoners obtain a new set of group memberships, such that the new memberships form a refinement of the previous set (each group is either the same as a group from the previous round, or is a proper subset of a group from the previous round, and at least one group from the previous round is split into more than one group).

Since a refinement results in an increase in the number of groups, which is bounded by the total number of prisoners, outcome 2 can only happen finitely often, and then outcome 1 must happen, resulting in victory.

Here is the round procedure:

Code: Select all

for (X a nonempty, proper subset of {G_1...G_n})
{
   everyone in a group in X flicks their switch (1 night)
   for (i=1 to n)
   {
      everyone in group i who received one of the flicks from X pings (B nights)
   }
}

perform new group divisions (call the group division procedure)


If the number of groups in the new division is more than the the number of groups in the old division, we're in outcome 2. Repeat the round procedure with the new groups. If the number of groups in the new division is the same as the number of groups in the old division, we know that for each group G, every member of G experienced exactly the same history during the round. That means when everyone in a group in X flicked their switch, either everyone in G received a flick, or nobody in G received a flick. Therefore, if Y is the set of groups which received a flick from X, we know that the total number of people in a group in Y is the same as the total number of people in a group in X. Moreover, we know that Y contains a group not in X. Therefore, this gives a system of equations as in the lemma, which the prisoners can solve to find the size of each group, hence the total number of prisoners.

Proof of the lemma needed above:

Spoiler:

Lemma: Suppose you have unknowns a₁ to a_n, except a₁=1. Moreover, for every nonempty proper subset A of {a₁, ..., a_n}, there is another subset B with B\A nonempty and an equation of the form "sum of A equals sum of B", and the resulting system of equations is solvable in the positive integers. Then the system of equations has a unique solution in the positive integers.

We will actually prove the stronger lemma 2 below (the reason for this is that lemma 2 is proved by induction, and we need the stronger form as our inductive hypothesis). For the purposes of lemma 2, all linear combinations are assumed to have positive coefficients.

Lemma 2: Suppose you have unknowns a₁ to a_n, except a₁=1. Moreover, for every nonempty proper subset A of {a₁, ..., a_n}, there is another subset B with B\A nonempty and an equation of the form "sum of A equals linear combination of B", and the resulting system of equations is solvable in the positive integers. Then the system of equations has a unique solution in the positive integers.

Proof:
By induction on n. Certainly the result is true for n=1 and n=2. Assume n>2, the result is true for n-1. Suppose you have a system of equations as above for {a₁...a_n}. We will show how to eliminate a_n from the system of equations so as to get a system of equations in {a₁...a_n-1} with the same property. By the inductive hypothesis, this system must have a unique solution, which leads to a unique solution for {a₁...a_n}.

Let A be a subset of {a₁...a_n-1}. We have the following equations:

sum(A) = L₁
sum(A)+a_n = L₂
a_n = L₃

where L₁ is a linear combination of a subset of {a₁...a_n} including some element not in A, L₂ is a linear combination of a subset of {a₁...a_n} including some element other than a_n not in A, and L₃ is a linear combination of {a₁...a_n} including some element other than a_n. The fact that the equation a_n = L₃ has a solution in the positive integers implies that if a_n appears in L₃, the coefficient of a_n is strictly less than 1, so we can obtain a new equation of the same form where a_n does not appear in L₃. Therefore, we may as well assume a_n does not appear in L₃.

Let L₁' be the linear combination obtained from L₁ be replacing the occurrence of a_n, if any, in L₁ by L₃. Now we get the following equations in {a₁...a_n-1}:

sum(A) = L₁'
sum(A)+L₃ = L₂

At least one of following two possibilities must hold:
1) sum(A) = L₁' involves at least one variable not in A.
2) sum(A) = L₁' has positive coefficients for every term appearing in L₃.
This is because if 1 does not hold, then the only variable not in A appearing in L₁ must have been a_n, which means that L₁' was obtained by substituting in L₃, so 2 holds.

If 1 holds, then we are done, because we have successfully removed a_n from the equation and found a new equation satisfying the conditions of the lemma. If 2 holds, then we can add some multiple of of the first equation to the second equation, to get an equation of the form

(1+M)sum(A)+L₃ = L₂+ML₁'

where the coefficients of L₃ are less than the corresponding coefficients of L₂+ML₁'. Thus

sum(A) = (L₂+ML₁'-L₃)/(1+M)

and the right-hand-side is a linear combination (with all coefficients positive!) which contains at least one variable not in A. So we are done.

Yes, I double-posted. Hopefully finding a solution is a good enough excuse.