## 11118 - Prisoners, Boxes and Pieces of Paper

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

### 11118 - Prisoners, Boxes and Pieces of Paper

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

Thanks
Last edited by sclo on Mon Oct 16, 2006 9:02 am, edited 1 time in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada
I've been looking for that proof of optimality -- do you have a specific place I could find it (was it published somewhere)?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact: