The basic principle, as with other problems of this type, is that we start with two sets.
We want to count the size of the prison population - a set $P$ with $n$ members.
We start with two known subsets:
- $S_0$ consisting of exactly 1 person who is writing the plans.
- $P \setminus S_0$ everyone not in $S_0$
The initial goal is to partition $P$ into $k$ distinct subsets each no larger than a known limit, such that
$P \setminus \bigcup\limits_{i=0}^kS_i = \emptyset$
This gives an initial upper bound for $n$, to be referred to as $n_\max$, which will then be later refined by later stages of a protocol.
As with my answer to a similar problem, there will be multiple phases as follows:
Phase 1: round $j$ needs to define at least one new set $S_j$, in a way that guarantees that all prisoners will eventually be in a numbered set.
Phase 2: any sets whose size is known (and in particular any sets whose size is known to be exactly 1) announce information they already have about the size of the remaining sets of unknown size.
Phase 3: once the bounds on the size of the sets have been reduced as much as possible using already-known information, a protocol is run that guarantees to subdivide the remaining sets.
Phase 1
All prisoners start off with a token count of zero, except $S_0$ who starts off with a token count of 1.
The number of tokens in circulation at most doubles each round.
Each prisoner's token count is personal to them.
Round 1 Day 1 (definition of $S_1$)
$S_0$ turns on exactly one switch.
Define $S_1$ as the person who saw a light on, who now also has a token count of 1.
Round 1 Day 2 (announcement of uncounted population)
Everyone with a token count of zero turns on ALL their switches.
Everyone else leaves ALL their switches off.
Round 1 Day 3 (propagation of message)
Everyone with a token count of zero OR who saw any light on day 2 turns on ALL their switches.
Everyone else leaves ALL their switches off.
As the message has now necessarily reached at least one of $S_0 \cup S_1$ on day 2, and the other on day 3, everyone now knows that
$P \setminus (S_0 \cup S_1) \ne \emptyset$
Round $j$ Day 1 (definition of $S_j$)
Everyone turns on at most a number of switches equal to the number of tokens they hold. If the room is indistinguishable from one they were in on a previous day, they turn on different switches if possible.
Everyone adds the number of lights they see to their token count, and keeps notes about exactly how much they added to their token count this day.
Define $S_j$ as the set of people who saw a light on and previously had a token count of zero. These people immediately reduce their token count to 1, in order to help limit the size of future sets.
Round $j$ Day 2 (announcement of uncounted population)
Everyone with a token count of zero turns on ALL their switches.
Everyone else leaves ALL their switches off.
Round $j$ Days 3 to $2^j+1$ (propagation of message)
Everyone with a token count of zero OR who saw any light since day 2 of this round turns on ALL their switches.
Everyone else leaves ALL their switches off.
Each day means the message necessarily reaches at least one more person, and $\bigcup\limits_{i=0}^jS_i$ contains at most $2^j$ members.
Even if all "definition of set" messages were received by the maximum possible number of people, everyone now knows either that
$P \setminus \bigcup\limits_{i=0}^jS_i \ne \emptyset$
or
$P \setminus \bigcup\limits_{i=0}^jS_i = \emptyset$
Phase 2
Eventually, after $k$ rounds the population will be fully partitioned into sets, giving an upper bound $n_\max = 2^k$ to the population.
The lower bound $n_\min$ is 3 (unless $n_\max = 2$ of course). To see this, imagine the wiring diagram with 3 rooms as below, and the warden putting the prisoners in the same cell each night. The number of switches in room 1 can be arbitrarily large, so the number of rounds before the prisoner who is kept in room 2 throughout sees a light can also become arbitrarily large, but all prisoners will eventually become part of a numbered set.
Each round in phase 2 will aim to reduce $n_\max$ by establishing bounds on the size of $S_j$.
All messages in phase 2 will involve everyone who can confirm the proposition turning on ALL their lights, and anyone who sees any lights turning on all their lights in a propagation phase.
For now, we are ignoring the fact that $n_\max$ (the number of rooms) and $c_\max$ (the maximum time to get a message to everyone) are not necessarily equal.
Phase 2 round 1
This takes zero days (a refreshing change!). Everyone already knows that $S_1$ has exactly 1 member by design of the protocol.
Phase 2 round 2
Message 1 "Has anyone ever been in a room with more than 1 switch or more than 1 light?"
This message has such a massive effect on the whole of the rest of the protocol, that it's worth establishing now... weaker versions of the same question will be determined in later rounds as they become relevant.
If sent, there will necessarily be at least 2 senders, so we wait $n_\max - 2$ days to ensure everyone else has received it if sent.
If received, this changes the entire puzzle to the equivalent of the "circular prison of unknown size" - a problem that has already been solved. In particular the implication $S_k = \emptyset \implies S_{k+1} = \emptyset$ now holds, so we know that all sets up to the last non-empty one are also non-empty.
The rest of this protocol assumes that the "puzzle-changing" message was not received - assume a "sub-sheet" for what to do if the message was received has also been included...
The remainder of round 2 has a special format and rules, as we only need to disambiguate 3 possibilities - $S_2$ having 0, 1 or 2 members, and $S_0$ or $S_1$ already have sufficient information on their own to eliminate one of these possibilities.
Message 2 "Is $S_2$ non-empty?"
If so, everyone in $S_2$ sends confirmation, and also at least one of $S_0$ and $S_1$ will have failed to observe a light, so initiate the message too.
If $S_2$ has 2 members, there will be 4 initiators of this message and up to $n_\max-4$ recipients.
If $S_2$ has 1 member (which we don't DISCOVER until the next message is received, but is true even now), we will later be able to reduce $n_\max$ by 1, and there will be 2 initiators of this message, so we wait $n_\max-3$ days in total.
Obviously, if $S_2$ is empty, we proceed directly to round 3, skipping the remaining message for this round...
Message 3 "Did $S_2$ see 2 lights and thereby destroy a token?"
This message has a much shorter waiting time - by destroying a token in this round 2, we know that $S_3$ has a maximum of 3 members (rather than our previous estimate of 4), $S_4$ has a maximum of 6 members (rather than 8), etc.
Overall, this reduces $n_\max$ by about 25% (more precisely by $2^{k-3}$, where $n_\max$ was initially $2^{k-1}$), so the waiting time is $n_\max - 2^{k-3}-1$
Message 4 "Does the non-empty $S_2$ have exactly one member?"
(not sent if message 3 was received, as everyone already knows it to be true by implication)
If so, one of the following will be true:
- The sole member of $S_2$ saw 2 lights (and would already have sent message 3).
- Exactly one of $S_0$ and $S_1$ saw 1 light
This message always has exactly 1 sender when sent, and reduces our estimate of $n_\max$ by 1, so can be received by a maximum of $n_\max-2$ recipients if sent.
Phase 2 round $j$
Based on information in previous rounds, we define $t_\max$ for this round as the maximum number of tokens any one individual could hold. e.g. for Round 3, depending on the configuration of messages received $t_\max$ is either 2 (if $S_2$ was empty or if round 2 message 4 was sent) or 1.
Message 1 "Has anyone ever been in a room with at least $t_\max$ switches?"
(this message is only sent if $t_\max > 2$, and if all previous messages pertaining to a lower value of $t_\max$ were sent - in particular we skip it for round 3, as it's equivalent to round 2 message 1)
When sent, it means that all tokens remain valid.
When this message is scheduled but NOT received, it will have significant implications for future rounds, as any tokens in excess of $t_\max-1$ can be ignored - depending on the configuration of tokens already established in earlier rounds, we may already be able to confirm that some tokens we knew about from last round could not be used, and thus limit the maximum number of people that could possibly be members of $S_j$ and later sets, and therefore significantly reduce the commonly-known $n_\max$.
e.g. suppose in round 4 that $S_0$ held (and is known by everyone to have held) 4 tokens, with $t_\max = 4$. When this message is NOT received, everyone immediately knows that $S_0$ could not have been in a room with more than 3 switches, so the possible maximum size of $S_4$ reduces by 1, the possible maximum size of $S_5$ reduces by 2, etc.
Message 1.x, etc. "Has anyone ever been in a room with at least $x$ switches?"
The moment an upper bound for the number of switches in a single room is established, we send a further series of messages of a similar type (starting with $x = t_\max - 1$ and working down towards the number of switches previously confirmed to have been present in the same room. This gives the exact maximum number of switches known to be present in the same room.
After establishing this exact number, no further messages of this type will ever be sent again.
Message 2 "Is $S_j$ non-empty?"
Unlike round 2, for later rounds this message can only be sent by members of $S_j$. Even if $S_0$ or $S_1$ failed to observe a light, it's still possible that other sets already defined saw lights corresponding to all the switches set by them.
Initially, the maximum size of $S_j$ is assumed to be the total number of tokens in circulation at the end of the previous round (as modified by $t_\max$ if it was already common knowledge that $t_\max$ tokens were held by one individual.
Message 3.0.1 "Can $S_0$ reduce the upper bound for $S_j$ by at least one based on their private knowledge?"
$S_0$ will send this message if at least one of the following apply:
- $S_0$ saw a light on Phase 1, round $j$, day 1, activated by someone else's switch.
- $S_0$ was in a room with insufficient switches to allow them to pass on all their tokens held up to $t_\max$
- a recent reduction in $t_\max$ means that tokens $S_0$ is holding and everyone assumes will be carried forward into this round will no longer be carried forward.
Message 3.0.$x$ "Was $S_0$ able to reduce the upper bound for $S_j$ by at least $x$ based on their private knowledge?"
Similar to the previous message, but allowing for more than 1 light observed, and/or more than one switch unable to be set, etc.
A series of similar messages are sent until either:
- $S_0$ fails to send a message
- $S_j$ is now known to be of size exactly 1.
Message 3.$i$.$x$ "Was anyone in $S_i$ able to reduce the upper bound for $S_j$ by at least $x$ based on their private knowledge?"
Similar messages may be sent by each subsequent defined set, including $S_j$ itself (anyone in $S_j$ would respond in the affirmative if they saw more than the 1 light that defines them as a member of this set)
Initially, these messages must all be interpreted as though only 1 person is sending them, regardless of the bounds on the size of $S_i$.
Message 4.$i$ "Did anyone in $S_i$ have observations that differed from what we just received in messages 3.$i$.*?"
(this message is only sent for groups not known to be of size exactly 1, and where at least message 3.$i$.1 was received).
When a positive response is received, this defines a new set $S_{i_x}$ containing at least 1 member (i.e. the first time it happens for $S_i$ we defines $S_{i_1}$, the second time, we define $S_{i_2}$, etc. if $S_{i_1}$ later proves to have different subsets, we might define $S_{i_{1_1}}$ etc.), and drawn from the members of $S_i$. The bounds on $S_i$ and any set it was drawn from, or any other sets drawn from it are immediately adjusted accordingly.
We then check for messages 3.$i_x$.* to establish what the observations of this new set were, and if $S_{i_x}$ is not of size exactly 1, the next message slot would be reserved for message 4.$i_x$, etc.
When no response is received, and the lower bound on the size of $S_i$ is greater than 1, we re-apply the effects of messages 3.$i$.* to further reduce the upper bound on the size of $S_j$.
Phase 3 (if needed)
NB the (presumed) worst case runnning time (which I'm not planning to calculate precisely this time!) occurs when phase 1 has as many rounds as possible, because each round takes twice the previous one, and the initial delay for at least the first few rounds of phase 2 is similar to the final round of phase 1.
This worst case running time will be proportional to $2^{n t}$, where $t$ is defined by the structure of the prison, but represents the maximum number of tokens a member of a newly-defined set can hold before they're guaranteed to be able to get a message to another prisoner. This is, itself, limited by the maximum number of switches in any room.
To hit that worst-case running time, the guard would put the prisoner holding the fewest tokens into a room with a large number of switches, of which only 1 connects to a room holding a prisoner not in a defined set, and only 1 light that is connected to a switch in a room where any other prisoner holding tokens is residing. All other prisoners holding tokens have their switches connected only to each other's rooms. (See diagram at the start of phase 2 for an example of this with exactly 3 rooms).
In order to have ANY set containing more than 1 prisoner at the end of phase 1, this implies phase 1 completes in a fraction $1/2^t$ of the time it could have done.
Phase 2 will determine $n$ precisely, as long as no set is larger than size 2.
In order for phase 3 to be necessary at all, there must exist some ambiguity over the size of at least one set, which itself means we must have had at least one set of size at least 3, which was split into two subsets based on differing observations, but where the subset(s) of size at least 2 continued to have otherwise identical observations.
That also implies that phase 1 was shorter than it could have been by a factor of at least about $2^{t^2}$ for each such group of 3, giving plenty of time to disambiguate compared to the worst case running time.
As with the previous problem, if several rounds of phase 2 have occurred with such ambiguities still remaining, it may be more efficient to have designed the work-sheet to include some rounds of what is described as "phase 3" interspersed with "phase 2".
For this problem, a lot of phase 3 will be based on sharing more detailed observations from the key days in phase 1 - how many switches were in the room, how many lights (including the ones that were off), etc.
However, because the warden knows this information will be compared, he'll presumably have arranged for each to be in indistinguishable rooms on any relevant date (indeed, it's possible that every room in the prison could be indistinguishable, e.g. containing the same number of switches and lights with a complicated and unknown wiring pattern between them.)
Unfortunately, this is where the plan falls apart.
Unlike the previous puzzle, members of a subset can form one or more closed loops where each have identical observations, and those not in the set also have identical observations.
For example, if a set of unknown size has determined that if they're in a room with 2 switches, they'll switch the "left" switch, they can be put in a section of the prison where the "left" switches loop around so they'll only see each other's lights. That section could even be cross-wired to another section of unknown size (both size 3 in the diagram) which has the "right" switches in a loop as below:
A completely deterministic strategy known to the warden, together with an appropriate design for the prison's wiring diagram, would seem to allow him to arrange prisoners such that some subset of them will never have any difference in observations to each other (possibly having multiple such subsets that are always arranged to interact with each other in ways that avoid allowing any disambiguation).
As such, this either needs an even more sophisticated strategy on the part of the prisoners that hasn't occurred to me yet, or some element of randomness... in which case we might as well introduce the randomness earlier...
Forgetting phase 3 of a fully deterministic strategy for now (and avoiding re-writing the earlier stages), I can finish this by adding a non-deterministic "phase 3" as follows:
Message R1: entropy injection.
For 1 day, everyone sets their switches completely randomly.
Message R2.i.x "Did anyone in $S_i$ see at least $x$ lights on the last entropy injection day?"
This works similarly to message 3 in the later rounds of phase 2.
When a negative response is eventually received as values of $x$ increase, a further message occurs:
Message R3.i "Does anyone in $S_i$ disagree with the observations from the most recent message R2?
As with "message 4" in the later rounds of phase 2, a positive response splits the set, and increases the lower bound on the size of the set from which it was split. Implications in terms of limits on sizes of other sets (and hence of $n_\max$) are worked thorough.
Messages R2 and R3 are then repeated for any further relevant sets of unknown size. Only sets of ambiguous size defined in the same round are considered relevant.
If no relevant set is split, the procedure is repeated from R1.
Optional short-cuts
In the base rules, each round of phase 1 takes twice as long as the previous round, as we have to assume that the warden COULD have been arranging prisoners so that every token is held by a different person during the "definition of $S_j$", and that the warden then arranges them on subsequent days so that exactly one person discovers the existence of an uncounted population on subsequent days.
The writer of the instructions can build in a hard-coded upper limit, assuming $n_\max \le 2^k$ for some value of $k$. After round $k$ the number of days to wait for any given message to be received can be capped at this hard-coded limit.
A small gain can also be made by assuming $n_\min \ge 2^l$, and skipping the "announcement of uncounted population" stage for the first l rounds, but at the cost of significantly delaying the release of prisoners if that assumption proves to be false (as we'd be waiting unnecessarily long for the messages that prove the assumption incorrect).
If we're capping $n_\max$, we can also skip most "announcement of uncounted population" and "message propagation" stages in phase 1, reducing most rounds of phase 1 to a single day. In the previous problem, $S_k = \emptyset \implies S_{k+1} = \emptyset$, but that's not the case for this problem, so we're already needing to test for emptyness on each set.
It may be more efficient to run the non-deterministic "phase 3" immediately after the relevant round of phase 2, so that the next round of phase 2 can proceed with more certainty. NB only sets of uncertain size need this treatment. A large set of precisely known size only becomes a problem if it is later split into subsets with differing observations. THAT is the time at which we would run the round of "phase 3".
