珍珠湾ART

标题: 新囚犯问题 [打印本页]

作者: constant    时间: 2005-12-15 21:20
标题: 新囚犯问题

难度:+++

监狱里有2k个犯人。监狱长把犯人找来,说:“你们的名字在这2k个盒子里,每盒一个。明天你们轮流到这里来,每个人打开一个盒子,看看是不是自己,不是再开下一个,最多可以开k个,看到自己的名字就算通过。如果所有人都通过,就释放你们。现在你们可以讨论一个策略,完了之后不准再有任何形式的交流。”

每个人看到自己名字的概率是1/2。如果没有策略,释放的概率是(1/2)^(2k)。能不能设计一个策略,使得释放的概率有一个与k无关的正下界?

www.ddhw.com

 

作者: QFT    时间: 2005-12-16 04:05
标题: 一个问题:是不是看完后再放回去? 通过否只有自己知道?

  一个问题:是不是看完后再放回去? 通过否只有自己知道?





作者: constant    时间: 2005-12-16 04:43
标题: 是。每个人都不知道前边的任何结果

  是。每个人都不知道前边的任何结果





作者: sadfsdfsdfsd    时间: 2005-12-16 10:11
标题: 回复:新囚犯问题

第一个人看前k个盒子,然后排序. 第二个人从前k个盒子看log2(k)个(二分查找),从后k个盒子看k-log2(k)个,第三个人从前k个盒子看log2(k)个,从后k-log2(k)个看log2(k-log2(k))个,在看剩下的,排序.第三个和第二个相似,尽可能用二分查找.www.ddhw.com
 
上面的值并非确切计算只是大致估计,如果k很大基本上释放的概率接近1/2.
www.ddhw.com

 

作者: QL    时间: 2005-12-16 14:23
标题: 回复:新囚犯问题

Is reordering of the boxes allowed?
If so, each one may search the k right most boxes, and if he found his box, move it to the left most position. 
www.ddhw.com

 

作者: constant    时间: 2005-12-16 16:15
标题: Reordering is not allowed

  Reordering is not allowed





作者: IQ75    时间: 2005-12-17 00:21
标题: 回复:新囚犯问题

Then how can information be exchanged? www.ddhw.com
 
Questions:
1. Each time a box is open, do they close it right away for the next person to open it, or just leave it open always.
2. The next person has to wait until the former try all his k the boxes?www.ddhw.com
 
Thanks.
www.ddhw.com

 

作者: constant    时间: 2005-12-17 01:15
标题: 回复:回复:新囚犯问题

There cannot be information exchange.www.ddhw.com
 
1. Closed, kept in the original location and position. No marking allowed.www.ddhw.com
 
2. Yes. They will not see each other, and don't know each other's results.
www.ddhw.com

 

作者: QL    时间: 2005-12-18 06:19
标题: 回复:新囚犯问题

Here is an idea:www.ddhw.com
Each criminal is assigned a number 1--2k, and the i-th criminal will begin with the i-th box, if he found the box contains j-th criminal's name, he then check the j-th box, and continue this process, until he opens k boxes.
 
Constant, is this the right way? I am still think about the proof.
 
 


 www.ddhw.com

 

  本贴由[QL]最后编辑于:2005-12-17 23:4:53  


作者: QL    时间: 2005-12-18 06:25
标题: 回复:回复:新囚犯问题

Try to prove that the prcedure works:
Each random permutation induces some loops(using the aferomentioned procedure), if the number of elements in each loop is less than or equal to k, then every criminal will get `his' box.www.ddhw.com
So, the problem is now: with probability > some constant( not depend on k) that a permutation will not have a loop with length > k.....


 

 

  本贴由[QL]最后编辑于:2005-12-17 22:26:1  
www.ddhw.com

 

  本贴由[QL]最后编辑于:2005-12-17 23:2:17  


作者: QL    时间: 2005-12-18 06:58
标题: 回复:回复:回复:新囚犯问题

We can make the following estimation:
Number of permutations that have one loop of length (n+1):
C(2n,n+1) (n+1)! (n-1)! = 2n!/(n*(n+1))
Number of permutations that have one loop of length (n+2):
C(2n,n+2) (n+2)! (n-2)! < 2n!/(n*(n+1))
....www.ddhw.com
So the total number of permutations with the largest loop length> n is bounded above by
2n!/(n+1)
So, chance for the criminals is better than 1-(1/n+1), which tends to 1 as n goes to infinity. Sounds fishy, something wrong with the procedure or proof?


 www.ddhw.com

 

  本贴由[QL]最后编辑于:2005-12-17 23:0:1  


作者: QL    时间: 2005-12-18 16:01
标题: 回复:回复:回复:回复:新囚犯问题

Wrong estimation, try again:www.ddhw.com
Number of permutations that have one loop of length (n+1):
C(2n,n+1)*n!*(n-1)! = 2n!/(n+1)
Number of permutations that have one loop of length (n+2):
C(2n,n+2)*(n+1)! = 2n!/(n+2)....
 
So, probability that the longest loop has a length > n is:
2n!(1/(n+1)+1/(n+2)+1/(n+3)+1/(2n))
 
since 1/1+1/2+...1/n ~ln(n), 1/(n+1)+1/(n+2)...+1/(2n) ~ ln(2),
so the chance for the criminals is: 1-ln(2)
www.ddhw.com

 

作者: QL    时间: 2005-12-18 16:17
标题: 回复:回复:回复:回复:回复:新囚犯问题

I mean the chance is bounded below by  1-ln(2).
www.ddhw.com

 

作者: constant    时间: 2005-12-18 21:40
标题: 回复:回复:回复:回复:回复:回复:新囚犯问题

Great! The probability of 1 - ln2 = 0.3068... is very high, and I think it is the best possible.
www.ddhw.com

 

作者: QL    时间: 2005-12-18 22:42
标题: 回复:新囚犯问题

Thanks for the interesting problem.  I guess we need such intuitively 'no-way' problem once in a while to remind us not to lay too much confidence in intuition.
www.ddhw.com

 

作者: IQ75    时间: 2005-12-19 22:09
标题: A question

Good thought! But how can you expain the case that no >n loop but a lot of small loops?
www.ddhw.com

 

作者: QFT    时间: 2005-12-19 22:50
标题: what if boxes are mixed up? as thrown back to ball

  what if boxes are mixed up? as thrown back to ball





作者: QL    时间: 2005-12-20 05:07
标题: 回复:A question

In that case, every criminal will get his box within n steps.
www.ddhw.com

 

作者: QL    时间: 2005-12-20 06:12
标题: 回复:what if boxes are mixed up? as thrown back to b

Not quite understand your question, the boxes are numbered according to the problem, what do you mean by 'mixed up'?
www.ddhw.com

 

作者: QFT    时间: 2005-12-20 06:39
标题: 回复:回复:what if boxes are mixed up?

I mean if no label can be attached to boxes, and 监狱长 would rearrange the boxes after the boxes were seen by a prisoner.
www.ddhw.com

 

作者: QL    时间: 2005-12-20 14:31
标题: 回复:回复:回复:what if boxes are mixed up?

He would dare to do that, not now. That is prisoner abuse.
www.ddhw.com

 

作者: QFT    时间: 2005-12-20 20:25
标题: we like to discourage prisoners.[:B][:B]

Great solution!
www.ddhw.com

 





欢迎光临 珍珠湾ART (http://66.160.158.134/) Powered by Discuz! X3