A bit late to the get together, however this query retains bugging me as a result of inefficiencies of the options I learn… most of the different solutions deal with proof of existence. This reply focuses on operating time.
I predict {that a} full algorithm together with the next as its core can have a worst case operating time lower than of $4.875 * 2^N$ within the restrict for any worth of N for which it’s significant. In Big-O notation, that is $O(2^N)$, so not merely polynomial within the exponential, however fixed. The actual restrict for the presumed worst case for $N ge 3$ is $4.875 * 2^N – 2(N+1)^2$
The core operate within the protocol, and the one one used to regulate the lights is the place a given set (or a subset of a given set who’ve made a particular commentary) announce themselves to “all different prisoners”. Each message has a well-defined most variety of recipients, and lasts for this many days (and never a single day extra!). It will not be assured that each one senders of a message will obtain it again, however that’s superb, as a result of the senders have already got the data being despatched.
Phase 1
As with different options, the primary part is to determine higher and decrease bounds for $N$. This process ensures to finish in $2^N – 1$ days, and never a single day extra.
During this part, we additionally partition the prisoners into $Okay$ teams the place $Okay le N le 2^Okay$, based mostly on which spherical every prisoner found a minimal certain for $N$.
Before beginning, a single set is outlined consisting of “you”. This shall be known as $s_0$ from right here on. On every spherical not less than one additional set is outlined consisting of not less than one different prisoner, till there are not any extra prisoners, at which level everyone seems to be conscious of this.
Phase 1, spherical $J$ (the place $1 le J le Okay$) lasts for $2^{J-1}$ days.
Everyone who will not be in a numbered set activates their mild.
Everyone takes notice of what they noticed on the primary day of the spherical.
For these already in a numbered set, this shall be communicated to everybody else in part 2.
For those that are NOT in a numbered set, anybody who didn’t see a lightweight notes that they’re a member of $s_J$.
For the rest of the spherical (for spherical 1, this doesn’t occur, because it solely lasts a single day), the message is repeated (together with being relayed by anybody who noticed a lightweight yesterday) till everybody will essentially have obtained it. On every day, not less than one one that didn’t see a lightweight the day earlier than will see a lightweight right this moment.
By the final day of the spherical, both everyone seems to be conscious of the existence of a non-empty $s_J$ (everybody sees a lightweight, besides a most of 1 one that was already setting their mild on day 1 of this spherical).
If $s_J$ was non-empty, we proceed to the subsequent spherical of part 1, taking twice as many days.
If $s_J$ was empty, all prisoners have now been allotted to a set, so we proceed to part 2 instantly.
Phase 1 lasted for $Okay$ rounds taking in complete $2^Okay – 1$ days, the place $Okay le N le 2^{Okay-1}$
At the top of part 1, the next widespread information is thought by ALL prisoners:
- the worth of $Okay$
- $s_0$ has exactly 1 member (i.e. ${s_0}_max = 1$)
- an preliminary higher certain on the variety of members of $s_J$ (the place $1 le J le Okay$) as ${s_J}_max = 2^{J-1}$ (particularly, ${s_1}_max = 1$)
- the protocol that shall be adopted going forwards, and particularly
- ${s_J}_max le sum_{i=0}^j {s_i}_max$ – the variety of members of $s_J$ can’t be greater than the full of $s_I$ for $0 le I < J$. All prisoners maintain notes in regards to the widespread information values of ${s_J}_max$ and replace them as new info is available in.
- ${s_J}_min = 0$ for $J > 1$ (actually we all know the decrease certain is not less than 1, however the place a decrease certain is required, we have to “uncover” it one after the other)
- $N_max = sum_{i=0}^Okay {s_i}_max$ – the higher certain on $N$, initially $2^{Okay-1}$ however up to date as new info is available in.
- $N_min = sum_{i=0}^Okay max({s_i}_min, 1)$ – the decrease certain on $N$ – that is initially $Okay$, but in addition up to date as new info is available in.
Phase 2:
Each spherical $J$ of part 2, $1 < J < Okay$ establishes widespread information in regards to the measurement of $s_J$ that was created throughout part 1 spherical $J$.
Phase 2 spherical 1 lasts for zero days, and solely entails “you”.
If “you” did not see a lightweight on day 1. $s_1$ is empty, and you’re the solely prisoner.
If “you” noticed a lightweight, you already know that $s_1$ is non-empty, and so does everybody else.
Phase 2 spherical 2
This makes use of a unique message to the later rounds, as just one bit of knowledge is required to find out whether or not $s_2$ has 1 or 2 members.
If $s_2$ has just one member, then whichever of $s_0$ and $s_1$ failed to watch a lightweight on part 1, spherical 2, day 1 (general day 2) sends a message by setting their mild.
This message should be repeated for not less than $N-1$ days. We don’t but know $N$, but when this message is distributed, will probably be as a result of $s_2$ has just one member, which in flip signifies that $s_3$ can solely have a most of three members (somewhat than 4), $s_4$ can solely have a most of 6 members (somewhat than 8), and so forth…
In complete, the message would scale back the higher certain of N that’s widespread information by $2^{Okay-3}$.
The variety of days that $s_0$ or $s_1$ activate their mild for this spherical (and for which anybody who has already seen a lightweight this spherical repeats it) is thus $2^{Okay-1} – 2^{Okay-3} – 1 = 3 * 2^{Okay-3} – 1$, by which era the message, if despatched, can have reached all prisoners.
On receipt of the message, it turns into widespread information that $s_2$ has 1 member, and the generally recognized higher restrict is lowered completely by $2^{Okay-3}$ – everybody notes down this new higher certain, and makes use of it in all future calculations.
If the message is NOT obtained, the higher certain stays the identical, however everybody now is aware of that $s_2$ comprises EXACTLY 2 members. Clearly the warden was feeling beneficiant, as lowered the worth of $Okay$, in order that reaching this level (enumerating the primary 4 members) has taken lower than half the period of time it may have taken.
Phase 2 spherical $J$ (the place $2 < J le Okay$)
The important objective of this spherical is to outline bounds on the scale of $s_J$. If no earlier set has greater than 2 members, these bounds shall be established exactly.
Unlike spherical 2, or the rounds of part 1, it will include a number of messages outlined within the following order:
Each $s_I$, the place $0 le I < J$, is given the chance in flip to ship a message in the event that they failed to watch a lightweight on the primary day of spherical $J$ of part 1. For every already-identified one that failed to watch a lightweight, there should be a member of $s_J$ who noticed a lightweight that day.
The most time for the message to succeed in all members, if despatched, shall be $N_max – 2^{Okay-J-1} – 1$
After ready this many days everybody both:
- reduces the higher certain of the variety of members in $s_J$ by 1 (message obtained)
- will increase the decrease certain of the variety of members in $s_J$ by the variety of members of $s_I$ (message not obtained). NB the primary such “message not obtained” confirms the implicit decrease certain of 1, so initially of the spherical deal with the decrease certain as if it have been zero.
This in flip causes $N_max$ or $N_min$ to be up to date. Reducing $N_max$ is, in fact, most helpful to us, and when it occurs it’s lowered by $2^{Okay-J-1}$. Once once more, the replace, if it happens, is rapid, and applies to the very subsequent message.
It will not be essential to “ask” $s_J$ or $s_I$ (the place $I>J$) in the event that they noticed a lightweight on that day, as it’s implicit within the definition of the units – $s_J$ is outlined to be the set of those that noticed a lightweight on that day however not on any earlier related day.
After every earlier set has despatched (or not) a message, we examine once more the listing of units. If we obtained a message from that set, it signifies that not less than one member of the set didn’t see a lightweight, however for any units with multiple member, we have to know whether or not they all noticed the identical factor.
Therefore for every such set the place this isn’t instantly obvious, we await an additional message indicating whether or not anybody in that group DID see a lightweight on the related day. Receipt of this message does NOT scale back $N_max$, so not like the opposite messages we await $N_max – 1$ days.
If this second message is obtained, the related set, $s_I$ is break up into two units, $s_{I.0}$ and $s_{I.1}$. For all additional rounds of part 2 (or part 3 if required), they are going to be handled as two separate units – we get extra messages per spherical, however every message is extra particular. If the unique set had not less than 3 members, it is not going to be clear at this level how the unique set was break up, so we might have to make clear that in part 3. It could be POSSIBLE (however unlikely if the warden was paying consideration) that this might resolve itself later in part 2 if a number of of the subgroups additionally get break up.
The finish of part 2 happens in spherical $Okay$. If part 3 will not be vital, the ultimate message, if despatched, leads to $N_max = N_min$. However, the second the prisoner who could be sending that message receives (or fails to obtain) the penultimate message, that prisoner (and that prisoner alone) is aware of the true worth of $N$ for sure, and pronounces this; additionally persevering with to set the sunshine in line with the protocol in case the warden doesn’t react by releasing all prisoners instantly.
It is assumed that the worst case happens when $Okay = N$, i.e. when the warden has organized that every of our units comprises exactly one individual. In this case our preliminary certain $N_max$ = 2^{N-1}$
Running time of presumed worst case:
The presumed worst case can be the best for the warden to rearrange – by no means transfer any prisoners.
In this case, every spherical in part 1 creates a set containing solely a single prisoner, taking $2^N – 1$ days in complete.
Phase 2 spherical 2 takes $3 * 2^{N-3} – 1$ days, leaving a $N_max = 3 * 2^{N-3}$
Phase 2 spherical $J$ makes use of $J$ messages which scale back ${s_J}_max$ from J to 1. During this time, $N_max$ is lowered 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 every an period of time that’s shorter by $2^{N-J-1}$ days, till the ultimate message at $(J+1) * 2^{N-J-1} – 1$ days.
This offers a components for days taken for all of the messages in spherical $J$ of
$(J^2 + J(J+1)/2 – 1) * (2^{N-J-1}) – J$
The very last message may be skipped when $J = N – 1$, saving $N – 1$ days that it might in any other case have taken to ship that message.
This offers an general components for the full operating 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 components:
$39 * 2^{N – 3} – 2 (N + 1)^2$
… or to place one other means:
$2^n * 4.875 – 2{n+1}^2$
… which agrees with the output from a extra detailed simulation I carried out earlier.
Phase 3.
Details of part 3 have to be confirmed. Other solutions already give methods by which, given an higher certain on $N$ (which I’ve termed $N_max$), and quite a few outlined units, we are able to drive one of many units to be break up into two subsets in $O(n^2 * N_max)$ operations.
Note that in our preliminary development, for any set containing greater than 1 member, the worth of Okay should be lowered by 1, halving our preliminary higher certain on $N$, and as such we attain the purpose the place we all know for sure {that a} set comprises greater than 1 member in a fraction of the time that we may have reached an analogous level had these members been break up into separate units inside part 1.
It will not be clear at this second at what level it turns into extra environment friendly to run a spherical of part 3. Initially I assume it happens after part 2, however for instance, suppose we have now least 10 prisoners organized into 8 teams as follows (I’m working with a particular instance utilizing excel to avoid wasting 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 all know that the presumed worst case for 10 prisoners is 4750 days.
However, as a result of we have now solely $Okay$ teams, we begin the algorithm with $Okay = 8$, and the primary few levels of the evaluation are the identical as if $N = 8$.
The first distinction happens in part 2 spherical 3, the place somewhat than ready 79 days for the primary 2 messages and an additional 63 days for the ultimate message, we wait 79 days for all 3, and don’t obtain any of them (thus we all know that $s_3$ has 3 members). $N_max$ then stays at its former worth of 96, as a result of none of those messages have been obtained.
For spherical 4, we assume that the warden organized prisoners in order that the one who did see a lightweight was in set $s_3$, (in any other case we might efficiently rely the member of $s_4$, as group 3 would have been unanimous in stating they didn’t see a lightweight).
Therefore $s_0$, $s_1$ and $s_2$ will all ship messages saying they didn’t see a lightweight, as will the opposite 2 members of $s_3$. Those 4 messages take 87, 79, 71, 63 days respectively, leaving us with widespread information that $10 le N le 64$ (or generalising, $Okay+2 le N le 2^{Okay-2}$). In truth $Okay = N-2$, so $N_max$ has already been lowered to $2^{N-4}$.
It is instantly apparent that not less than one of many members of $s_3$ should have seen a lightweight, as in any other case $s_4$ could be empty, so we do not hassle with a message to verify that, as an alternative we instantly break up s3.
Common information at this level shall 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 one other spherical of part 2 permits the higher certain on s5 to be lowered. As s3 has been break up into 2 separately-identifiable units, we now get 6 messages in spherical 5 somewhat than the “regular” 5 messages. All however 1 of those will actually point out that the prisoners didn’t see a lightweight, and the warden will certainly not conveniently break up $s_{3.0}$ for us (which actually comprises 2 prisoners though we have no idea this but). These messages take 59 + 59 + 55 + 51 + 47 + 43 days to transmit, (314 days for spherical 5), leading to widespread information that features the next:
$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 an analogous method, spherical 6 would have 7 messages totalling 257 days, and spherical 7 has 8 messages totalling 219 days, leaving a last state if part 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 level, a complete of $1677$ days have elapsed on this particular instance, giving $4750 – 1677 = 3073$ days to run a part 3 algorithm that forces one group to separate and nonetheless beat the worst case for N=10. As our higher certain on $N$ at this level is just $25$, the utmost time to transmit a single message from one prisoner to all different prisoners is $24$ (and different protocols might properly embody messages recognized to be despatched by a number of prisoners, or which aren’t meant to succeed in all prisoners). This offers (not less than on this particular case) a price range of not less than $128$ messages with out exceeding the higher certain already established.
The enchancment in operating time decreases exponentially (actually opposite to the day counting above, the warden wants to make sure that it’s a group of unsure measurement somewhat than s0 which confirms the decrease certain of 1, in order that buys a couple of irrelevant further days).
If actually $N > 10$, and the warden had “hidden” not less than one further prisoner in not less than one of many later teams, the evaluation up to now could be the identical, however as $N$ is increased, we have now much more time to run a “part 3” protocol.
In this particular occasion, what we might ideally need to do is have s3.0 ship a 1 day message, and each set (together with $s_{3.0}$) ship a message to point whether or not they obtained that message. This would reveal that $s_{3.0}$ had 2 members, as 2 totally different units should have obtained the message.
The last design of the part 3 protocol would want to determine extra exactly:
- what number of extra rounds of part 2 we run earlier than the diminishing impact of the discount in higher restrict makes it extra environment friendly to run a spherical of the part 3 protocol subsequent.
- which messages are despatched and in what order.
- whether or not we’re actually capable of assure that part 3 doesn’t take extra time than the presumed worst case for a similar $N$ (NB not the identical $Okay$).
- whether or not we use “new” messages to drive the scale of the group to be revealed, or messages that we all know have been already despatched earlier within the protocol.
Because that half continues to be not absolutely outlined, the worst case is merely presumed, nevertheless, the meant magnificence of the answer is that the warden can not make part 3 “sophisticated” with out exponentially lowering the operating time of phases 1 and a pair of.
Post-script – what a couple of sensible operating time?
Even with this comparatively low worst case, the worst case operating time even for comparatively small values of $N$ spirals uncontrolled.
The above protocol could possibly be modified in order that if part 1 spherical $Z$ signifies that there are nonetheless unallocated prisoners, we assume that the higher restrict is $2^Z$. (This and following paragraphs have been initially written with $Z = 7, 2^Z = 128$). Phase 1 rounds $Z+1$ to $2^Z$ would then be accomplished in simply 1 day every, as we not examine for responses so as to modify the higher certain. Given that each one different prisoners would then obtain a piece sheet with this fastened higher certain in-built, they don’t have any selection however to comply with the protocol as written in the event that they want to have any likelihood of utilizing it to flee alive.
If actually $N > 2^Z$, prisoners who nonetheless see a lightweight on the finish of spherical $2^Z$ would know that the protocol had failed and the process was doomed to failure. These prisoners, and any others who obtain contradictory messages, ought to go away their lights off completely to minimise the danger of the warden arranging for a prisoner to obtain a false message.
The important extra change could be that $Okay$ could be initially unknown, $Z + 1 le Okay le 2^Z$.
Otherwise, the protocol would work just about as-is, changing $N_max$ with $min(N_max, 2^Z)$, and presumably some extra messages used to probe whether or not a given set exists (the group itself, and anybody else who noticed a lightweight on throughout the day of the group’s creation may initially verify this) as soon as the existence or not of that group begins to have a major impact on the higher certain in use.
For all values of $N$ which might be actually as much as $2^Z$, it will work accurately, and with the operating time vastly lowered to human scales.
However, as a result of part 1 will get lowered to a relentless worth for $Okay ge 8$, the disincentive for the warden to make “sophisticated” instances that want numerous work to resolve in part 3 is vastly diminished even for $N le 2^Z$.
Although the warden can intervene with which messages are obtained by not less than one prisoner if $N > 2^Z$, in order that prisoners get out of synchronisation with the protocol, it should nonetheless take a number of years earlier than anybody makes a false declaration (for instance declaring that $N = Z$, when actually it’s increased, having been tricked into believing the widespread information is totally different to what it truly is). It is hoped that this provides the insurgent alliance’s particular forces unit time to overthrow the evil dictator!
However, that latter case is kind-of dishonest, and there are likely extra environment friendly protocols that can be utilized if we’re assuming a set higher certain anyway.
