Hacker News Reader

Comment by dbatten | Hacker News Reader

Two things:

1) You don't take your number when you find it. I guess my brain assumed "find" meant "find and take with you to prove you found it." Perhaps a better term might be "encounter."

2) Here's a much better explanation (thanks micaeked): http://datagenetics.com/blog/december42014/index.html. Essentially, the algorithm works because following numbers to drawers will eventually create a loop (e.g., drawer 2 points to 4 points to 6 points to 2). By starting with the drawer with your number, you're guaranteed to be in a loop with your number. The only question is whether your loop is less than 50 drawers long...

Furthermore, this confirms that there IS no transfer of information from previous prisoners in any way.

View on HN

The only question is whether your loop is less than 50 drawers long...

So then the question is: what proportion of the permutations of 100 numbers contain a cycle greater than 50 vertices long? Is it 30%? The claim made in the Wikipedia article is that the prisoners have around 30% chance of surviving.

Edit: looks like that is the case. You can even take the limit of the number of boxes (hence prisoners) to infinity and their probability of survival never drops below 30%! This is an amazing result.

Can you explain to me why it is guaranteed you will be in a loop with your number?

The entire set-up (the numbers in the boxes) is a permutation. In other words, it’s a function s that maps bijectively from [0, n-1] to [0, n-1], or to put it more simply: for each i in [0, n-1] there is exactly one value j such that s(j) = i.

If you take i_0, then i_1 = s(i_0), then i_2 = s(s(i_0))... and so forth, at some point you will encounter a value you have already seen (because you can only visit n different values at most), and from that point onward you will loop. The trick is that the first value you will see twice MUST be i_0 (your starting point). If not, that is if s(i_k) = i_m where m > 0 (and i_k is the last value before you loop back) then s(i_k) = s(i_{m-1}). This means that i_k = i_{m-1} which is in contradiction with the fact that i_k is the last value before looping (i_k was already visited at step m-1)

Edit to answer TFQ: if your start with your own number as i_0, the proof above shows that at some point you will loop back to it. Then it’s a question of whether you loop back in 50 moves or less.

To try a simpler explanation:

1) You will be in a loop (by a property of how permutations and hashing work).

2) Using the algorithm in the solution, you always go to the box indicated by the number in the drawer you open.

So if you start with "your" number's drawer, that it is "pointed to" by the drawer with your number in it. So your number is part of that loop.

* Thus you will never be in some other loop. Loops are disjoint. Disjoint circles, not train tracks that interconnect. Just loops. Think about that and realize it.

* This strategy guarantees you'll be in your loop. ("Unfortunately" you'll be at the end of that loop: the box that points to your number. But still, in the loop, which is the point).

* Thus if there are multiple loops, all of length 50 or less, you'll get your number before your number is up.

* And math shows that if there are 100 nodes in a randomly unidirected graph, 30% of them contain no loops greater than length 50.

So if everyone follows this strategy, 30% chance they'll win.

Every box points to a box and is pointed to by a box.

If at first you try box 3 and it doesn't contain your number 3, then your number 3 is out there and its box points to the one you tried. Thus its box is in your chain and has your number.

Reply on news.ycombinator.com