swordsp N/A's List: The Locker Puzzle

• The Locker Puzzle from Mathematical Intelligencer 2006(1) pp28-31 

• Locker Room Dilemma

• Alice, Bob, Charlie, and Diane are prisoners under the supervision of warden Stan. One day the warden takes the ID cards from each prisoner and places them randomly in different lockers in a locker room. The locker room consists of four numbered lockers each with a curtain instead of a door. The curtains are marked 1, 2, 3, and 4. On the next day the prisoners will be taken, one at a time, into the locker room, where they can choose a curtain and look behind it. If they see their own ID card, they are said to be successful. Otherwise, they get to open a second curtain and again, if they see their own ID card, they are successful; otherwise they are failures. As they leave the locker room they cannot communicate with the others. And as they enter the locker room they have no way of telling if a previous prisoner was successful or has looked into any specific locker. 

    

   If all four prisoners are successful, then they will all be released; otherwise, back to the cells for everyone. 

    

   The prisoners know the protocol and can get together in advance to decide on a strategy. For example, they might decide that each should open two lockers at random. Such a strategy would mean that each prisoner succeeds with probability 1/2, and so the group of four is successful with probability 1/16, or 6.25%. Find a strategy whose probability of success is over 40%. 

    

   Extra Credit: Suppose there are 2m prisoners and each can look into m lockers. Find a strategy that is asymptotically positive as m goes to infinity. 

    

   Source: Thanks to Joe Buhler for the suggestion. The puzzle itself originates from the paper "The Cell Problem Complexity of Succinct Data Structures," by Peter Bro Milterson and Anna Gál. The language in the paper, however, is quite different than that used here. The problem is discussed in detail in "The Locker Puzzle," by E. Curtin and M. Warshauer, The Mathematical Intelligencer (2006:1)28-31.

• 100个囚犯关在一间屋子A里。另一间屋子B里有100个编了号的抽屉，每个抽屉里面有一张 纸条上一一对应地写着一个囚犯的名字。囚犯们一个一个被带到B屋，按他的想法打开其中 50个抽屉，看其中的名字，随后恢复原状并被带到刑场。如果所有的囚犯都成功地打开了 写有自己名字的抽屉，则他们被释放；但只要有一个人失败，那么集体枪决。  问囚犯们应该怎么做才能使他们活下来的概率超过30%。  注： 1. 囚犯被带离A屋后就无法再和仍在A屋的人交流 2. 任何人在进到B屋时，B屋的状态都是关着的100个有编号的抽屉。他们只看里面的名字 ，不做任何改变，不能留任何消息。 3. 如果随机开50个抽屉，那么存活概率为2^(-100) = 0... 4. 这个使存活概率超过30%的策略，已经被证明为最优策略。
• 我觉得当n充分大时，可以达到概率1-ln2=30.6%。办法是事先先随机排一张表，100个抽屉 对应100个人的名字，每个人轮到他进屋时，先打开表中他所对应的抽屉，如果名字不是他 ，设为A，则再打开A所对应的抽屉，以此类推。这样，2n个人能存活的概率当且仅当这张 事先安排的对应表与实际对应表相比，不存在一个大于n的圈,这个概率是 1-(2n)![1/(2n)+1/(2n-1)+1/(2n-2)+……+1/(n+1)]/(2n)!=1-1/(2n)+1/(2n-1)+1/(2n-2 )+……+1/(n+1)约等于1-ln2
• 关于概率的计算： 2n个人中构成一个长度为m的圈的概率为： C(2n,m)*(m-1)!*(2n-m)! / (2n)! ( n+1<=m<=2n )  因为长度为m，所以有C(2n,m)个组合； 对于每种组合，因为圈的尾部必须对应为本人，所以有(m-1)！种排列； 其他(2n-m)个人任意排列为(2n-m)! (2n)!为所有人的排列总数。 因为m>n，所以这样的圈只可能同时存在一个。 上式简化为1/m。 不存在大于n的圈的概率就是 1 - 1/(2n) - 1/(2n-1) - ... - 1/(n+1)
• 应该是  C(2n,m)*(m-1)!*(2n-m)! / (2n)! ( n+1<=m<=2n )  其中的(2n-m)!表示没有构成大圈的数的排列。 这样才能简化成1/m

2 more annotations...