1
$\begingroup$

Is there a 100% guarantee winning strategy to the "100 prisoner problem discussed" here, here, and here?

Basically there's a room with a light bulb and a switch, and 100 prisoners are called one at a time randomly (possibly many times for any particular prisoner), and they look at the light bulb and decide whether to flip the switch. The prisoners can talk before anyone has been called but can't communicate ever after that. Is any prisoner shouts "YAY!" while in the room and all prisoners have been to the room, they are released, otherwise all executed.

Just to make the constraints more clear,

1) the room starts with the light bulb turned off, the prisoners know this

2) the prisoners don't know who's picked at any time

3) at any particular time, all the information that's available to a prisoner is the strategy discussed beforehand with fellow inmates, the whether the light bulb is on or off (if he/she's in the room, otherwise they don't know), and the information they have possibly computed with all the other information they have so far.

4) for the sake of this problem, lets assume everyone is picked at least once

I believe all the solutions discussed in the links provided don't guarantee a win (sorry if I missed a solution that actually guarantees a win). They merely give a very small percentage of failure as time progresses. For instance, one of the solutions is to pick someone as the counter, and only he can turn the light off, and if anyone that's new in the room and hasn't turned the light on yet (and if the light is off), he turns it on. The counter later turns the light off and add 1 to his count (starts count at 0), until he's reached 99. This requires the counter to be picked 100 times at least, yet there's no way to tell any particular person will be picked at least 100 times.

$\endgroup$
1
$\begingroup$

As @MikeEarnest wrote, the usual rules of the game mean everyone will be called infinitely often (with prob $1$), and then the details of the random model / adversarial behavior of the jailer will merely affect the finish time of the algorithm.

Instead, you're asking if the problem can be solved assuming some prisoner only appears a finite no. of times, right? I think the answer is No. First, lets be more precise.

  • Let $P = \{1, 2, \dots, 100\}$ denote the prisoners.

  • Let $x_t \in P$ be the prisoner called on day $t$.

  • Let $X_t = \{x_n: n \le t\}$ be the set of prisoners who has been called (at least once) by day $t$.

  • Define an infinite sequence $X = (x_1, x_2, \dots)$ to be legal by your rules if there exists $T \in \mathbb{N}$ s.t. by day $T$ everyone has appeared at least once, i.e. $X_T = P$.

Then, to solve your version of the problem means to have some deterministic distributed algorithm $A$ s.t. for any legal sequence $X$ as input, the prisoners go free at a finite time $T'(X)$. It is allowed that $T'$ be a function of $X$ (i.e. of $T$, or any other aspect of $X$).

Here is one key point: if algorithm $A$ must work for any legal input $X$, that means an adversary can first look at $A$, then decide on $X$, and $A$ must still work.

It probably takes a lot of work to formalize an algorithm, so I will (sadly) keep that part vague. Subject to that caveat, here is proof that an algorithm (that works for any legal input) cannot exist.

I will prove that an "easier" version of this problem is still unsolvable: the jailer told all the prisoners, truthfully, that a specific prisoner S (for Spartacus!) will be called infinitely often (each of the others will still be called at least once, i.e. $X$ is legal).

Now suppose S first get called at $t=1000$. He can see the lightbulb on or off.

Case $1$: everyone has been called already, i.e. $X_{1000} = P$. Without loss of generality, lets say for such an input the lightbulb will be on at $t=1000$. (How the others contrive it, I don't know, but lets assume they can do it.)

In this case S must eventually call for freedom, say at time $T'$, which is a constant hard-coded into the algorithm for this class of inputs, because otherwise the algorithm would fail for the legal input where $\forall t > 1000: x_t = S$ i.e. he will be called every day from now on.

So we have established that:

  • If S gets called first on $t=1000$, sees the lightbulb on, and gets called from $t=1001$ to $T'$, then he calls for freedom on day $T'$.

This immediately also means, if $X_{1000} \neq P$, the lightbulb needs to be off. (Again, how the others contrive it, I have no idea.) Because if the lightbulb were on while $X_{1000} \neq P$, then for the legal input where S gets called between $t=1001$ to $T'$ while all remaining prisoners get called beyond $T'$, S would erroneously call for freedom on $T'$.

Case $2$: $X_{1000} \neq P$ and prisoner $V \notin X_{1000}$ i.e. V (for Valjean) has not yet been called.

We have established that in Case $2$, S sees the lightbulb off at $t=1000$. Lets say he leaves the lightbulb in state $E \in \{on, off\}$. Now lets construct the rest of $X$: lets say $x_{1001} = V$ and $x_{1002} = S$, at which time S can see the lightbulb in state $F \in \{on, off\}$. With this extra bit he needs to distinguish between these cases:

Case $2.1$: $X_{1001} = P$, i.e. V, the new guy, is also the last guy and now everyone has been called.

Case $2.2$: $X_{1001} \neq P$, i.e. V, the new guy, is not the last guy and someone is still not called.

In 2.1, S needs to call for freedom at some fixed time $T''$ (for the algorithm to work in case the legal input is s.t. he gets called forever from now on) whereas in 2.2, S must not call for freedom at $T''$ (even if he gets called between $t=1002$ to $T''$). That's why S needs to distinguish 2.1 vs 2.2, and he can only do so based on the bulb status $F$ when he sees it again at $t=1002$.

However, as far as V is concerned, he has never been called until $t=1001$, he sees the bulb in state $E$, and he has no idea if the legal input so far is case 2.1 or 2.2. So in a deterministic algorithm he must make the same choice for what to do with the bulb and leave it in the same state $F$ for both 2.1 and 2.2. Therefore, S cannot distinguish between 2.1 and 2.2. I.e. no matter how the algorithm is designed, S must either do the wrong thing in case 2.1 (never calls for freedom) or in case 2.2 (calls for freedom erroneously).

In conclusion: no deterministic algorithm can work for all legal inputs.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.