4 ms·

And thats the part I still don't understand.

thaumasiotes 9y 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 9y 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).
- MrBuddyCasino 9y ago
  Ok, so I‘m walking a linked list that will lead to my number. But I still don’t get why the odds are better than just opening the first 50 boxes and hope for the best? What changes because I‘m on the chain?
  - treis 9y ago
    The success criteria goes from the prisoners randomly picking correctly to the warden not randomly creating a loop larger than 50. If the warden creates no loop greater than 50 then the prisoners win. If he creates one of 51 or more then the prisoners lose because the 51st number wont be found.
    - MrBuddyCasino 9y ago
      That was the shortest description that worked for me. Framed this way, its obvious - thanks, also to all the others!
  - Domenic_S 9y ago
    Assuming that linked list is shorter than 50, you're guaranteed to find your own number.
  - tukasqu 9y ago
    Think of it this way - if all the boxes are sorted then everyone finds their own number in their box. But let's say that everything is sorted except your's and some other prisoner's number. Then it makes sense to follow the chain, because there is only one chain of two nodes. Basically any number that is in its place is sorted and thus not part of a chain. Any number that is not in its place is not sorted and part of a chain. There can be many different chains, but only one chain that leads to your number. By starting from your own box, you guarantee that you follow your own chain thus reducing the search space. Maybe it helps to understand...
  - dfxm12 9y ago
    The goal isn't to maximize an individual's odds of finding their number, but maximizing the odds of the entire group finding their number.
  - jamie_ca 9y ago
    > If just one prisoner does not find his number, all prisoners die. You're trying to find a strategy that is successful for all prisoners. Following the chain reduces the problem to "is there a cycle of length >50", which can be calculated easier. Opening boxes randomly (or arbitrarily, as in "50 boxes starting with my number), by all prisoners, is 50%100 which as mentioned is vanishingly small. The trick is that chain-following actually gives information to each prisoner as they go, which helps leverage into a better win chance.
nebulous1 9y ago
If you consider that each box only has one box that "points" to it, and that last box must necessarily be part of the box's cycle (by definition, there's no way to avoid it as if you hypothetically swapped the last box to point somewhere else then all you're doing is linking the cycles and you'll end up in the same place but later)
jlarocco 9y ago
For me it helped to think of it as a collection of linked lists. At most, there can be 100 lists of length 1, where each number points to itself. On the other extreme, there are many ways to create a list of length 100. The strategy takes advantage of the fact that randomly permuting the numbers is less likely to create one or two long lists, and more likely to create a bunch of shorter lists. Since each prisoner knows which list he belongs to, he can use that information to reduce his search space from all of the boxes to just the boxes in his list.

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 9y 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).

MrBuddyCasino 9y ago
Ok, so I‘m walking a linked list that will lead to my number. But I still don’t get why the odds are better than just opening the first 50 boxes and hope for the best? What changes because I‘m on the chain?
- treis 9y ago
  The success criteria goes from the prisoners randomly picking correctly to the warden not randomly creating a loop larger than 50. If the warden creates no loop greater than 50 then the prisoners win. If he creates one of 51 or more then the prisoners lose because the 51st number wont be found.
  - MrBuddyCasino 9y ago
    That was the shortest description that worked for me. Framed this way, its obvious - thanks, also to all the others!
- Domenic_S 9y ago
  Assuming that linked list is shorter than 50, you're guaranteed to find your own number.
- tukasqu 9y ago
  Think of it this way - if all the boxes are sorted then everyone finds their own number in their box. But let's say that everything is sorted except your's and some other prisoner's number. Then it makes sense to follow the chain, because there is only one chain of two nodes. Basically any number that is in its place is sorted and thus not part of a chain. Any number that is not in its place is not sorted and part of a chain. There can be many different chains, but only one chain that leads to your number. By starting from your own box, you guarantee that you follow your own chain thus reducing the search space. Maybe it helps to understand...
- dfxm12 9y ago
  The goal isn't to maximize an individual's odds of finding their number, but maximizing the odds of the entire group finding their number.
- jamie_ca 9y ago
  > If just one prisoner does not find his number, all prisoners die. You're trying to find a strategy that is successful for all prisoners. Following the chain reduces the problem to "is there a cycle of length >50", which can be calculated easier. Opening boxes randomly (or arbitrarily, as in "50 boxes starting with my number), by all prisoners, is 50%100 which as mentioned is vanishingly small. The trick is that chain-following actually gives information to each prisoner as they go, which helps leverage into a better win chance.

nebulous1 9y ago

If you consider that each box only has one box that "points" to it, and that last box must necessarily be part of the box's cycle (by definition, there's no way to avoid it as if you hypothetically swapped the last box to point somewhere else then all you're doing is linking the cycles and you'll end up in the same place but later)

jlarocco 9y ago

For me it helped to think of it as a collection of linked lists. At most, there can be 100 lists of length 1, where each number points to itself. On the other extreme, there are many ways to create a list of length 100. The strategy takes advantage of the fact that randomly permuting the numbers is less likely to create one or two long lists, and more likely to create a bunch of shorter lists. Since each prisoner knows which list he belongs to, he can use that information to reduce his search space from all of the boxes to just the boxes in his list.