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:
- The prisoner numbered $k$ is led into the interrogation room and asked to choose an envelope and guess the number in that envelope.
- If they are correct then they and all the remaining prisoners are released.
- 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?