100 prisoners and a secret number (sequel)

Question

Inspired by this brilliant puzzle by @DmitryKamenetsky!

Much to the annoyance of the guards, the sly prisoners bribed a guard and learnt about the number in the envelope in advance, and the first prisoner was able to "guess" the correct number! The guards had no choice but to release them all.

Only days later, however, the same 100 prisoners (numbered from 1 to 100) are caught again! They are brought back to the prison, where there is the same old interrogation room but with a deck of 16 envelopes instead of 1. The envelopes contain 16 secret numbers - all integers chosen between 1 and 100. On the $k$-th day the following happens:

1. The prisoner numbered $k$ is led into the interrogation room and asked to choose an envelope and guess the number in that 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 pick a different envelope to check, then they will put the envelope back and be shot. They have no info about the envelope they chose in Step 1, apart from the fact that it doesn't contain the number they guessed.

The prisoners are allowed, again, 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) and insert it into a specific position in the envelope deck 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.

However, the guards decided that in order to punish the prisoners for their bribery, before the 1st prisoner enters the interrogation room, the envelopes will be shuffled and randomly placed either face up or face down. After that, though, they promised not to touch the deck of envelopes.

Question 1: Given that the guards and the prisoners know that the 16 integers are the same, what's the most number of prisoners that can be guaranteed to be saved in the worst case scenario? What's the most number of prisoners that is expected to be saved?

Question 2: What if the 16 integers are not necessarily the same?

Answer 1

Question 1

At least 97 Prisoners escape, 98.03 on average

Prisoner 1:
* guesses 99
* looks at an envelope and puts it back in one of the first 9 spots such that the face-up sum of positions the resulting 9 first cards modulo 10 is equal to the last decimal of the number
Prisoner 2:
* 'reads' the first 9 cards and guesses 80-89
* looks at the last envelope and if possible puts it back in one of the last 7 spots such that the face-up sum of numbers the resulting 7 last cards modulo 8 is equal to the first decimal of the number Prisoner 3:
* 'reads' the first 9 cards for the last decimal
* 'reads' the last 7 cards for the first decimal
* and guesses 1-79 or 100
Prisoner 4:
* 'reads' the first 9 cards for the last decimal
* and guesses 90-98

example

Prisoner 1 guesses 99
Prisoner 1 picks a card and reads 37
Still on table: udd dud dud ddu udu
Summing up-positions from the left: 1+5+8 = 4 mod 10
Prisoner 1 adds 3 by placing it back down in the first position (with 3 ups after it in the first 9)
Duddduddu-------
Prisoner 1 dies :-(

Prisoner 2 'reads' the first 9 cards
duddduddu-------
Summing up-positions from the left: 2+6+9 = 7 mod 10
Prisoner 2 guesses 87
Prisoner 2 picks the last card and reads 37
Still on table: dud ddu ddu ddd uud
Summing up-positions from the right: 3+2 = 5 mod 8
Prisoner 2 adds 6 by placing it back up in the 6th position from the right (with 6-'number of ups' downs right of it)
---------dUdduud
Prisoner 2 dies :-(

Prisoner 3 'reads' the first 9 cards
duddduddu-------
Summing up-positions from the leftt: 2+6+9 = 7 mod 10
Prisoner 3'reads' the last 7 cards ---------dudduud
Summing up-positions from the right: 6+3+2 = 3 mod 8
Prisoner 3 guesses 37
Prisoner 3 is lucky that prisoner 2 could help him 98 prisoners escape

Question 2 improved

one more! At least 95 prisoners can be saved

Prisoner 1 can use the first 7 envelopes to pick and read one and then encode value mod 6
Prisoner 2 can 'read' the first 7 envelopes to get the value mod 6 and use the last 7 envelopes to encode that value mod 6 (even using the last 5 following my method of question one)
Prisoner 3 can 'read' the first 7 envelopes to pick the target one, then encode value/6 mod 6
Prisoner 4-6 can 'read' the first 7 envelopes + last7 envelopes to get the position and value mod 36 and guess 1-36 37-73 and 73+ respectively

How to encode:

Look at first 7
Take an envelope such that up-down of remaining 6 is divided either:
0-6
2-4 with odd difference between the 2

if starting with 2; even difference: take an envelope between them
if starting with 2; out difference: take an envelope outside them
if starting with 3; difference odd+odd or even+even: take the middle one
if starting with 3; difference odd+even: take the last
if starting with 3; difference even+odd: take the first

Putting the envelope back:
* If the spit is 0-6 make it 1-7 using the n-th position to encode the similar values.
* If the spit is 2-6 there are 9 possibilities, which all need 6 values encoded. We have 21 pairs and 35 triplets available i.e. more than the 54 options needed. One could encode those in a lot of ways, e.g. like in the table below. - With the additional understanding that the earliest possible envelope position is used, the target envelopes position and value should be clear.

examples:
If prisoner 2 sees dduuuuu---------, that means the third envelope has value 1 mod 6
If prisoner 2 sees uuddddu---------, that means the 7th envelope has value 5 mod 6

Question 2 initial

At least 94 prisoners can be saved

prisoner 1 can encode 2 bits: Take 1 of envelopes 1-3, such that the other 2 are equal. Then put it back creating the following orientations:
uud or ddu: third envelope is 3 mod 4
udu or dud: second envelope is 2 mod 4
duu or udd: first envelope is 1 mod 4
uuu or ddd: first envelope is 0 mod 4

Prisoner 2 can now: Guess 1-4; Take 1 of envelopes 4-6, such that the other 2 are equal; put it back in 16th position, encoding the last bit.
Prisoner 3 can now: Guess 5-8; Take 1 of envelopes 6-8, such that the other 2 are equal; put it back in 15th position, encoding the second last bit.

prisoner 4 can encode 3 additional bits: Take the 'target envelope', put it back depending on the value/4 mod 8
if 7: at 7th position, oriented different from 5 and 6
if 6: at 6th position, oriented different from 5 and 7
if 5: at 5th position, oriented different from 3 and 4
if 4: at 4th position, oriented different from 3 and 5
if 3: at 3rd position, oriented different from 1 and 2
if 2: at 2nd position, oriented different from 1 and 3
if 1: at 1st position, oriented up
if 0: at 1st position, oriented down

Prisoners 5-7 can now deduce 5 bits from envelopes 1-7, 15 and 16
5 guesses 9-40, 6 guesses 41-72, 7 guesses 73+

Answer 2

Here's an answer to question 1 which saves at least

$93$

prisoners. The strategy makes use of

the binary number system

and requires that

the prisoners are working under the assumption that the numbers are all the same

Here's the strategy:

The prisoner $k$ will enter the room, looking at the leftmost envelope's orientation. This will be $0$ and the opposite orientation will be $1$. Then, they will look at the rightmost $k-1$ envelopes' orientations and interpret it the binary representation of the number in the envelope, and guess that (any prisoner which sees all one orientation will guess $1$, including the first prisoner).

Here's why it works:

The numbers $1$ to $100$ can all be represented with at most $7$ bits. This means that after $7$ prisoners have guessed incorrectly, prisoner $8$ will see the unique $7$-bit representation of the number in all the envelopes, and therefore "guess" correctly. Importantly, there are more than $7$ envelopes, so the $0$ position can always be known. If there are exactly $7$ envelopes, they can decide at the start that down is $0$ to save the same number of prisoners in the worst-case, but with worse average-case performance. As the number of envelopes decreases, the number of prisoners killed increases exponentially, until $1$ envelope where $50$ can be saved $-$ this strategy reduces to StephenTG's solution to the original problem.

---

A slight modification makes this work for question 2 to save at least

$87$

prisoners.

The strategy is to guess the $7$th envelope from the right. Odd prisoners $2k-1$ will look at the $7$th envelope and set it down ($0$) or up ($1$) to represent the $k$th bit of that number. Even prisoners $2k$ will examine the rightmost $k-1$ envelopes as the first $k-1$ bits, and take the $7$th from the right as the $k$th bit, and guess that for the $7$th envelope. If they are wrong, they check the $k$th envelope from the right (doesn't matter what it is) and set the envelope to match the $7$th. Prisoner $14$ then reads the number off the rightmost $7$ envelopes and guesses that for the $7$th envelope on the right.

An important note:

Since the prisoners must guess one envelope and then choose a different one to check and manipulate, odd prisoners cannot make any meaningful guesses because they only have information on the one envelope they need to manipulate.

Answer 3

The strategy by Alex Jones for Question 1 can be improved for the average case, to save an expected number of approximately

94.87

prisoners. The following part is the same:

The rightmost 7 bits are interpreted as a binary number, with the orientation of the leftmost envelope deciding whether face-up or face-down designates a 1 bit. If prisoner $k$ guesses wrong, she takes envelope $k$ from the right, looks at the number, and puts it back in the same spot, in the orientation corresponding to bit $k$ in the binary representation of the secret number.

Now, here's how to improve the average case:

When guessing a number based on the rightmost $k-1$ bits, prisoner $k$ guesses a number uniformly at random from the subset of numbers 1-100 whose binary representation ends with those $k-1$ bits. For $k < 7$, this results in a $2^{k-1}$ percent chance of guessing correctly; prisoner 7 is guaranteed to guess correctly.

This results in the following number of prisoners saved on average (if my calculation is correct):

$1\% \times 100 + 1.98\%\times 99 + 3.88\%\times 98 + 7.45\%\times 97 + 13.7\%\times 96 + 23.0\%\times 95 + 31.3\%\times 94 + 17.6\%\times 93 \approx 94.87$

(Edit: removed bogus improved worst case based on an idea involving Hamming distance)

Question 2

To be continued...

Note

The prisoners have an as-yet unused capability: inserting the chosen envelope in a different spot than where they took it from. Perhaps this can be used in a further improved strategy.