难度：+++
监狱里有2k个犯人。监狱长把犯人找来，说：“你们的名字在这2k个盒子里，每盒一个。明天你们轮流到这里来，每个人打开一个盒子，看看是不是自己，不是再开下一个，最多可以开k个，看到自己的名字就算通过。如果所有人都通过，就释放你们。现在你们可以讨论一个策略，完了之后不准再有任何形式的交流。”
每个人看到自己名字的概率是1/2。如果没有策略，释放的概率是(1/2)^(2k)。能不能设计一个策略，使得释放的概率有一个与k无关的正下界？
第一个人看前k个盒子,然后排序. 第二个人从前k个盒子看log2(k)个(二分查找),从后k个盒子看k-log2(k)个,第三个人从前k个盒子看log2(k)个,从后k-log2(k)个看log2(k-log2(k))个,在看剩下的,排序.第三个和第二个相似,尽可能用二分查找. 上面的值并非确切计算只是大致估计,如果k很大基本上释放的概率接近1/2. |
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. |
Then how can information be exchanged? 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? Thanks. |
There cannot be information exchange. 1. Closed, kept in the original location and position. No marking allowed. 2. Yes. They will not see each other, and don't know each other's results. |
Here is an idea: 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. 本贴由[QL]最后编辑于：2005-12-17 23:4:53 |
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. 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 本贴由[QL]最后编辑于：2005-12-17 23:2:17 |
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)) .... 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? 本贴由[QL]最后编辑于：2005-12-17 23:0:1 |
Wrong estimation, try again: 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) |
I mean the chance is bounded below by 1-ln(2). |
Great! The probability of 1 - ln2 = 0.3068... is very high, and I think it is the best possible. |
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. |
Good thought! But how can you expain the case that no >n loop but a lot of small loops? |
In that case, every criminal will get his box within n steps. |
Not quite understand your question, the boxes are numbered according to the problem, what do you mean by '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. |
He would dare to do that, not now. That is prisoner abuse. |
Great solution! |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |