The Circular Prison of Unknown Size

Question

You are the president of a secret society of mathematicians with $n$ members, including yourself. No one in the society knows what $n$ is. The dictator of the world, in an effort to erase mathematics from human history, has finally managed to capture all $n$ members of the society, and has placed them in prison.

The prison has a funny design. There are $n$ identical soundproof, windowless prison cells arranged in a circle, each containing a mathematician. The cells all have a light switch the prisoners can use, but the wiring system is screwed up, so the switch controls the light bulb in the clockwise neighboring cell. Furthermore, the switch is only capable of delivering a single flash of light at noon each day. Specifically, if this switch is set to "on" at noon, it will flash the next cell, and do nothing otherwise.

The prison warden worries that the prisoners might try to communicate using the lights, so every night at midnight, he fills all of the cells with knockout gas, cleans the cells so they can't communicate by leaving messages, sets all of the light switches to "off", and rearranges the prisoners in whatever fashion he pleases (still one prisoner per cell).

One day, the warden visits your cell. He confesses that he loves mathematics, and decides to offer your society a game to win their freedom. If any of the prisoners are able to figure out what $n$ is, they may shout out loud "There are $n$ prisoners!" (the cells are monitored with security cameras/mics). If they are correct, all prisoners will go free, and if not, they will all be executed.

The warden allows you to devise a plan for everyone else to follow. He will make $n-1$ copies of this plan, and allow every other prisoner to read it. The warden of course will also read your plan, and will perform the cell rearrangements in such a way to make it fail if he can.

What plan allows the prisoners to guarantee their freedom?

Extra for Experts: Can you find a plan which doesn't require the prisoners to make random decisions?

Notes: There is no lateral thinking required to solve this. Assume the prisoners have perfect, infinite memory, including knowledge of how many days have elapsed.

It is significant that you are one of the prisoners, and that you devise the plan. It means that while all $n-1$ other prisoners must follow the same strategy, you may follow a different strategy.

I will give priority to accepting answers which fulfill the "Extra for Experts" condition. This means there must exist a function $B(n)$ such your plan is guaranteed to stop after $B(n)$ days when there are $n$ prisoners.

This is the hardest puzzle I know, but there is a solution.

Answer 1

This was a monster of a puzzle. But I think I got it!

The following is a solution that does not use randomness, finishes in bounded time for any given circle size, and includes a (mostly- maybe a detail or two left to the reader =)) full proof of validity. Tell me if it makes sense, or if further clarification is needed.

We first define the subroutine $fill(S,k)$. This takes in a set of people, $S,$ such that everybody knows whether they are in $S$ or not. It also takes in a paramater $k$ related to how long to run for. It works as follows

1) On round 1, everybody in set $S$ turns on their light.

2) On every round from $2$ to $k$, everyone in $S$ and everyone who has seen a light on during $fill(S,k)$ turns on their light.

3) From round $k+1$ to $2^k+k+1$, everybody who saw a light on at the end of stage 2), and in every round since then, turns on their light.

Denote $S'$ to be the set of people who saw lights on round $k$. We first claim that, if S is only the leader, then regardless of $k$, at the end of this subroutine, everyone in the circle either sees a light, or does not see a light.

To see this, note that $S'$ either contains everyone or does not contain everyone. If it contains everyone, it is clear that stage 3) of the subroutine simply involves everyone turning on their light every round, and thus everyone sees a light at the end. If it does not contain everyone, then we note that the set of lights seen in each round of stage 2) at most doubles in size. Thus, at the end of stage 2), at most $2^k$ lights are on. But it's also easy to see that, if $S'$ is not the whole circle, then the set of lights on in stage 3) decreases by at least one each round. Thus, by the end, no lights will be on.

Now, suppose $ U > n$. Then, we claim that $ fill(S, U)$ will result in every light being on if and only if $S$ is not the empty set, and every light being off otherwise. This is easy to see because, if $U > n$, then $ S'$ will have to be the entire circle, as long as $S$ was not the empty set. Otherwise, if $S$ was the empty set, then clearly nobody will ever see a light.

Okay, now we're ready to describe our strategy:

Step 1. Deduce an upper bound $U$ on $n$, as done in many other solutions. We run $fill(L, k)$, where $L$ is the leader, for increasing $k$ starting at $1$. At some point, the result will be positive, with everyone seeing a light. At this point, we can be assured that the circle contains at most $2^k$ people where $k$ was the final value used to $fill$.

Step 2. Initialize by considering the leader to be in set $S_0$, and everyone else to be in set $S_1$. Let $k = 2$ represent the number of sets at any point.

Note that currently, everybody knows which indexed set they are in, and which sets exist. We will maintain this invariant so that everyone can coordinate their strategies.

Step 3. Set $done = false$. While not $done:$

3 A) Set $done = true$. For each subset $ I \subset \{1, 2, \cdots, k\}$, other than the empty set and the entire set:

3 A i) Everybody in the set $ \bigcup_{i \in I} S_i$ turns on their light once. Let $T$ be the set of people who saw lights on this day.

3 A ii) For every set $S_j$:

3 A ii a) Run $fill(S_j \cap T, U)$.

3 A ii b) Run $fill(S_j / T, U)$.

3 A ii c) If both $fills$ return positive results, then increment $k$ by 1, let $ S_j = S_j \cap T$, $S_k = S_j / T$, and set $ done = false$.

Step 4. We will prove that, when we reach this point, everyone in the circle can deduce the circle's size.

First, we prove that we eventually reach Step 4. Note that $done$ is only set to $false$ in 3) if a new set $ S_k$ is created. Furthermore, every new set created is not empty, and no nonempty set becomes empty during the algorithm, because $ S_j$ is only split if both $ S_j \cap T$ and $ S_j / T$ are nonempty. Thus, if there are $n$ people in the circle, we can create at most $n-2$ new sets before there are $n$ total sets, one person to a set, and no further sets can be split. At this point, set $3$ must terminate with $done = true$.

Now, suppose we reach step 4. For every set $S_i$, let $x_i = |S_i|$. For any partition $(A,B)$ of the $x_i$ into two nonempty sets, there was a corresponding round in the final iteration of Step 3 in which every person corresponding to $A$ turned on their light. This then resulted, for each $S_i$, in everyone in $S_i$ seeing a light on, or everyone seeing a light off. Furthermore, at least one person in an $S_i$ represented by $B$ saw a light, or else $A$ would have to be a closed loop. The key here is that we know that the number of people in $A$ who didn't see a light must be equal to the number of people in $B$ who did. This gives us an equation in the variables $x_i$, of the form

\begin{equation} \sum_{i \in X} x_i = \sum_{i \in Y} x_i, \end{equation},

where $ X \subset A$, $ Y \subset B$, and neither $X$ nor $Y$ is empty. We say that such an equation "satisfies" the partition $(A,B)$. More generally, we say that $(A,B)$ is satisfied by any equation of the form

\begin{equation} \sum_{i \in X} r_i x_i = \sum_{i \in Y} s_i x_i, \end{equation}

where all coefficients $r_i,s_i$ are positive, and $X$ and $Y$ are nonempty subsets of $ A$ and $B$. If a set of equations satisfies every partition of a set of variables, we say that that set of variables is fully satisfied. At step 4, we thus have a set of fully satisfied variables. Thus, to prove that we can deduce the size of the circle, we show that, given any set of variables such that $x_i = 1$, along with a satisfiable and fully satisfying set of equations on those variables, we can deduce the value of every variable

We use induction. For $ k = 2$ variables, we have $ x_1 = 1$, and the partition $ (x_1, x_2)$ yields $ k_1x_1 = k_2x_2$, where $ k_1, k_2 \neq 0$, so clearly both variables are determined.

Now, consider a set of $k$ variables $ x_1, x_2, \cdots, x_k$, and assume our hypothesis holds for all sets of $k-1$ variables. We will eleminate $x_k$ from the equations to construct a set of equations which fully satisfies $ x_1, \cdots, x_{k-1}$. For each partition $(A,B)$ of the remaining $k-1$ variables, there are two partitions of the whole set of variables: $ (A \cup c, B)$, and $ (A, B \cup c)$. Both of these partitions have some satisfying equation. If either of the satisfying equations don't include $c$, then we have an equation which satisfies $(A,B)$ on the first $k-1$ variables. Otherwise, if both satsifying equations include $c$ with some weight, then we can linearly combine them to eliminate $c$ and get a new equation, which some basic algebra tells us will also satisfy $(A,B)$ in the first $k-1$ variables. Thus, by doing this for every partition, we can construct a set of fully satisfying equations for $ x_1, \cdots, x_{k-1}$, which by our inductive hypothesis determines all of their values. Finally, we can consider the partition which separates $x_k$ form the other $k-1$ variables. This partition is only satisfied by a linear equation writing $x_k$ in terms of the other variables; as these are all determined, we can also determine $x_k$. Thus all variables are determined, and we are done.

Finally, since every person in the circle knows a fully satisfying set of equations on all of the subsets $S_i$, and knows that $ |S_1| = 1$, everyone in the circle can deduce the size of each subset, and of the entire circle.

Answer 2

This solution involves randomness. The mathematicians will base some of their decisions a coin flip, and with probability $1$ they will eventually know the value of $n$ and announce it.

The mathematician creating the plan is the captain.

Upper bound for $n$: This is done in a number of Rounds: Round $1$, Round $2$, etc.
Each Round is subdivided into Step A and Step B.

Step A of Round $k$ lasts for $k$ days. During this Step, the captain will always turn on their switch. Each other mathematician turns on their switch if and only if they have previously seen a light this Step (so we act as if the captain saw a light when the Step started).
At the end of Step A:

• if $k< n$, the number of mathematicians who have seen a light is between $k$ and $2^{k}$,

• if $k\geq n$, everybody has seen a light.

Step $B$ of Round $k$ lasts for $2^k$ days. During this Step, a mathematician turns on their switch if either they did not see a light during Step A or they have seen a light during Step B.
At the end of Step B:

• if everybody saw a light during Step A, then nobody saw a light during Step B,

• if somebody did not see a light during Step A, then everybody saw a light during Step B.

At the end of each round, it is common knowledge whether everybody saw a light during Step A.

Let $k_0$ be the smallest positive integer such that everybody saw a light during Step A of Round $k_0$ (it will necessarily be true that $k_0\leq n$). The value of $k_0$ is common knowledge, and at the end of Round $k_0$ every mathematician knows that $n\leq2^{k_0}$.

---

An announcement by some collection $S$ of mathematicians is a period of $2^{k_0}$ consecutive days, during which each mathematician in $S$ always turns on their switch, and starting on the second day, everybody else turns on their switch only if they have already seen a light during the announcement. At the end of the announcement:

