Timeline for 100 prisoners and a secret number
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 16, 2021 at 15:18 | comment | added | justhalf | That's what I'm saying. So I guess we are on the same page now. | |
| Jul 16, 2021 at 7:47 | comment | added | iBug | @justhalf You're still confusing "states" and "transitions". The first prisoner makes a transition by putting the envelope on a specific side, and this transition eliminates half of the remaining states. I.E. the new state and all further states reachable from this one creates a branch. So the first prisoner eliminates 49 (or 50) states by transitioning into a state where "the eliminated ones" are no longer reachable. | |
| Jul 16, 2021 at 7:12 | comment | added | justhalf | Ah ok. I understand the "In other words" part, but couldn't really understand how it relates to the prior part. Can you elaborate? For example, what do you mean by the first prisoner only encoding one state? You mentioned that the first prisoner eliminates 50 states. So perhaps the first one actually give 1 bit of information so we are left with 50 states and each subsequent prisoner eliminates 1 state each time (or 2, one for each possible bit the first prisoner gives)? | |
| Jul 16, 2021 at 6:06 | comment | added | iBug | @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". | |
| Jul 16, 2021 at 5:59 | comment | added | justhalf | Yes, I agree the first prisoner eliminates 49 (or 50, actually) states but I'm not sure how that is implied by your answer. | |
| Jul 16, 2021 at 5:56 | comment | added | iBug | @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). | |
| Jul 16, 2021 at 5:54 | comment | added | justhalf | 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. | |
| Jul 15, 2021 at 19:27 | comment | added | mathworker21 | "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. | |
| Jul 15, 2021 at 16:31 | history | answered | iBug | CC BY-SA 4.0 |