100 Prisoners, 100 lines of code

http://www.r-bloggers.com/100-prisoners-100-lines-of-code/

by ulvund • 16 years ago

43 17 16 years ago

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?

eru2• 16 years ago

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

sireat• 16 years ago

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.

eru2• 16 years ago

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.

dododo• 16 years ago

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.

edanm• 16 years ago

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?

D-Coder• 16 years ago

So the key idea is, if you get arrested, take a mathematician with you...

alphaBetaGamma2• 16 years ago

For the people who would go for an analytical solution rather then monte-carlo: for a large number of prisoners the probability that they all find their numbers tends to 1 - ln(2) ~= 0.3069

brlewis• 16 years ago

Look for the link "this excellent explanation" in the article for more on the analytical solution.

aidenn02• 16 years ago

Here's a new brain teaser. The warden is a mathematician, and instead of arranging them randomly, he ensures that there is a cycle of at least 51. However he's not too cruel, so he tells the prisoners that he has done this.

I'm pretty sure that since this is less random than the original version the survival rate would go up, but I haven't figured out how to do this.

shasta2• 16 years ago

Well, you can parameterize this strategy with an arbitrary permutation P of {1, .. 100} in the following way. If you open box containing N, instead of next opening box N, you open box P(N). If the warden's placement of numbers defines permutation Q (box N contains Q(N)), then this new scheme will have each prisoner find his number if P composed with Q has no cycles of length greater than 50.

Now, if you randomly picked a permutation P, then by symmetry since you don't know anything about the placement of numbers, you'd do just as well as with the original strategy. On the other hand, what you've proposed is that the warden has told you that choosing P to be identity results in failure. So if you exclude identity and pick one of the other permutations for your strategy, you'll fare a little tiny bit better on average.

You can do even better than this by picking from a more specialized class of permutations for P. I'll leave the problem of finding the best class for P as a follow up.

donaldc2• 16 years ago

If the boxes are in a random jumble when the prisoner enters, there may be no practical way of having 100 prisoners consistently assign an ordering from 1 to 100 for the boxes. The approach outlined will then fail.

Were I a particularly evil warden, I could meticulously place all the boxes in the same such "jumble" after each prisoner left. One of the prisoners would certainly derive a different ordering of the boxes than one of the other prisoners. The approach might still have a better than random chance of succeeding, but it would be lower than that outlined in the article, since there are now two (or more) chances for a cycle of length greater than 50.

shasta2• 16 years ago

> Were I a particularly evil warden, I could meticulously place all the boxes in the same such "jumble" after each prisoner left.

That's nothing. I'd make all of the boxes too small to even see, and I'd turn out the lights. Oh, and I'd shoot all of the prisoners.

aidenn02• 16 years ago

Cartesian coordinates seem to provide a very practical way of assigning an ordering.

donaldc2• 16 years ago

In a real-world setting, it's hard for 100 prisoners to consistently assign the same ordering to a jumble of 100 boxes.

100 Prisoners, 100 lines of code

Related Stories