5 ms·

SPOILER 1 Names in boxes I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if

by jfries 10y ago

SPOILER 1 Names in boxes I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?

deleted 10y ago
[deleted]
hundt 10y ago
It's because you start with the box labeled (via the initial random labeling) with your name. If you cycle back to it then it means that you found your name on a piece of paper, since the next box you open is always the one matching the piece of paper in the last box. So it is impossible to start in a cycle that doesn't include your name.
- jfries 10y ago
  Ah right, that's clever. Thanks for the explanation!
- rntz 10y ago
  Couldn't I start in a "tail" leading to a cycle that doesn't include my name? Suppose my name is "A", and I proceed: check box A - read name B; check box B - read name C; check box C - read name B and now I'm in a B-C loop, and will never find my name.
  - agf 10y ago
    Re-read your scenario -- you have both box A and box C containing name B, but the problem statement says each name appears only once. So you can't get into cycles like this.
    - rntz 10y ago
      Ah, of course! That guarantees there are no "tails"; every name (& box) is part of exactly one cycle. And this is then a property of cycles of permutations generally. Thanks!
  - hundt 10y ago
    No, because in your example both boxes A and C have name B in them. That's against the rules.
  - twoodfin 10y ago
    No, then "B" would be in two boxes: A and C.
- thomasahle 10y ago
  Do you have any intuition to why it helps to build the query sequence on the data? It seems natural that if you have to plan the queries for everybody in advance, you can't do better than 2^(-100) or perhaps (50!)^2/100!. Yet somehow by using the return values to find our next query point we can do much better. Blows my mind.
  - sskates 10y ago
    Each individual still has a ~50% chance of being unable to find their name using the query sequence protocol. By agreeing to the same query sequence their success modes and failure modes are now linked. If there's a cycle of 51 or greater, all of those individuals in that cycle are guaranteed to fail, while if they're in a cycle of 50 or less, all of those individuals are guaranteed to succeed. What this protocol does is make it so each individual failure mode is much more likely to overlap with each other failure mode. Correlating the performance of individuals when you have a one fail all fail scenario is a common solution to this type of problem.
    - thomasahle 10y ago
      You are right, but we can also agree on a common query sequence in advance that doesn't use the 'results' of the queries. What about using what we find makes this so much more efficient?
      - Guillaume86 10y ago
        You need to use the result of the query to place yourself in the right cycle (in this case by starting with the box matching your name).
- Retric 10y ago
  It assumes, they can secretly assign and remember a 100 items random ordering and then execute it perfectly. Further, it assumes they can decide which orientation is the start vs end of the line. Thus, it's not actually possible, but 'in theory' it seems to work. EX: If I know your going to order based on which side is closet to the entry door nob when the door is closed. Well nothing says they all enter from the same door if it's based on the wall, put the table in the middle of the room.
  - mwerty 10y ago
    I must be missing something. Couldn't one instead assume that they have a private notebook and a pen? And that they can tell left from right? Seems more reasonable.
    - Retric 10y ago
      So you want to add a private notebook that the warden can't read. Further, left vs right does not help if the table is in the middle of a room and people are entering from random doors. AKA, the solution assumes a lot of information not explicitly part of the original wording.
  - fenomas 10y ago
    I agree that the puzzle sort of plays dirty pool here. The strict requirement is that the boxes are distinguishable. The puzzle implies this by saying they're lined up on a table, but it would be more honest to the reader to say they're numbered 1-100, or somesuch.