• if at least one mathematician is in $S$, everybody will have seen a light,

• if no mathematician is in $S$, nobody will have seen a light.

So it becomes common knowledge whether or not $S$ is empty.

---

Counting mathematicians: At every point during the counting, some collection of $d$ mathematicians will be numbered #1 through #$d$. The remaining mathematicians remain unnumbered. To begin, the captain is #1 and every other mathematician is unnumbered. The mathematicians will repeatedly attempt to assign an additional mathematician a number.

Before each attempt, an announcement is made by every unnumbered mathematician. If there are no unnumbered mathematicians, this fact becomes common knowledge, and everyone can announce the largest number that has been assigned.

On the first day of the attempt, each numbered mathematician chooses whether or not to turn on their switch based on fair coin flip. Everybody who sees a light on this day is called a candidate.

Next, there are $d+1$ announcements. For $j\leq d$, the $j$-th announcement is made by mathematician #$j$ if they turned on their switch on the first day, and by nobody otherwise. The $(d+1)$-st announcement is made by every unnumbered candidate.

If exactly one of the numbered mathematicians made an announcement, and an unnumbered candidate made an announcement, then the (necessarily unique) unnumbered candidate is assigned #$d+1$; the attempt was a success. Otherwise no additional mathematician is numbered; the attempt was a failure. It is common knowledge whether a new number was assigned.

So long as there is a least one unnumbered mathematician, the probably of an attempt succeeding is positive. With probability $1$, every mathematician will eventually be numbered.

Answer 3

The task may be established, in a huge but bounded number of moves, by first establishing an upper bound M on the number of prisoners (possibly using Julian Rosen's approach) and repeatedly performing the following steps:

1. Observe the number of days elapsed as D.
2. Each prisoner will have seen one of 2^D possible on/off sequences thus far.
3. Pick a sequence for each of the next 2^D groups of M days; on the first day of each group, have prisoners turn on their light if the initial sequence of lights they've seen is appropriate for that group. On the remaining days, have prisoners turn on their light if they're in the group or have seen the light from anyone else that was.
4. Once all sequences have been enumerated, start over unless the information observed from all the announcements is sufficient to ascertain the total number of prisoners.

Without using randomness, it is not possible to ensure that every prisoner will ever end up seeing a unique sequence of lights; if there are N prisoners, the warden could arrange to have up to N/2 of them that always see the same sequence. On the other hand, every light that gets turned on each day must be accounted for; this will make it possible to infer the size of larger cliques.

For example, start with a single node turning on his light. Exactly one other prisoner will see that, implying there are two cliques with one prisoner each. If both see a light the next day, they're the only prisoners. Otherwise, if either of those first two prisoners sees the light of the other on the next day, that will imply the existence of another single-prisoner clique (single-prisoner cliques, once identified as such, aren't very interesting). If neither saw a light, that implies that the light was seen by two other people. On the next day, four lights will be switched on, and it will be possible to tell how many of the first four people see them. If none see them, then on the next day eight lights will be switched on. Here's the first real difficult spot.

If either all four or none of the new people see the light on the eight-light day, it will be easy to tell exactly how many other people are going to see the light. Things get tricky if some do but not all. That will create an uncertainty of +/-2 with the number of lights that will be seen in the next step. Further steps will have even more uncertainty.

I think the uncertainties will get resolved, however, by watching what happens when the cliques from the set of four are asked to broadcast their existence, and different nodes are asked who saw what when afterward; I'm still working on the exact cases, but I think they all work.

Answer 4

