11118 - Prisoners, Boxes and Pieces of Paper

[sclo]

Can someone tell me if the following I/O are correct?
removed....
they were nonsense.

Thanks

[little joey]

No, it's not. I think giving the correct answers is a spoiler, but let me admit that I couldn't have solved it without searching the net. And I couln't believe what I found, until I read it at least three times
Coodos, Igor.

[misof]

The puzzle is indeed fascinating, the correct answer is far from what one would expect.

For those who are not getting the trick, the problem statement contains the following important sequence: "The prisoner opens n/2 boxes of his choice, one by one." (emphasis mine)

Abednego, thanks for showing us this problem!

[krijger]

Thanks for the hint misof. And what a surprising result! (the limit for n to infinity is nonzero) Really a fun puzzle. By the way, does anybody has a proof that there is no better strategy?

For those still struggling with the problem: work out the case for n=4 by hand. Let the second box the first prisoner opens be dependant on what was in the first box he opened, and try to find a way for the other prisoners to use this information.

[sclo]

That IS the trick. That's just easy to miss.

I wonder if there exists a way to derive analytically the result. I did it using simulation and guess the formula.

[Abednego]

There is a formula that starts out being very complicated, but then it simplifies to something trivial. My code is 3 lines long.

Originally, the problem comes from a talk in a math conference. The title of the talk was "Seven problems you think you've misheard." It also came with a proof of optimality.

[Quantris]

I've been looking for that proof of optimality -- do you have a specific place I could find it (was it published somewhere)?

[Abednego]

The amazing Google reveals this page:
http://www.sciencenews.org/articles/200 ... thtrek.asp
It has references at the bottom.