16 ms·

Since wikipedia doesn't explain why it works (or maybe I just didn't understand it), I found this explanation much better: http://datagenetics.com/blog/december

Since wikipedia doesn't explain why it works (or maybe I just didn't understand it), I found this explanation much better: http://datagenetics.com/blog/december42014/index.html http://datagenetics.com/blog/december42014/index.html

dbatten 8y ago
Thank you. This is a MUCH better resource.
- manojlds 8y ago
  This sentence did the trick: > Because the prisoner starts on the box of their own number they are, by definition, on the chain that contains their ticket (there is only one ticket that points to that box).
  - jgtrosh 8y ago
    That's really the sentence that seems to be wrong, until you see the light shine through the problem.
dEnigma 8y ago
Ah yes, that's where I first heard about this problem. Dategenetics is a great blog in general, with lots of interesting content.
- squeakynick 8y ago
  Thanks for the compliment. </blush>
thaumasiotes 8y ago
Wikipedia provides exactly the same explanation that your link does: > The prison director's assignment of prisoner numbers to drawers can mathematically be described as a permutation of the numbers 1 to 100. > Every permutation can be decomposed into disjoint cycles, that is, cycles which have no common elements. > In the initial problem, the 100 prisoners are successful if the longest cycle of the permutation has a length of at most 50. Their survival probability is therefore equal to the probability that a random permutation of the numbers 1 to 100 contains no cycle of length greater than 50. What did you think was missing from the Wikipedia article?
- portlander12345 8y ago
  The prisoner starting with their own number box ensures that they are in the chain with their number ticket in it.
  - thaumasiotes 8y ago
    > The cycle notation is not unique since a cycle of length l can be written in l different ways depending on the starting number of the cycle. During the opening the drawers in the above strategy, each prisoner follows a single cycle which always ends with his own number.
  - MrBuddyCasino 8y ago
    And thats the part I still don't understand.
    - thaumasiotes 8y ago
      So, following your cycle looks like this: Open box 7, find number 2 Open box 2, find number 2700 Open box 2700, find number -16 Open box -16, find number 0.9 Open box 0.9, find number ℵ Open box ℵ, find number 赢 Open box 赢, find number two ... As you can see, it's not necessary to use numeric digits to identify the boxes; any identifier at all will do. But this is a cycle; if we had started by opening box 0.9, it would look like this: Open box 0.9, find number ℵ Open box ℵ, find number 赢 Open box 赢, find number two ... Open box 7, find number 2 Open box 2, find number 2700 Open box 2700, find number -16 Open box -16, find number 0.9 Exercise: given that this cycle starts with "open box 7", how does it end? (Or in other words, what is the second half of the line before "Open box 7"?) If this cycle instead started with "Open box ᚠ", how would it end in that case?
    - alkonaut 8y ago
      Think of it this way: you are always in a chain. It can be between 1 and 100 boxes long. But it can’t be a dead end or not include the 1-note. Worse case it visits all boxes and gets back to 1. Try forming a scenario that doesn’t. E.g a “loop”: Prisoner #1 opens box 1. Finds the number 2. Opens box 2 finds the number 3. Opens box 3... Could he now find the “2” that would lead to him being stuck in the 2-3 loop? No. He already found the 2. It can’t appear again. In the third box he’ll find a number he hasn’t seen. The loop cannot form in any other way than to come to where he started - which it will do when he finds the note with “1” on it. So by starting with box 1, he is on a loop of length 1..100 including the pointer TO box 1 (which is what he is looking for).