- SilasX 10y ago
  I don't understand: the solution text claims that some permutations are guaranteed to work every time[1]. But you still have to initially land in one of "your" cycles, right? [1] "If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared."
  - lmkg 10y ago
    You always land in "your" cycle, because you start with the box with your name on it. All sequences of box-opening that use the method described must eventually cycle, because both box-to-name mappings are 1-to-1. Because it's a cycle, the sequence must eventually lead back to the box you started with. Since you start with the box with your name on it, then whatever cycle you landed it, it definitely contains the box with your name on it, because that box is the one that completes the cycle. The only question is whether the cycle is length-50 or less.
    - SilasX 10y ago
      I guess that's what I'm confused about: when we start, the boxes we map our names to have nothing to do with the name in the box. Just because my cycle includes the box I got assigned to, doesn't mean that cycle includes the box with my name inside it. If my name maps to 89, then sure, I accept 89 is a LT-50 cycle, but why does it mean that that cycle actually contains my name (as opposed to the box we assigned me to)?
      - hundt 10y ago
        Think about how you will get back to the box you got assigned to. Like what do you have to see in order to return to box 89, where you started?
        SilasX 10y ago
        Ah, okay, that makes more sense. So the solution is to impose a random ordering on the (1-100 random numbers assigned to the) boxes that ensures you will return to the first one you picked, and that the one that points to your initial pick (or your initial pick itself) has your name in it. This ordering then partitions the boxes into cycles where each prisoner is in their cycle, and has a low chance of having 50-sized cycles. Still mesmerized at how the choice of query can improve your chances like that without accumulating information.
deleted 10y ago
[deleted]
phkahler 10y ago
I don't understand the answer at all. Are they suggesting that the prisoners have somehow labeled the boxes? Or do they agree to assign names to the boxes via some other way - like make an alphabetic list of prisoners and assume that is the order of the "names on the boxes"? I suppose I just answered my own question, but I'm still not sure ;-)
- gambiting 10y ago
  Every prisoner assigns every box a random name from the list. Boxes cannot be modified in any way, so every prisoner has to do it on their own. The (unexplained) assumption here is that each prisoner can do that somehow, either in their head or on a piece of paper. It doesn't matter that every prisoner has their own unique assignment of names to boxes. The crucial part here is that it's not guaranteed to work - but it gives prisoners 30% chance to survive, as opposed to some infinitesimally small number if each picks 50 boxes on random.
  - captaincanoe 10y ago
    If each prisoner randomly labels the boxes in their own (presumably independent) manner, then this strategy fails miserably. In fact, it's equivalent to each prisoner choosing 50 random (unique) boxes. The solution specifies that "the prisoners must first agree on a random labeling of the boxes by their own names." This is necessary.
  - hexane360 10y ago
    If each prisoner has their own ordering, it's exceedingly likely that one of those orderings will have a 51-cycle. This strategy only works with one common dictionary. You have the same individual odds, but you've linked each person: each member of a cycle succeeds or fails together. If it wasn't decided beforehand, you could just make up the ordering as you go. This gives exactly the same odds as random selection.
- burkaman 10y ago
  Yeah, they memorize their own random ordering. Alphabetic is risky because the warden might guess that strategy and purposefully set up the boxes so it doesn't work.
justinnhli 10y ago
Minute Physics [1] did a video on the puzzle [2] and the solution [3]. [1] https://www.youtube.com/user/minutephysics/videos https://www.youtube.com/user/minutephysics/videos [2] https://www.youtube.com/watch?v=eivGlBKlK6M https://www.youtube.com/watch?v=eivGlBKlK6M [3] https://www.youtube.com/watch?v=C5-I0bAuEUE https://www.youtube.com/watch?v=C5-I0bAuEUE
bjornedstrom 10y ago
I coded a simulation here if that helps: https://gist.github.com/bjornedstrom/971574557b6f3179db083508c8cf8c3b https://gist.github.com/bjornedstrom/971574557b6f3179db08350...
- adium 10y ago
  The first two times I ran it I got 0.298 and 0.286. Out of 20 attempts 5 were below 30%.
  - hundt 10y ago
    1000 is a pretty small number of trials. Also note the docs on random.shuffle: Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.[1] I don't know if we have any reason to believe that the small subset of all permutations that this library can generate is unbiased in terms of the size of the cycles. https://docs.python.org/2/library/random.html#random.shuffle https://docs.python.org/2/library/random.html#random.shuffle
- Guillaume86 10y ago
  I also coded a simulation, mine is in js: https://jsfiddle.net/a3ch3s5h/ https://jsfiddle.net/a3ch3s5h/ I only run once, you'll have to run it a few times to get a positive result. The output is displayed in the js console (F12 on most browsers). Edit: Something interesting I derived from the solution is that by allowing the first prisoner to reset the experiment if he fails or don't like the result, they get a 100% success rate. The first prisoner just need to wait for an arrangement which place him in a 50 length cycle (which means no other cycle can be of length > 50).

