8 ms·

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).
  - MrBuddyCasino 8y 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 8y 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 8y ago
        That was the shortest description that worked for me. Framed this way, its obvious - thanks, also to all the others!
    - Domenic_S 8y ago
      Assuming that linked list is shorter than 50, you're guaranteed to find your own number.
    - tukasqu 8y 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 8y 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.
- nebulous1 8y 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 8y 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.
itp 8y ago
This point was obvious once pointed out, and is definitely the reason this link clicked for me and the Wikipedia explanation did nothing.
- thaumasiotes 8y ago
  As I pointed out in a sibling comment, this is also stated in the Wikipedia article.
deleted 8y ago
[deleted]

> 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).
- MrBuddyCasino 8y 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 8y 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 8y ago
      That was the shortest description that worked for me. Framed this way, its obvious - thanks, also to all the others!
  - Domenic_S 8y ago
    Assuming that linked list is shorter than 50, you're guaranteed to find your own number.
  - tukasqu 8y 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 8y 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.
nebulous1 8y 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 8y 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.

itp 8y ago

This point was obvious once pointed out, and is definitely the reason this link clicked for me and the Wikipedia explanation did nothing.

thaumasiotes 8y ago
As I pointed out in a sibling comment, this is also stated in the Wikipedia article.

deleted 8y ago

[deleted]