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

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

11118 - Prisoners, Boxes and Pieces of Paper

Post by sclo » Sun Oct 15, 2006 2:05 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Oct 15, 2006 2:35 am

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

Post by misof » Sun Oct 15, 2006 11:07 am

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! :D

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Sun Oct 15, 2006 4:16 pm

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:

Post by sclo » Mon Oct 16, 2006 8:58 am

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.

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

Post by Abednego » Sun Oct 22, 2006 11:46 pm

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

Post by Quantris » Thu Oct 26, 2006 8:12 pm

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

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

Post by Abednego » Thu Oct 26, 2006 11:00 pm

The amazing Google reveals this page:
http://www.sciencenews.org/articles/200 ... thtrek.asp
It has references at the bottom.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 111 (11100-11199)”