Comment by dbatten | Hacker News Reader

Comment by dbatten | Hacker News Reader

I'm confused...

"Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers."

And, in the example given, "That prisoners 5 to 8 will also find their numbers can also be derived from the information gained by the first three prisoners."

There's never any explanation of what happens when a prisoner opens a drawer and finds it empty. In the first example given, what happens when prisoner 5 goes in and there's nothing in drawer 5? The algorithm doesn't seem to account for this.

It seems like there's some sort of assumption that the later prisoners are gathering information from the earlier prisoners, but the problem set-up seems to preclude this? They're going into a room so they can't watch each other, the drawers are closed afterwards so they can't derive information from which drawers are open/closed, and they're not allowed to communicate.

Am I not following something?

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.

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.

The statement "That prisoners 5 to 8 will also find their numbers can also be derived from the information gained by the first three prisoners" is poorly worded. I think the author intended it to mean the information gained to you, an outside observer trying to prove this statement. There is no transfer of information from one prisoner to the next.

Also, when the prisoners find their number they don't remove it. No drawers are ever empty. They just have to open a drawer that contains their number.

Absolutely agreed about that sentence being poorly phrased; I've edited that now.

The numbers are left in the drawers once someone finds their number.

I think you're right that the statement doesn't make sense- or else we're both not understanding it.

From what I can see, no prisoner needs any information beyond knowing their own number. Once they know that, they're just searching the cycle that their number is in to see if it's less than 50-long.

Reply on news.ycombinator.com