4 ms·

Right, so picking a box at random and following the chain would be bad because you could get back to where you started having not found your number. Starting wi

Right, so picking a box at random and following the chain would be bad because you could get back to where you started having not found your number. Starting with your own numbered box is your defense against this because to go back to where you started you would have to have found your number.

daxfohl 8y ago
This was my aha moment. I was thinking, the solution presented seemed not only invalid but ill-defined, as you could hit a cycle and still have picks left. With this, it totally makes sense why it works: if there are disjoint cycles, this strategy guarantees that each prisoner is on its own cycle. And I guess the math works out that in unidirected graphs of 100 nodes, 30% of them contain only disjoint cycles of 50 or fewer nodes.
- sigotirandolas 8y ago
  Because of the way that the problem is set up (each of the 100 numbers is in one of the 100 lockers), it can always be written as a list of disjoint cycles (mathematically: every permutation can be written as a product of disjoint cycles). So, by starting in your own locker, you will eventually end up finding your own number. The only constraint is that everyone has to do it in 50 tries or less, i.e. there's no cycle of length >50.
ddtaylor 8y ago
Not that it's fair to ask you this, but how would we model the probability of picking chains at random? I would assume it's much better than the (1/2)^(100) approach of picking random each time.
- flyGuyOnTheSly 8y ago
  >I would assume it's much better than the (1/2)^(100) approach of picking random each time. You can assume whatever you wish, but the calculated proof is right there in your statement.
  - ddtaylor 8y ago
    What I don't know is how to model the probability of the chain starting anywhere in the cycle.
    - flyGuyOnTheSly 8y ago
      At the risk of sounding obtuse... is the answer you're looking for not exactly (1/2)^(100)?
    - sigotirandolas 8y ago
      There's no 'start' of a cycle, they are circular. I.e. the cycle 1->2->3->1 is the same as 3->1->2->3). I.e. picking a locker at random is equivalent to picking a chain of length N with probability N/100. In fact, the prisoners aren't given any information about the cycles and can't communicate, so they can't choose a cycle "at random". Not sure if your question can be formulated as follows (which requires giving more information to the prisoners): Suppose that we color every group of lockers that form a cycle in a different color, and every prisoner then picks a random color and then picks a random locker among the lockers of that color. What is the chance of winning?
    - daxfohl 8y ago
      I would assume it's much worse than the (1/2)^(100) approach of picking random each time. If you pick randomly with each of your 50 picks then you've got a 50% chance of winning. If you pick a random cycle and follow it, then you win iff the cycle you pick is your cycle and your number occurs within the first 50 of that cycle. So if the cycle that includes you is small, the first thing is less than 50%, and if the cycle that includes you is large, then the last thing is .. hmm well worth numbering: Say there's a 99 cycle and a 1 cycle. So 0.99 you're in the latter. And assuming that, 50/99 you pick a box that leads you to yourself in 50 picks. And 1/100 you're in the first, and assuming that 1/100 you pick it. So, 1/100 x 1/100 + 0.99 x 50/99 = .0001 + .5 = 0.5001. Hmm, I expected it to be under .5. So .. help?
      - daxfohl 8y ago
        I think my math for the above case is wrong, but I've got seven empty beer cans in front of me so. But even if it's right, you can somewhat rationalize. If there are two cycles each of len 50 then it's 50% chance. And if there are two cycles where one is 99 and the other is 1, then you've got very marginally better than 50% chance. And if it's one cycle of 100 you've got 50%. But if it's more than two cycles, say three of 33 or 34, then you can quickly see that you've only got a 33% chance of finding yourself. And plenty of outcomes like that exist. So it seems like 1 cycle (or apparently 2 with 99:1) is an upper bound. And the remainder only serve to lower the odds. And given they're plenty likely (I guess), your odds are even worse than randomly guessing with each pick.

daxfohl 8y ago

This was my aha moment. I was thinking, the solution presented seemed not only invalid but ill-defined, as you could hit a cycle and still have picks left. With this, it totally makes sense why it works: if there are disjoint cycles, this strategy guarantees that each prisoner is on its own cycle. And I guess the math works out that in unidirected graphs of 100 nodes, 30% of them contain only disjoint cycles of 50 or fewer nodes.

sigotirandolas 8y ago
Because of the way that the problem is set up (each of the 100 numbers is in one of the 100 lockers), it can always be written as a list of disjoint cycles (mathematically: every permutation can be written as a product of disjoint cycles). So, by starting in your own locker, you will eventually end up finding your own number. The only constraint is that everyone has to do it in 50 tries or less, i.e. there's no cycle of length >50.

ddtaylor 8y ago

Not that it's fair to ask you this, but how would we model the probability of picking chains at random? I would assume it's much better than the (1/2)^(100) approach of picking random each time.

flyGuyOnTheSly 8y ago
>I would assume it's much better than the (1/2)^(100) approach of picking random each time. You can assume whatever you wish, but the calculated proof is right there in your statement.
- ddtaylor 8y ago
  What I don't know is how to model the probability of the chain starting anywhere in the cycle.
  - flyGuyOnTheSly 8y ago
    At the risk of sounding obtuse... is the answer you're looking for not exactly (1/2)^(100)?
  - sigotirandolas 8y ago
    There's no 'start' of a cycle, they are circular. I.e. the cycle 1->2->3->1 is the same as 3->1->2->3). I.e. picking a locker at random is equivalent to picking a chain of length N with probability N/100. In fact, the prisoners aren't given any information about the cycles and can't communicate, so they can't choose a cycle "at random". Not sure if your question can be formulated as follows (which requires giving more information to the prisoners): Suppose that we color every group of lockers that form a cycle in a different color, and every prisoner then picks a random color and then picks a random locker among the lockers of that color. What is the chance of winning?
  - daxfohl 8y ago
    I would assume it's much worse than the (1/2)^(100) approach of picking random each time. If you pick randomly with each of your 50 picks then you've got a 50% chance of winning. If you pick a random cycle and follow it, then you win iff the cycle you pick is your cycle and your number occurs within the first 50 of that cycle. So if the cycle that includes you is small, the first thing is less than 50%, and if the cycle that includes you is large, then the last thing is .. hmm well worth numbering: Say there's a 99 cycle and a 1 cycle. So 0.99 you're in the latter. And assuming that, 50/99 you pick a box that leads you to yourself in 50 picks. And 1/100 you're in the first, and assuming that 1/100 you pick it. So, 1/100 x 1/100 + 0.99 x 50/99 = .0001 + .5 = 0.5001. Hmm, I expected it to be under .5. So .. help?
    - daxfohl 8y ago
      I think my math for the above case is wrong, but I've got seven empty beer cans in front of me so. But even if it's right, you can somewhat rationalize. If there are two cycles each of len 50 then it's 50% chance. And if there are two cycles where one is 99 and the other is 1, then you've got very marginally better than 50% chance. And if it's one cycle of 100 you've got 50%. But if it's more than two cycles, say three of 33 or 34, then you can quickly see that you've only got a 33% chance of finding yourself. And plenty of outcomes like that exist. So it seems like 1 cycle (or apparently 2 with 99:1) is an upper bound. And the remainder only serve to lower the odds. And given they're plenty likely (I guess), your odds are even worse than randomly guessing with each pick.