Hacker News Reader

Comment by Robin_Message | Hacker News Reader

I'm not seeing any obvious trick here. Trying it with just two prisoners, two boxes and one look, I can't see a way to do better than chance. I'm just wondering if it's something like the two envelopes problem, where you can on average do better by switching based on a monotonic function of the amount in the first envelope. Perhaps there is a way of picking the boxes based on your number that does better than average, even if its just a little bit. Any hints?

View on HN

with 2 prisoners the probability of success is 0.5, so you are correct.

with 4 prisoners the probability of success is about 0.37, which is better than chance. (the probability of success turns out to be one minus the difference of two harmonic numbers.)

it's hard to give a hint without giving the answer. the best i can do is that it has to do with the structure of cycles in permutations.

I don't know the answer, but I think I know the general direction. And unless I'm mistaken, you're wrong about the "2 prisoners".

Semi-Spoiler alert

As I interepreted the parent post, he hasn't found a way, with 2 prisoners, to do better than the strategy of every prisoner picking a random box. Under that strategy, your chance of success is 0.25 - 0.5 * 0.5 (each has a 0.5 chance of being right).

So if, as you say, you can get the probability to 0.5 for 2 prisoners, you are doing better than chance. (And this I already know how to do, I'm assuming for more prisoners it's the same idea, but generalized).

Am I making sense at all?

You're right, a 0.5 strategy is better than random chance. Unfortunately, the simplest generalization of that strategy yields only 0.5^(n-1), which is not good enough - you need to start with a bigger base case.

There does exists a strategy to get %50 for two people (hint below). But the case of two people does not help much to solve the more general case (imho).

HINT: Suppose each prisoner picks a box at random. They can (randomly) decide what box to open before they enter the room with the boxes, at a time when they can still communicate. In some cases they will then be able to determine that they have no chance of both finding their number. So there must be a better strategy.

Some hints (I hope they are not too revealing): Suppose the boxes are numbered. Also devise a scheme that will correlate the probabilities of success for the prisoners (i.e. success should not be independent).

The strategy should start working with 4 prisoners.

If I understood correctly, the idea is to have a consistent strategy for all prisoners, which "clumps" the winning results from 51 to 100 into 100.

I do not know, if `clumping' works as a general idea to point you in the right direction. (Though the solution does lead to clumping.)

As an alternative: Try to make the successes of the prisoners _not_ statistically independent.

Reply on news.ycombinator.com