by jfries 10y ago

deleted 10y ago

[deleted]

hundt 10y ago

It's because you start with the box labeled (via the initial random labeling) with your name. If you cycle back to it then it means that you found your name on a piece of paper, since the next box you open is always the one matching the piece of paper in the last box. So it is impossible to start in a cycle that doesn't include your name.

jfries 10y ago
Ah right, that's clever. Thanks for the explanation!
rntz 10y ago
Couldn't I start in a "tail" leading to a cycle that doesn't include my name? Suppose my name is "A", and I proceed: check box A - read name B; check box B - read name C; check box C - read name B and now I'm in a B-C loop, and will never find my name.
- agf 10y ago
  Re-read your scenario -- you have both box A and box C containing name B, but the problem statement says each name appears only once. So you can't get into cycles like this.
  - rntz 10y ago
    Ah, of course! That guarantees there are no "tails"; every name (& box) is part of exactly one cycle. And this is then a property of cycles of permutations generally. Thanks!
- hundt 10y ago
  No, because in your example both boxes A and C have name B in them. That's against the rules.
- twoodfin 10y ago
  No, then "B" would be in two boxes: A and C.
thomasahle 10y ago
Do you have any intuition to why it helps to build the query sequence on the data? It seems natural that if you have to plan the queries for everybody in advance, you can't do better than 2^(-100) or perhaps (50!)^2/100!. Yet somehow by using the return values to find our next query point we can do much better. Blows my mind.
- sskates 10y ago
  Each individual still has a ~50% chance of being unable to find their name using the query sequence protocol. By agreeing to the same query sequence their success modes and failure modes are now linked. If there's a cycle of 51 or greater, all of those individuals in that cycle are guaranteed to fail, while if they're in a cycle of 50 or less, all of those individuals are guaranteed to succeed. What this protocol does is make it so each individual failure mode is much more likely to overlap with each other failure mode. Correlating the performance of individuals when you have a one fail all fail scenario is a common solution to this type of problem.
  - thomasahle 10y ago
    You are right, but we can also agree on a common query sequence in advance that doesn't use the 'results' of the queries. What about using what we find makes this so much more efficient?
    - Guillaume86 10y ago
      You need to use the result of the query to place yourself in the right cycle (in this case by starting with the box matching your name).
Retric 10y ago
It assumes, they can secretly assign and remember a 100 items random ordering and then execute it perfectly. Further, it assumes they can decide which orientation is the start vs end of the line. Thus, it's not actually possible, but 'in theory' it seems to work. EX: If I know your going to order based on which side is closet to the entry door nob when the door is closed. Well nothing says they all enter from the same door if it's based on the wall, put the table in the middle of the room.
- mwerty 10y ago
  I must be missing something. Couldn't one instead assume that they have a private notebook and a pen? And that they can tell left from right? Seems more reasonable.
  - Retric 10y ago
    So you want to add a private notebook that the warden can't read. Further, left vs right does not help if the table is in the middle of a room and people are entering from random doors. AKA, the solution assumes a lot of information not explicitly part of the original wording.
- fenomas 10y ago
  I agree that the puzzle sort of plays dirty pool here. The strict requirement is that the boxes are distinguishable. The puzzle implies this by saying they're lined up on a table, but it would be more honest to the reader to say they're numbered 1-100, or somesuch.