We can solve this in a brute force way by construction a universal strategy. We will systematically categorize all the information a prisoner could possibly have and then, noting that we can generate all that information in countably many turns, we will proceed to generate that information. I have no idea what information is useful or how to interpret the results, but hey, if our mathematicians are perfectly logical, they can figure it out! (There's nothing to distract them, even!)

Notice that if a certain set of prisoners turns their lights on one turn, and then the same set* turn their lights on again, we gain no information. Moreover, notice that whatever information we do gain is a function of our strategy - that is, the pattern of lights flashing and not flashing that a prisoner observes is meaningless without knowing what groups were instructed to turn their lights on at each turn.

Therefore, we construct the following "hierarchy" of information, where $S_n$ represents the set of possible pieces of information on the $n^{th}$ turn. In particular, let: $$S_0=\{\text{you},\text{other}\}$$ be the initial bit of information that all prisoners have - they either are you or are not. Any instruction for the first turn is of the form "you (should/shouldn't) turn your light on and others (should/shouldn't) turn their lights on" - that is, we select a subset of $S_0$ and instruct anyone having that information to turn their lights on. In particular, we find out that, until new information is learned, all the prisoners may know is:

• What they knew from $S_0$.

• Whether they saw a light, given a subset of $S_0$ which turned their lights on.

We express this as:

$$S_1=S_0\times \mathbb P(\mathbb P(S_0))$$ where $\times$ is a Cartesian product and $\mathbb P(S)$ is the power set of $S$ and the latter set of the product represents the set of subsets of $S_0$ for which a given prisoner saw a light (assuming all subsets were tried). We may repeat this argument to create the set $$S_{n+1}=S_n\times \mathbb P(\mathbb P(S_n))$$ which is related similarly to $S_n$ as before. Then, our strategy becomes:

Enumerate all subsets of $S_0$, telling prisoners corresponding to each subset to turn their lights on. This sorts prisoners into the subsets given in $S_1$. Enumerate the subsets of $S_1$. Proceed until someone proves that there are exactly $n$ prisoners.

Now, this strategy is not very efficient, given that the size of the $S_n$ grows as fast as tetration. But, it is notable for being universal - meaning that every other strategy is simply this one, where certain days are skipped. Therefore, given that this challenge is possible at all, this strategy works.

For convenience, one may note that for $n=1$ we may see that any prisoner who receives the information (in $S_1$) of: $$(you,A)$$ where $A$ is a set containing $\{you\}$ as an element (meaning you saw a light when you turned yours on and no one else did), then you have proven that $n=1$. I think it goes without saying that the following set from $S_3$ proves that $n=2$**: $$\Bigg(\!\!\bigg(you,\Big\{\!\!\Big\{\!\big(you,\varnothing\big),\big(other,\{\!\{you\}\!\}\!\big)\!\Big\}\!\!\Big\}\bigg),\bigg\{\!\!\bigg\{\!\bigg(\!other,\Big\{\!\Big\{\big(you,\varnothing\big),\big(other,\{\!\{you\}\!\}\big)\Big\}\!\Big\}\bigg)\!\bigg\}\!\!\bigg\}\Bigg).$$ I'm sure the mathematicians will have no trouble figuring this all out - hey, I'm only the guy who provides the strategy, not who interprets its meaning.

(*"Same set" in the sense of "no matter how the warden has acted or what turns have come in between, the same prisoners will act" - which is to say that if we address the same set of prisoners in two different ways so that the sets feasibly could be different but turn out to be the same, then we may gain information)

(**Although no one will ever actually receive the given set; many of the subsets would need to be expanded - but in the partial order generated by the self-referencing relations $(A,B)\geq (A,B')$ if $\forall b'\in B'\exists b\in B\forall a'\in b'\exists a\in b[a'\geq a]$ and $(A,B)\geq (A',B)$ if $A\geq A'$, the given element has the property that all greater elements also provide a proof - this order is essentially ordering $S_n$ by saying $X\geq Y$ whenever $X$ represents more observations of lights than $Y$)

Answer 5

Below is, in my opinion, the cleanest possible presentation of the solution. The method is the same as Gil's other than rewording, but the proof at the end is different. As a fun fact, the process runs for at most $n^2 + 2^n + n^22^{2n}$ steps.

---

First, we demonstrate how all the prisoners can determine an upper bound on their number.

Initially, let $m=1$, and let's say that the leader (i.e. you) is "active," but no one else is. For the next $m$ days, everyone who is active flashes, and every inactive prisoner who gets flashed becomes active. After these $m$ days, between $\min(m+1,n)$ and $2^m$ people are active (since the number of active people at most doubles each day, and as long as not everyone is active, it increases by at least one). Then, for the next $2^m$ days, everyone who is active flashes, and everyone who doesn't get flashed becomes inactive. If there were any inactive people, then at least one person will be deactivated each day. Otherwise, everyone stays active.

At the end of these $m+2^m$ days, everyone is now either active or inactive. In the former case, the prisoners now know $n\le 2^m$. In the latter case, they increment $m$ and try again. They are guaranteed to stop when $m=n-1$.

From now on, assume the prisoners know an upper bound, $B$. Given a subset $S$ of prisoners, where everyone knows whether or not they are in $S$, we know define a process called Signal$(S)$; by the end of this process, everyone will know whether $S$ is nonempty, so that people in $S$ have signaled their presence. Signal$(S)$ lasts for $B$ days. Initially, people in $S$ are "active," and everyone else inactive. Each day, active people flash, and people who are flashed become active. On the last day, everyone either flashed or didn't, according to whether $S$ was nonempty.

Here is the whole algorithm. At any point, the prisoners will be partitioned into some number of (nonempty) sets, $S_1,\dots S_k$, where every prisoner knows which set they are in. Initially, $S_1$ contains only you, and $S_2$ has everyone else.

1. The prisoners find an upper bound, $B$.
2. For every proper, nonempty subset $A$ of $\{1,2,\dots,k\},$
   a. [1 day] All prisoners in $\bigcup_{i\in A}S_i$ flash. Let $F$ be the set of people flashed on this day.
   b. For each $1\le j\le k$,
   $\quad$i. [B days] Signal$(S_j\cap F).$
   $\quad$ii. [B days] Signal$(S_j\setminus F)$.
   $\quad$iii. If both $S_j\cap F$ and $S_j\setminus F$ are nonempty, replace $S_j$ with $S_j\cap F$, increment $k$, and
   $\qquad$ set $S_{k+1}=S_j\setminus F$.
3. If $k$ increased during step 2, repeat step 2. Otherwise, the prisoners stop, and calculate $n$.

The above loop will eventually stop, since $k$ can't be greater than $n$.

But how do they calculate $n$ once this stops? Because the $k$ did not increase, for every set $S_j$, either everyone or no one in $S_j$ was flashed during 2(a). Let $x_{i}$ be the number of people in $S_i$. Also, let $A'$ be the set of $j$ for which $S_j$ was flashed on step 2(a). Note that $A'\setminus A$ must be nonempty; otherwise, everyone in $\bigcup_{i\in A}S_i$ would be flashing themselves, creating a closed loop, contradicting that $A$ was proper (not all of $\{1,\dots,k\})$.

Since the number of people who flashed during 2a) equals the number who were flashed, the prisoners now know that $$\sum_{i\in A}x_i=\sum_{j\in A'}x_j.$$ This means the prisoners know a systems of $2^k-2$ equations about the variables $x_1,x_2,\dots,x_k$. Additionally, they know $x_1=1$. We prove that such a system of equations has a unique positive integer solution. The prisoners proceed to guess this solution by trial and error, and win by announcing that $n=\sum_i x_i$.

Consider a system of equations in unknowns $x_{1},\dots x_k$, where for each nonempty proper subset $A$ of indices, there is another subset $A'$ where $A'\setminus A$ is nonempty, and an equation of the form $\sum_{i\in A} x_i = \sum_{j\in A'} x_j$. This system as at most one positive integer solution where $x_1=1$.

Proof: Let $x_1,\dots,x_k$ and $y_1,\dots,y_k$ be two such solutions. Let $r$ a minimal value of $\frac{y_i}{x_i}$ for all choices of $i$, and let $z_i=y_i-rx_i$. This implies each $z_i$ is nonnegative, at least one $z_i=0$, and that the numbers $z_i$ solve the same equations.

Suppose not all $z_i$ are zero. Let $Z$ be the set of $i$ for which $z_i=0$. Then there would be a set $Z'$ for which $\sum_{i\in Z} z_i = \sum_{j\in Z'} z_j$, and where $Z'\setminus Z$ is nonempty. But every summand on the left is zero, and at least one on the right is positive, so this is a contradiction.

Thus, all $z_i$ are zero, so each $y_i=rx_i$. Since $x_1=y_1=1$, this implies $r=1$, so in fact each $x_i=y_i$, showing any solution is unique.

Answer 6

A bit late to the party, but this question keeps bugging me due to the inefficiencies of the solutions I read... many of the other answers focus on proof of existence. This answer focuses on running time.

I predict that a complete algorithm including the following as its core will have a worst case running time less than of $4.875 * 2^N$ in the limit for any value of N for which it is meaningful. In Big-O notation, that's $O(2^N)$, so not merely polynomial in the exponential, but constant. The exact limit for the presumed worst case for $N \ge 3$ is $4.875 * 2^N - 2(N+1)^2$

The core function in the protocol, and the only one used to control the lights is where a given set (or a subset of a given set who have made a specific observation) announce themselves to "all other prisoners". Each message has a well-defined maximum number of recipients, and lasts for this many days (and not a single day more!). It is not guaranteed that all senders of a message will receive it back, but that is fine, because the senders already have the information being sent.

Phase 1

As with other solutions, the first phase is to establish upper and lower bounds for $N$. This procedure guarantees to complete in $2^N - 1$ days, and not a single day more.

During this phase, we also partition the prisoners into $K$ groups where $K \le N \le 2^K$, based on which round each prisoner discovered a minimum bound for $N$.

Before starting, a single set is defined consisting of "you". This will be referred to as $s_0$ from here on. On each round at least one further set is defined consisting of at least one other prisoner, until there are no more prisoners, at which point everyone is aware of this.

Phase 1, round $J$ (where $1 \le J \le K$) lasts for $2^{J-1}$ days.

Everyone who is not in a numbered set turns on their light.

Everyone takes note of what they saw on the first day of the round.

For those already in a numbered set, this will be communicated to everyone else in phase 2. For those who are NOT in a numbered set, anyone who did not see a light notes that they are a member of $s_J$.

For the remainder of the round (for round 1, this does not happen, as it only lasts a single day), the message is repeated (including being relayed by anyone who saw a light the previous day) until everyone will necessarily have received it. On each day, at least one person who did not see a light the day before will see a light today.

By the last day of the round, either everyone is aware of the existence of a non-empty $s_J$ (everyone sees a light, except a maximum of one person who was already setting their light on day 1 of this round).

If $s_J$ was non-empty, we proceed to the next round of phase 1, taking twice as many days. If $s_J$ was empty, all prisoners have now been allocated to a set, so we proceed to phase 2 immediately.

Phase 1 lasted for $K$ rounds taking in total $2^K - 1$ days, where $K \le N \le 2^{K-1}$

At the end of phase 1, the following common knowledge is known by ALL prisoners:

• the value of $K$
• $s_0$ has precisely 1 member (i.e. ${s_0}_\max = 1$)
• an initial upper bound on the number of members of $s_J$ (where $1 \le J \le K$) as ${s_J}_\max = 2^{J-1}$ (in particular, ${s_1}_\max = 1$)
• the protocol that will be followed going forwards, and in particular
• ${s_J}_\max \le \sum_{i=0}^j {s_i}_\max$ - the number of members of $s_J$ cannot be more than the total of $s_I$ for $0 \le I < J$. All prisoners keep notes about the common knowledge values of ${s_J}_\max$ and update them as new information comes in.
• ${s_J}_\min = 0$ for $J > 1$ (in fact we know the lower bound is at least 1, but where a lower bound is needed, we need to "discover" it one by one)
• $N_\max = \sum_{i=0}^K {s_i}_\max$ - the upper bound on $N$, initially $2^{K-1}$ but updated as new information comes in.
• $N_\min = \sum_{i=0}^K \max({s_i}_min, 1)$ - the lower bound on $N$ - this is initially $K$, but also updated as new information comes in.

Phase 2:

Each round $J$ of phase 2, $1 < J < K$ establishes common knowledge about the size of $s_J$ that was created during phase 1 round $J$.

Phase 2 round 1 lasts for zero days, and only involves "you".

If "you" failed to see a light on day 1. $s_1$ is empty, and you are the only prisoner. If "you" saw a light, you already know that $s_1$ is non-empty, and so does everyone else.

Phase 2 round 2

This uses a different message to the later rounds, as only 1 bit of information is required to determine whether $s_2$ has 1 or 2 members.

If $s_2$ has only 1 member, then whichever of $s_0$ and $s_1$ failed to observe a light on phase 1, round 2, day 1 (overall day 2) sends a message by setting their light.

This message must be repeated for at least $N-1$ days. We do not yet know $N$, but if this message is sent, it will be because $s_2$ has only 1 member, which in turn means that $s_3$ can only have a maximum of 3 members (rather than 4), $s_4$ can only have a maximum of 6 members (rather than 8), etc...

In total, the message would reduce the upper bound of N that is common knowledge by $2^{K-3}$.

The number of days that $s_0$ or $s_1$ turn on their light for this round (and for which anyone who has already seen a light this round repeats it) is thus $2^{K-1} - 2^{K-3} - 1 = 3 * 2^{K-3} - 1$, by which time the message, if sent, will have reached all prisoners.

On receipt of the message, it becomes common knowledge that $s_2$ has 1 member, and the commonly known upper limit is reduced permanently by $2^{K-3}$ - everyone notes down this new upper bound, and uses it in all future calculations.

If the message is NOT received, the upper bound remains the same, but everyone now knows that $s_2$ contains EXACTLY 2 members. Clearly the warden was feeling generous, as reduced the value of $K$, so that reaching this point (enumerating the first 4 members) has taken less than half the amount of time it could have taken.

Phase 2 round $J$ (where $2 < J \le K$)

The main purpose of this round is to define bounds on the size of $s_J$. If no earlier set has more than 2 members, these bounds will be established precisely.

Unlike round 2, or the rounds of phase 1, this will consist of multiple messages defined in the following order:

Each $s_I$, where $0 \le I < J$, is given the opportunity in turn to send a message if they failed to observe a light on the first day of round $J$ of phase 1. For each already-identified person who failed to observe a light, there must be a member of $s_J$ who observed a light that day.

The maximum time for the message to reach all members, if sent, will be $N_\max - 2^{K-J-1} - 1$

After waiting this many days everyone either:

• reduces the upper bound of the number of members in $s_J$ by 1 (message received)
• increases the lower bound of the number of members in $s_J$ by the number of members of $s_I$ (message not received). NB the first such "message not received" confirms the implicit lower bound of 1, so at the start of the round treat the lower bound as though it were zero.

This in turn causes $N_\max$ or $N_\min$ to be updated. Reducing $N_\max$ is, of course, most useful to us, and when it happens it is reduced by $2^{K-J-1}$. Once again, the update, if it occurs, is immediate, and applies to the very next message.

It is not necessary to "ask" $s_J$ or $s_I$ (where $I>J$) if they saw a light on that day, as it is implicit in the definition of the sets - $s_J$ is defined to be the set of those who saw a light on that day but not on any previous relevant day.

After each earlier set has sent (or not) a message, we check again the list of sets. If we received a message from that set, it indicates that at least one member of the set did not see a light, but for any sets with more than one member, we need to know whether they all saw the same thing.

Therefore for each such set where this is not immediately apparent, we wait for a further message indicating whether anyone in that group DID see a light on the relevant day. Receipt of this message does NOT reduce $N_\max$, so unlike the other messages we wait for $N_\max - 1$ days.

If this second message is received, the relevant set, $s_I$ is split into two sets, $s_{I.0}$ and $s_{I.1}$. For all further rounds of phase 2 (or phase 3 if required), they will be treated as two separate sets - we get more messages per round, but each message is more specific. If the original set had at least 3 members, it will not be clear at this point how the original set was split, so we may need to clarify that in phase 3. It would be POSSIBLE (but unlikely if the warden was paying attention) that this could resolve itself later in phase 2 if one or more of the subgroups also get split.

The end of phase 2 occurs in round $K$. If phase 3 is not necessary, the final message, if sent, results in $N_\max = N_\min$. However, the moment the prisoner who would be sending that message receives (or fails to receive) the penultimate message, that prisoner (and that prisoner alone) knows the true value of $N$ for certain, and announces this; also continuing to set the light according to the protocol in case the warden does not react by releasing all prisoners immediately.

It is assumed that the worst case occurs when $K = N$, i.e. when the warden has arranged that each of our sets contains precisely one person. In this case our initial bound $N_\max$ = 2^{N-1}$

Running time of presumed worst case:

The presumed worst case is also the simplest for the warden to arrange - never move any prisoners.

In this case, each round in phase 1 creates a set containing only a single prisoner, taking $2^N - 1$ days in total.

Phase 2 round 2 takes $3 * 2^{N-3} - 1$ days, leaving a $N_\max = 3 * 2^{N-3}$

Phase 2 round $J$ uses $J$ messages which reduce ${s_J}_\max$ from J to 1. During this time, $N_\max$ is reduced as an iterative step from $J * 2^{N-J}$ to $(J+1) * 2^{N-J-1}$.

Observe that $J * 2^{N-J} = 2J * 2^{N-J-1}$

The first and second messages take $(2J - 1) * 2^{N-J-1} - 1$ days to transmit, and the remaining messages each an amount of time that is shorter by $2^{N-J-1}$ days, until the final message at $(J+1) * 2^{N-J-1} - 1$ days.

This gives a formula for days taken for all the messages in round $J$ of

$(J^2 + J(J+1)/2 - 1) * (2^{N-J-1}) - J$

The very final message can be skipped when $J = N - 1$, saving $N - 1$ days that it would otherwise have taken to send that message.

This gives an overall formula for the total running time of

$2^N-1 + 3 * 2^{N-3} -1 + (\sum_{J=3}^{N-1}{((J^2 + J (J + 1)/2 - 1) 2^{N - J - 1} - J}) - (N-1)$

This simplifies to a surprisingly simple-looking formula:

$39 * 2^{N - 3} - 2 (N + 1)^2$

... or to put another way: $2^n * 4.875 - 2{n+1}^2$

... which agrees with the output from a more detailed simulation I performed earlier.

Phase 3.

Details of phase 3 need to be confirmed. Other answers already give techniques by which, given an upper bound on $N$ (which I've termed $N_\max$), and a number of defined sets, we can force one of the sets to be split into two subsets in $O(n^2 * N_\max)$ operations.

Note that in our initial construction, for any set containing more than 1 member, the value of K must be reduced by 1, halving our initial upper bound on $N$, and as such we reach the point where we know for certain that a set contains more than 1 member in a fraction of the time that we could have reached a similar point had those members been split into separate sets within phase 1.

It is not clear at this moment at what point it becomes more efficient to run a round of phase 3. Initially I assume it occurs after phase 2, but for example, suppose we have least 10 prisoners arranged into 8 groups as follows (I'm working with a specific example using excel to save my head exploding!)

$s_0$: 1, $s_1$: 1, $s_2$: 1, $s_3$: 3, $s_4$: 1, $s_5$: 1, $s_6$: 1, $s_7$: 1

First, we know that the presumed worst case for 10 prisoners is 4750 days.

However, because we have only $K$ groups, we start the algorithm with $K = 8$, and the first few stages of the analysis are the same as if $N = 8$.

The first difference occurs in phase 2 round 3, where rather than waiting 79 days for the first 2 messages and a further 63 days for the final message, we wait 79 days for all 3, and do not receive any of them (thus we know that $s_3$ has 3 members). $N_\max$ then remains at its former value of 96, because none of these messages were received.

For round 4, we assume that the warden arranged prisoners so that the person who did see a light was in set $s_3$, (otherwise we would successfully count the member of $s_4$, as group 3 would have been unanimous in stating they did not see a light).

Therefore $s_0$, $s_1$ and $s_2$ will all send messages saying they did not see a light, as will the other 2 members of $s_3$. Those 4 messages take 87, 79, 71, 63 days respectively, leaving us with common knowledge that $10 \le N \le 64$ (or generalising, $K+2 \le N \le 2^{K-2}$). In fact $K = N-2$, so $N_\max$ has already been reduced to $2^{N-4}$.

It is immediately obvious that at least one of the members of $s_3$ must have seen a light, as otherwise $s_4$ would be empty, so we don't bother with a message to confirm that, instead we immediately split s3.

Common knowledge at this point will be:

$s_0$: 1, $s_1$: 1, $s_2$: 1, $s_{3.0} + s_{3.1}$: 3, ${s_4}_\max$: 2, ${s_5}_\max$: 8, ${s_6}_\max$: 16, ${s_7}_\max$: 32

Continuing another round of phase 2 allows the upper bound on s5 to be reduced. As s3 has been split into 2 separately-identifiable sets, we now get 6 messages in round 5 rather than the "normal" 5 messages. All but 1 of these will in fact indicate that the prisoners did not see a light, and the warden will surely not conveniently split $s_{3.0}$ for us (which really contains 2 prisoners although we do not know this yet). These messages take 59 + 59 + 55 + 51 + 47 + 43 days to transmit, (314 days for round 5), resulting in common knowledge that includes the following:

$s_0$: 1, $s_1$: 1, $s_2$: 1, $s_{3.0} + s_{3.1}$: 3, ${s_4}_\max$: 2, ${s_5}_\max$: 3, ${s_6}_\max$: 11, ${s_7}_\max$: 22

In a similar manner, round 6 would have 7 messages totalling 257 days, and round 7 has 8 messages totalling 219 days, leaving a final state if phase 2 is run to completion of:

$s_0$: 1, $s_1$: 1, $s_2$: 1, $s_{3.0} + s_{3.1}$: 3, ${s_4}_\max$: 2, ${s_5}_\max$: 3, ${s_6}_\max$: 5, ${s_7}_\max$: 9

$10 \le N \le 25$

At this point, a total of $1677$ days have elapsed in this specific example, giving $4750 - 1677 = 3073$ days to run a phase 3 algorithm that forces one group to split and still beat the worst case for N=10. As our upper bound on $N$ at this point is only $25$, the maximum time to transmit a single message from one prisoner to all other prisoners is $24$ (and other protocols may well include messages known to be sent by multiple prisoners, or which are not intended to reach all prisoners). This gives (at least in this specific case) a budget of at least $128$ messages without exceeding the upper bound already established.

The improvement in running time decreases exponentially (in fact contrary to the day counting above, the warden needs to ensure that it is a group of uncertain size rather than s0 which confirms the lower bound of 1, so that buys a few irrelevant extra days).

If in fact $N > 10$, and the warden had "hidden" at least one extra prisoner in at least one of the later groups, the analysis so far would be the same, but as $N$ is higher, we have even more time to run a "phase 3" protocol.

In this specific instance, what we would ideally want to do is have s3.0 send a 1 day message, and every set (including $s_{3.0}$) send a message to indicate whether they received that message. This would reveal that $s_{3.0}$ had 2 members, as 2 different sets must have received the message.

The final design of the phase 3 protocol would need to establish more precisely:

• how many more rounds of phase 2 we run before the diminishing effect of the reduction in upper limit makes it more efficient to run a round of the phase 3 protocol next.
• which messages are sent and in what order.
• whether we are in fact able to guarantee that phase 3 does not take more time than the presumed worst case for the same $N$ (NB not the same $K$).
• whether we use "new" messages to force the size of the group to be revealed, or messages that we know were already sent earlier in the protocol.

Because that part is still not fully defined, the worst case is merely presumed, however, the intended elegance of the solution is that the warden cannot make phase 3 "complicated" without exponentially reducing the running time of phases 1 and 2.

Post-script - what about a practical running time?

Even with this relatively low worst case, the worst case running time even for relatively small values of $N$ spirals out of control.

The above protocol could be modified so that if phase 1 round $Z$ indicates that there are still unallocated prisoners, we assume that the upper limit is $2^Z$. (This and following paragraphs were initially written with $Z = 7, 2^Z = 128$). Phase 1 rounds $Z+1$ to $2^Z$ would then be done in just 1 day each, as we no longer check for responses in order to modify the upper bound. Given that all other prisoners would then receive a work sheet with this fixed upper bound built in, they have no choice but to follow the protocol as written if they wish to have any chance of using it to escape alive.

If in fact $N > 2^Z$, prisoners who still see a light at the end of round $2^Z$ would know that the protocol had failed and the procedure was doomed to failure. These prisoners, and any others who receive contradictory messages, should leave their lights off permanently to minimise the risk of the warden arranging for a prisoner to receive a false message.

The main additional change would be that $K$ would be initially unknown, $Z + 1 \le K \le 2^Z$.

Otherwise, the protocol would work pretty much as-is, replacing $N_\max$ with $\min(N_\max, 2^Z)$, and possibly some additional messages used to probe whether a given set exists (the group itself, and anyone else who saw a light on during the day of the group's creation could initially confirm this) once the existence or not of that group starts to have a significant effect on the upper bound in use.

For all values of $N$ that are really up to $2^Z$, this will work correctly, and with the running time greatly reduced to human scales.

However, because phase 1 gets reduced to a constant value for $K \ge 8$, the disincentive for the warden to make "complicated" cases that need lots of work to resolve in phase 3 is greatly diminished even for $N \le 2^Z$.

Although the warden can interfere with which messages are received by at least one prisoner if $N > 2^Z$, so that prisoners get out of synchronisation with the protocol, it will still take multiple years before anyone makes a false declaration (for example declaring that $N = Z$, when in fact it is higher, having been tricked into believing the common knowledge is different to what it really is). It is hoped that this gives the rebel alliance's special forces unit time to overthrow the evil dictator!

However, that latter case is kind-of cheating, and there are possibly more efficient protocols that can be used if we're assuming a fixed upper bound anyway.

Answer 7

Once a bound on the number of prisoners is established, the problem may be solved in polynomial time (rather than hyper-exponential) without requiring prisoners to use an overly-complicated rule sheet, by establishing a protocol where the master initiates queries and other prisoners respond. Time is subdivided into groups of days whose length is the known upper bound on the number of prisoners, and on each group of days either the master will either send a "bit" or expect to receive a bit from the prisoners.

Every group of days on which the master expects to receive a bit of information from the prisoners will be assigned an index number, and the most common type of query will ask slaves to identify the days of the group on which they saw lights. Rather than having the slaves spend 2^N groups of days reporting every possible pattern of light and dark they may have seen, an interactive protocol could limit queries to the days of interest.

To issue such a query, the master will send "10" followed by the number of the group of interest, in binary. After that, each slave will intialize an "initial sequence" to the string "0" and proceed as follows:

1. Get a bit from the master. If "0", go to step 4
2. Output a "1" if the initial sequence of light/dark seen on that day matches the string. If didn't output a "1", and no "1" is seen, proceed to step 4.
3. Append a "0" to the string and go to step 1.
4. If the string contains any zeroes, strike all trailing "1"'s and replace the last "0" with a "1" and go to step 1.
5. This query is done; await next query from the master.

Using this query approach, the master will be able to acquire all the information that could have been acquired by having slaves blindly broadcast information about everything they'd heard, but the amount of time will be reduced enormously. If no information about the maximum number of prisoners is available I know of no mechanism to avoid having the time requirement be exponential with respect to the actual number of prisoners (since the time required for a broadcast to reach N prisoners can vary anywhere from lgN to N) but this protocol would still serve to reduce the total time requirement from being hyper-exponential to being simple exponential.

I'm not sure if it would be possible to reduce the worst-case time below O(2^N), but perhaps there is some technique where it could be done. The earlier-described technique of establishing the upper bound on the number of prisoners only establishes it as being between N and 2^N, which implies that one might take time 2^N to find out there are N prisoners, but it might be possible to find out more information with each length of "cleanup sequence" before one starts using cleanup sequences that are twice as long.