cbau 8y ago
This is a great explanation. Is this problem useful for anything? I've seen multiple variations of these prisoner problems now, and I can never remember any being useful in other contexts.
- eggpy 8y ago
  Well, first of all it's a puzzle so it's useful as something fun to think about. Math is kinda like science though, you never know exactly how or if a particular discovery will be useful. In this case maybe you could find some graph traversal scenario where this would be applicable. In the Wikipedia article under variants they mention > If the number of team members and the fraction of boxes which are opened is fixed, the winning probability stays strictly larger than zero when more empty boxes are added Replace boxes with nodes and now you have some math to determine graph traversals. Maybe a bit more math and you can expand it for multiple paths. I don't know though, I'm not a mathematician and I don't normally have to do more than DFS and BFS in coding interviews, but sure I can see some way that this might be useful.
- Balgair 8y ago
  Genetics for one. If a DNA primer-pair is looking for it's complement [0], then this strategy could be useful. Here the prisoners are the complementary primers and the DNA-sequence-to-be-matched-to is the cabinet. Shepherding proteins/histones could restrict in a nucleic bottleneck of some sort, such that only one primer gets to go at once without repeating [1]. Only when the primers are all set-up is the DNA 'free' to be transcribed or some such thing. [0] For a sequence like ATGC, the primer is the opposite nucleotide, therefore the 'matching number' would be not ATGC as well, but TACG. [1] Look, bio is weird, like, jumping genes are actually a thing. This set-up, though strange, is not as unreasonable as a lot of stuff that goes on.
- theknarf 8y ago
  It sounds like a parallelization algorithm. Spin up a hundred threads each whom does not need to communicate with anyone.
adyavanapalli 8y ago
I'm curious, is there a better strategy?
- presidentender 8y ago
  Any better strategy would have to exhibit the cyclic behavior of the proposed strategy. I don't think there is any.
- LolWolf 8y ago
  There is not, actually! You can show this strategy does as well as the case where prisoners have full information of each other's moves.[0] So any other strategy where each prisoner is blind to others' actions can always be executed in the full-information case above; so this bound is tight and this strategy is optimal: if there was a strategy that did better in the blind case, you could execute it in the full-information case to get a better outcome, but this is impossible. For a nice exposition of this, see Curtin and Warshauer's article "The Locker Puzzle." --- [0] More specifically, a game where all lockers are left open, so every strategy has the same probability of winning.
  - nemetroid 8y ago
    To be precise, the strategy is shown to be optimal as well in a modified game where all lockers are left open and you cannot open any more lockers if you find your own number.

dbatten 8y ago

Thank you. This is a MUCH better resource.

manojlds 8y ago
This sentence did the trick: > Because the prisoner starts on the box of their own number they are, by definition, on the chain that contains their ticket (there is only one ticket that points to that box).
- jgtrosh 8y ago
  That's really the sentence that seems to be wrong, until you see the light shine through the problem.

dEnigma 8y ago

Ah yes, that's where I first heard about this problem. Dategenetics is a great blog in general, with lots of interesting content.

squeakynick 8y ago
Thanks for the compliment. </blush>

thaumasiotes 8y ago

Wikipedia provides exactly the same explanation that your link does: > The prison director's assignment of prisoner numbers to drawers can mathematically be described as a permutation of the numbers 1 to 100. > Every permutation can be decomposed into disjoint cycles, that is, cycles which have no common elements. > In the initial problem, the 100 prisoners are successful if the longest cycle of the permutation has a length of at most 50. Their survival probability is therefore equal to the probability that a random permutation of the numbers 1 to 100 contains no cycle of length greater than 50. What did you think was missing from the Wikipedia article?

portlander12345 8y ago
The prisoner starting with their own number box ensures that they are in the chain with their number ticket in it.
- thaumasiotes 8y ago
  > The cycle notation is not unique since a cycle of length l can be written in l different ways depending on the starting number of the cycle. During the opening the drawers in the above strategy, each prisoner follows a single cycle which always ends with his own number.