SilasX 10y ago
I don't understand: the solution text claims that some permutations are guaranteed to work every time[1]. But you still have to initially land in one of "your" cycles, right? [1] "If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared."
- lmkg 10y ago
  You always land in "your" cycle, because you start with the box with your name on it. All sequences of box-opening that use the method described must eventually cycle, because both box-to-name mappings are 1-to-1. Because it's a cycle, the sequence must eventually lead back to the box you started with. Since you start with the box with your name on it, then whatever cycle you landed it, it definitely contains the box with your name on it, because that box is the one that completes the cycle. The only question is whether the cycle is length-50 or less.
  - SilasX 10y ago
    I guess that's what I'm confused about: when we start, the boxes we map our names to have nothing to do with the name in the box. Just because my cycle includes the box I got assigned to, doesn't mean that cycle includes the box with my name inside it. If my name maps to 89, then sure, I accept 89 is a LT-50 cycle, but why does it mean that that cycle actually contains my name (as opposed to the box we assigned me to)?
    - hundt 10y ago
      Think about how you will get back to the box you got assigned to. Like what do you have to see in order to return to box 89, where you started?
      - SilasX 10y ago
        Ah, okay, that makes more sense. So the solution is to impose a random ordering on the (1-100 random numbers assigned to the) boxes that ensures you will return to the first one you picked, and that the one that points to your initial pick (or your initial pick itself) has your name in it. This ordering then partitions the boxes into cycles where each prisoner is in their cycle, and has a low chance of having 50-sized cycles. Still mesmerized at how the choice of query can improve your chances like that without accumulating information.

deleted 10y ago

[deleted]

phkahler 10y ago

I don't understand the answer at all. Are they suggesting that the prisoners have somehow labeled the boxes? Or do they agree to assign names to the boxes via some other way - like make an alphabetic list of prisoners and assume that is the order of the "names on the boxes"? I suppose I just answered my own question, but I'm still not sure ;-)

gambiting 10y ago
Every prisoner assigns every box a random name from the list. Boxes cannot be modified in any way, so every prisoner has to do it on their own. The (unexplained) assumption here is that each prisoner can do that somehow, either in their head or on a piece of paper. It doesn't matter that every prisoner has their own unique assignment of names to boxes. The crucial part here is that it's not guaranteed to work - but it gives prisoners 30% chance to survive, as opposed to some infinitesimally small number if each picks 50 boxes on random.
- captaincanoe 10y ago
  If each prisoner randomly labels the boxes in their own (presumably independent) manner, then this strategy fails miserably. In fact, it's equivalent to each prisoner choosing 50 random (unique) boxes. The solution specifies that "the prisoners must first agree on a random labeling of the boxes by their own names." This is necessary.
- hexane360 10y ago
  If each prisoner has their own ordering, it's exceedingly likely that one of those orderings will have a 51-cycle. This strategy only works with one common dictionary. You have the same individual odds, but you've linked each person: each member of a cycle succeeds or fails together. If it wasn't decided beforehand, you could just make up the ordering as you go. This gives exactly the same odds as random selection.
burkaman 10y ago
Yeah, they memorize their own random ordering. Alphabetic is risky because the warden might guess that strategy and purposefully set up the boxes so it doesn't work.

justinnhli 10y ago

Minute Physics [1] did a video on the puzzle [2] and the solution [3]. [1] https://www.youtube.com/user/minutephysics/videos https://www.youtube.com/user/minutephysics/videos [2] https://www.youtube.com/watch?v=eivGlBKlK6M https://www.youtube.com/watch?v=eivGlBKlK6M [3] https://www.youtube.com/watch?v=C5-I0bAuEUE https://www.youtube.com/watch?v=C5-I0bAuEUE

bjornedstrom 10y ago

I coded a simulation here if that helps: https://gist.github.com/bjornedstrom/971574557b6f3179db083508c8cf8c3b https://gist.github.com/bjornedstrom/971574557b6f3179db08350...

adium 10y ago
The first two times I ran it I got 0.298 and 0.286. Out of 20 attempts 5 were below 30%.
- hundt 10y ago
  1000 is a pretty small number of trials. Also note the docs on random.shuffle: Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.[1] I don't know if we have any reason to believe that the small subset of all permutations that this library can generate is unbiased in terms of the size of the cycles. https://docs.python.org/2/library/random.html#random.shuffle https://docs.python.org/2/library/random.html#random.shuffle
Guillaume86 10y ago
I also coded a simulation, mine is in js: https://jsfiddle.net/a3ch3s5h/ https://jsfiddle.net/a3ch3s5h/ I only run once, you'll have to run it a few times to get a positive result. The output is displayed in the js console (F12 on most browsers). Edit: Something interesting I derived from the solution is that by allowing the first prisoner to reset the experiment if he fails or don't like the result, they get a 100% success rate. The first prisoner just need to wait for an arrangement which place him in a 50 length cycle (which means no other cycle can be of length > 50).