100 prisoners and a secret number

Question

There are 100 prisoners numbered from 1 to 100. They know their own numbers. There is an interrogation room with a table and an envelope. The envelope contains a secret number - an integer chosen between 1 and 100, inclusive. On the $k$-th day the following happens:

1. The prisoner numbered $k$ is led into the interrogation room and asked to guess the number in the envelope.
2. If they are correct then they and all the remaining prisoners are released.
3. If they are wrong then they are allowed to open the envelope, see the secret number and place it back in the envelope. Then they are shot.

The prisoners are allowed to come up with a strategy before the 1st day. Upon seeing the number (in step 3) they agree to place the envelope in one of two states (facing up or facing down) as a means to communicate with the next prisoner to enter the room. They have no other means to communicate or hear what earlier prisoners have guessed.

What is the most number of prisoners that can be guaranteed to be saved in the worst case scenario?

Answer 1

Probably not optimal, but here's an approach that saves at least

50 prisoners. Prisoners 2-50 agree to guess 2(k-1) or 2k-1, prisoner 1 will guess 1, and prisoner 51 will guess 100. No one else will need to guess.

When someone guesses wrong, they leave the envelope face up if the number is odd, or face down if it's even. Then everyone guesses whichever of their numbers is possible based on envelope orientation. Prisoner 1 has no extra info, and by prisoner 51, there's only one possibility left, so if it comes to them they guess right.

Answer 2

@StephenTG's answer is the best. Here's a proof:

Since there are 100 possible numbers, they must encode into 100 "states".

The first prisoner can encode only one state since his view of the envelope carries no meaningful significance. Then for every following prisoner, the side of the envelope provides two ways to encode a state. Therefore the first 50 prisoners can encode at most 99 states. When the 51st prisoner enters, there's only one state left so we can confidently know it's the last state and make the guess.

In other words,

A state can be represented by a tuple (# of prisoners already shot, side of envelope)

Answer 3

99 prisoners: The way to transmit more than one bit of information from the placement of the envelope and paper comes from a legalistic interpretation of the rule:

If they are wrong then they are allowed to... a) open the envelope, b) see the secret number and c) place it back in the envelope. Then they are shot. ... They have no other means to communicate.

Obviously they would a) open the envelope and b) see the secret number. But as written, these rules say they could choose not to do c) place it back in the envelope. Hence, they could place the secret number back on top of the envelope (face down or face face up), or beside it, at various orientations.

(Now if they could place the secret number face-up, then the solution is trivial, only prisoner 1 has to guess, prisoner 2 can see it before they guess, or before opening the (now-empty) envelope. So worst-case 99, expected 99.01. But that's trivial and renders the enveope obsolete, so let's exclude it.)

But here's the innovation: if they can place the number face-down, that opens up multiple possibilities for signalling information:

O, the orientation of the paper wrt envelope. There can be at least 8 orientations (from north to northwest). That's 3 extra bits of information.

D, the distance of the (nearest point of the) paper from the envelope (from overlapping to one inch to two inches to four inches to six inches to one foot to two feet to three feet to six feet). We can get another 4 extra bits of information, or more, from that.

R: the rotation of the paper. Even if the paper was square, we can still get 1 bit from this. If it's rectangular we could get 2 bits.

So there's 7+ bits of information, enough to fully encode the number for prisoner 2. (They can decide the bit protocol beforehand).

Hence worst-case is 99 saved, and expected is 99.01 if prisoner 1 guesses randomly. Curiously, this is the same as if they are allowed to place the secret number face-up. Either way, the secret number can be fully knowable for prisoner 2.

(Sucks to be prisoner 1, who only has 1% chance, while everyone else is guaranteed to survive... maybe they would start a fight to change their shirt number. Or change it to make it look like '7' or '11', so that noone owned up to being prisoner 1. But we digress.)

Answer 4

Just some remarks I wanted to make.

In StephenTG's solution, it is actually unnecessary for the first prisoner to make a guess; he merely needs to put the envelope in the right state, and then $50$ prisoners will be guaranteed to be saved. If prisoner $1$ instead guesses $1$ or $2$ randomly, then an expected number of $50.5$ prisoners will be saved.

So a natural question is how well can the prisoners do if they are allowed randomness. To be more precise, the secret number is chosen adversarially (worst-case) based on the prisoners' random strategy but before the randomness is instantiated. The goal is to maximize the expected number of prisoners saved.

I can achieve an expected number of $75$ prisoners saved. Solution below. Can you do better?

Let $g_1$, the guess of prisoner $1$ be uniformly distributed over $\{1,2,\dots,100\}$. Let $g_2^{+},\dots,g_{49}^+$ be a random permutation of $\{n \le 100 : n \equiv g_1 \pmod{2}\} \setminus \{g_1\}$, and $g_2^-,\dots,g_{50}^-$ be a random permutation of $\{n \le 100 : n \not \equiv g_1 \pmod{2}\}$. Have $g_1$ put the envelope up if the true number is even, and odd otherwise. Then have prisoner $j$ guess $g_j^+$ or $g_j^-$ based on the position of the envelope (with no prisoner after the first changing the position of the envelope). Clearly all numbers $n \in \{1,\dots,100\}$ are equally worst-case for this prisoners' strategy. And for any $n$, a quick calculation shows that the expected number of prisoners that survive is $75$.

Answer 5

I have a different way of getting the same amount of prisoners as @StephenTG:

$50$

Here's the strategy:

Each prisoner guesses their own number by default, unless the envelope is facing up. An incorrect prisoner $k$ will place the envelope facing up only if the correct number is $101 - k$. A prisoner who sees an upwards-facing envelope will then know the correct number, as they are $k+1$.

Here's why it works:

If the number is $50$ or below, then no prisoner will see an upward-facing envelope, so they will all guess their own number, and one of the first $50$ will get it, saving at least $51$ prisoners. If the number is $51$ or above, then it can be written as $101 - k$ for some $k \leq 50$, so one of the first $50$ will place their envelope facing up, thus one of the first $51$ will get it, saving at least $50$ prisoners.

Answer 6

(I'm generalizing the question here, and substituting 100 by $N$)

Claim:

The solution proposed by @StephenTG is one of the best solutions both in the worst case scenario and on average. It is also one of the best solutions for any other number of prisoners.\

@iBug 's answer explains:

why, from the placement of the envelope, we can only deduce the yes/no answer to one question only. Basically, his answer is saying that no matter what strat we are using, the only useful information that any prisoner has is their number (i.e., how many have died before them) and the position of the envelope, the reason being that these two are the only factors that are actually affected by the actual number in the envelope that a prisoner is able and allowed to know.\

Therefore, let's consider a criterion $A$. Then, for any number-in-envelope, it either satisfies or doesn't satisfy $A$.

As the answer is chosen completely at random, we can analyze matters probabilistically. Assume $P(A)=P(\text{the number satisfies $A$})=p$. Thus, there are $pN$ numbers that satisfies $A$. Since the information that the envelope can convey is just if the number-in-envelope satisfies $A$, to find the exact value, the prisoners will have to guess every element. Hence, in the worst case, the number of prisoners sacrificed will be $\max(pN,(1-p)N)$. Thus, the most optimal strat in terms of the worst case scenario is when $max(p,1-p)$ is the smallest, which is clearly when $p=0.5$.

Now let's think about the expected number of sacrificed prisoners. First, consider the following scenario: if we know that there are $x$ possible answers, what is the expected number of times that we need to guess before we get the correct answer? The answer is $\dfrac{x+1}{2}$, the average of the least and most number of times you will have to guess. Then, if we know the number-in-envelope satisfies $A$, then we would have to guess $\dfrac{pN+1}{2}$ times on average. Similarly, if the number-in-envelope doesn't satisfy $A$, then we would have to guess $\dfrac{(1-p)N+1}{2}$ times on average. From this, we can deduce (by the formula of expectation), that the expected number of times one would need to guess is $$E=p\cdot\dfrac{pN+1}{2}+(1-p)\cdot\dfrac{(1-p)N+1}{2},$$which, after some simplification, equals $$0.5N\cdot(p^2+(1-p)^2)+0.5.$$ By expanding and completeing the square, we have $$E=N((p-0.5)^2+0.25)+0.5.$$ As the square is always positive, the minimum expected number of guesses (i.e., the minimal number of prisoners sacrificed) is achieved when $p=0.5$, and is $$E_\text{min}=0.25N+0.5.$$ In our case, $N=100$, so $E_\text{min}=25.5.$

Conclusion:

We have proved that the optimal strat ensures that P(A)=0.5. In other words, any strat that ensures that exactly half of the possible numbers-in-envelope satisfies $A$ is optimal.

Answer 7

25 Prisonners. They decide the 1st prisoner will guess 50 to instantly half their chances, leaving the envelope face up if its greater and face down if its less.

They then continue to guess down by 2's (48,46,44,etc.), leaving the envelope face down to indicate it is less until it is the number above in which case it will be face up. At that point the prisoner will be able to guess the correct number.

50-2(x-1) if face down, 50-2(x-1)+3 if face up, so if you are prisoner 12 and see a face down envelope you guess 28, if face up you know its 31. At most it would get to prisoner 26 who's only guesses would be 1 if face down, or 3 if face up.

Answer 8

So they were having time to make strategies so my strategy would be that the first prisoner who will go will tell any no. If number is correct by luck it's good otherwise he will see the number if number is greater then 50 he will leave envelope facing upwards else downwards the same process other prisoner will repeat till one no. Is left during this process nearly 7 prisoner will be put to death and rest will be safe

Answer 9

In worst case scenario 94 prisoners can be saved

We just need to use k/2 formula,

In case of 100 if the number is less than 50 then envelope is down and if more than 50 then envelope is up

If less than 50 then divide into two parts 25-25 and in case of odd numbers i.e. 25 choose the even one i.e. 12

And so on...