## 11118 - Prisoners, Boxes and Pieces of Paper

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
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
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