- MrBuddyCasino 8y ago
  And thats the part I still don't understand.
  - thaumasiotes 8y ago
    So, following your cycle looks like this: Open box 7, find number 2 Open box 2, find number 2700 Open box 2700, find number -16 Open box -16, find number 0.9 Open box 0.9, find number ℵ Open box ℵ, find number 赢 Open box 赢, find number two ... As you can see, it's not necessary to use numeric digits to identify the boxes; any identifier at all will do. But this is a cycle; if we had started by opening box 0.9, it would look like this: Open box 0.9, find number ℵ Open box ℵ, find number 赢 Open box 赢, find number two ... Open box 7, find number 2 Open box 2, find number 2700 Open box 2700, find number -16 Open box -16, find number 0.9 Exercise: given that this cycle starts with "open box 7", how does it end? (Or in other words, what is the second half of the line before "Open box 7"?) If this cycle instead started with "Open box ᚠ", how would it end in that case?
  - alkonaut 8y ago
    Think of it this way: you are always in a chain. It can be between 1 and 100 boxes long. But it can’t be a dead end or not include the 1-note. Worse case it visits all boxes and gets back to 1. Try forming a scenario that doesn’t. E.g a “loop”: Prisoner #1 opens box 1. Finds the number 2. Opens box 2 finds the number 3. Opens box 3... Could he now find the “2” that would lead to him being stuck in the 2-3 loop? No. He already found the 2. It can’t appear again. In the third box he’ll find a number he hasn’t seen. The loop cannot form in any other way than to come to where he started - which it will do when he finds the note with “1” on it. So by starting with box 1, he is on a loop of length 1..100 including the pointer TO box 1 (which is what he is looking for).

cbau 8y ago

This is a great explanation. Is this problem useful for anything? I've seen multiple variations of these prisoner problems now, and I can never remember any being useful in other contexts.

eggpy 8y ago
Well, first of all it's a puzzle so it's useful as something fun to think about. Math is kinda like science though, you never know exactly how or if a particular discovery will be useful. In this case maybe you could find some graph traversal scenario where this would be applicable. In the Wikipedia article under variants they mention > If the number of team members and the fraction of boxes which are opened is fixed, the winning probability stays strictly larger than zero when more empty boxes are added Replace boxes with nodes and now you have some math to determine graph traversals. Maybe a bit more math and you can expand it for multiple paths. I don't know though, I'm not a mathematician and I don't normally have to do more than DFS and BFS in coding interviews, but sure I can see some way that this might be useful.
Balgair 8y ago
Genetics for one. If a DNA primer-pair is looking for it's complement [0], then this strategy could be useful. Here the prisoners are the complementary primers and the DNA-sequence-to-be-matched-to is the cabinet. Shepherding proteins/histones could restrict in a nucleic bottleneck of some sort, such that only one primer gets to go at once without repeating [1]. Only when the primers are all set-up is the DNA 'free' to be transcribed or some such thing. [0] For a sequence like ATGC, the primer is the opposite nucleotide, therefore the 'matching number' would be not ATGC as well, but TACG. [1] Look, bio is weird, like, jumping genes are actually a thing. This set-up, though strange, is not as unreasonable as a lot of stuff that goes on.
theknarf 8y ago
It sounds like a parallelization algorithm. Spin up a hundred threads each whom does not need to communicate with anyone.

adyavanapalli 8y ago

I'm curious, is there a better strategy?

presidentender 8y ago
Any better strategy would have to exhibit the cyclic behavior of the proposed strategy. I don't think there is any.
LolWolf 8y ago
There is not, actually! You can show this strategy does as well as the case where prisoners have full information of each other's moves.[0] So any other strategy where each prisoner is blind to others' actions can always be executed in the full-information case above; so this bound is tight and this strategy is optimal: if there was a strategy that did better in the blind case, you could execute it in the full-information case to get a better outcome, but this is impossible. For a nice exposition of this, see Curtin and Warshauer's article "The Locker Puzzle." --- [0] More specifically, a game where all lockers are left open, so every strategy has the same probability of winning.
- nemetroid 8y ago
  To be precise, the strategy is shown to be optimal as well in a modified game where all lockers are left open and you cannot open any more lockers if you find your own number.