31
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ I came up with this puzzle myself. I have a decent solution, but I am not sure that it is optimal. I am looking forward to your solutions! $\endgroup$ Jul 15 at 13:56
  • 1
    $\begingroup$ So the prisoners communicate through whether the envelope is face up or face down on the table, which the next prisoner can see before he has to make a guess? At first I read it as if they were putting the secret number face up or face down in the envelope, but that could not possibly be of any use to the next prisoner given that they have to make a guess before seeing that. $\endgroup$ Jul 15 at 14:14
  • 2
    $\begingroup$ Nice problem! (if a bit gory) $\endgroup$
    – justhalf
    Jul 15 at 15:15
  • $\begingroup$ @JaapScherphuis Thought the same. "Reality-wise" the number staying untouched inside the envelope seems much more feasible than the whole envelope staying untouched on the table. $\endgroup$
    – MaxD
    Jul 16 at 4:26
  • $\begingroup$ This problem is very similar to this (but not the same) : math.stackexchange.com/questions/116340/… $\endgroup$
    – vsz
    Jul 16 at 6:30
19
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Well done! This is essentially the solution I had in mind. In fact only the first prisoner needs to place the envelope. The others don't even need to touch it. There is also a similar solution using a different property of the secret number. Now can we save any more prisoners? $\endgroup$ Jul 16 at 0:55
  • $\begingroup$ Could you eliminate this by half again (or twice?) by agreeing on which side of the envelope will be closest to the door? $\endgroup$
    – jlars62
    Jul 16 at 23:09
  • $\begingroup$ @jlars62 in reality you could do that, but in this puzzle they can only communicate by placing the envelope facing up or down. $\endgroup$ Jul 16 at 23:54
8
$\begingroup$

@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)

$\endgroup$
8
  • 1
    $\begingroup$ "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." I don't see how this is relevant to the proof that saving $50$ is the best that can be done. $\endgroup$ Jul 15 at 19:27
  • $\begingroup$ Stephen's answer actually do not touch the envelope anymore after the first prisoner touched it, so I'm not sure this answer is complete enough to say that the first 50 prisoners can encode 99 states based on the envelope side. $\endgroup$
    – justhalf
    Jul 16 at 5:54
  • $\begingroup$ @justhalf Consider the first prisoner "an oracle" that eliminates 49 states. It doesn't affect our encoding of states. Since this is a deterministic algorithm (tactic), at any specific state, the algorithm directs that we can only guess one number. Which state we run into is another thing (designing the algorithm vs. putting it into run). $\endgroup$
    – iBug
    Jul 16 at 5:56
  • $\begingroup$ Yes, I agree the first prisoner eliminates 49 (or 50, actually) states but I'm not sure how that is implied by your answer. $\endgroup$
    – justhalf
    Jul 16 at 5:59
  • $\begingroup$ @justhalf It doesn't imply, actually. My answer provides a layout of the states, and how you encode the numbers into these states is a different problem. The core idea is, think it as a state machine, you need 100 states to encode 100 different numbers. And my answer just describes that "you need 51 prisoners to form such a 100-state state machine". $\endgroup$
    – iBug
    Jul 16 at 6:06
4
$\begingroup$

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.)

$\endgroup$
3
  • 1
    $\begingroup$ I love how you think. However C) they are expected to place the number back in the envelope. But yes in real life, even with the number inside the envelope it can be placed in different orientations without the guards finding out. This would allow the prisoners to pass more bits of information. Anyway you get a vote up from me. $\endgroup$ Jul 16 at 4:22
  • 3
    $\begingroup$ In this vein - crease the corners of the envelope. Each corner can have 2 creases - near the corner and a bit further. Altogether - 8 bits of information are available. $\endgroup$
    – Vilx-
    Jul 16 at 7:19
  • $\begingroup$ @PlayerOne: that's exactly what I said, 2 days ago. $\endgroup$
    – smci
    Jul 18 at 23:00
2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ The prisoners are already allowed randomness. I am quite interested to see what is the best answer in expectation, ie., if the whole experiment can be repeated like a million times? $\endgroup$ Jul 16 at 4:39
  • $\begingroup$ Your calculation is of by half a prisoner. You have a 50% chance that the first prisoner has the correct parity. In that case only 24 prisoner die in worst case average. So in total 75.5 prisoner survive. $\endgroup$
    – Etoplay
    Jul 16 at 13:25
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

(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.

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
3
  • 8
    $\begingroup$ If prisoner 3 sees it face-up, how does he know if the number is 49 or is >52? $\endgroup$
    – msh210
    Jul 15 at 16:22
  • $\begingroup$ This won't work. Assume the guess sequence is 50, 48, 46 (answer = 47). The next prisoner doesn't know whether they should guess 47 or 56 (following 50, 52, 54). $\endgroup$
    – iBug
    Jul 15 at 16:23
  • $\begingroup$ Welcome to Puzzling! Please take our tour and look around at our other puzzles :) $\endgroup$
    – bobble
    Jul 15 at 16:50
-4
$\begingroup$

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

$\endgroup$
1
  • 6
    $\begingroup$ Binary search has already (to my knowledge) been offered in two answers, one of which is deleted. The same problem remains: how does the third person know what the first person did? If they see "envelope face up", should they guess within 25-50 or 75-100? Anyways, welcome to Puzzling, take our tour and look around at our other puzzles. $\endgroup$
    – bobble
    Jul 16 at 14:25
-5
$\begingroup$

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...

$\endgroup$
2
  • 16
    $\begingroup$ Third prisoner encounters the envelope with face up, which is code for "higher". How does he know whether he has to guess between 25-50, or 75-100 ? $\endgroup$
    – Gloweye
    Jul 16 at 11:54
  • $\begingroup$ (Also, welcome to Puzzling! We have a tour and many other puzzles 'round the site for you to explore) $\endgroup$
    – bobble
    Jul 16 at 13:49

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