新囚犯问题

constant · 发表于 2005-12-15 21:20:51

难度：+++

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

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

QFT · 发表于 2005-12-16 04:05:26

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

constant · 发表于 2005-12-16 04:43:46

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

sadfsdfsdfsd · 发表于 2005-12-16 10:11:14

第一个人看前k个盒子,然后排序. 第二个人从前k个盒子看log2(k)个(二分查找),从后k个盒子看k-log2(k)个,第三个人从前k个盒子看log2(k)个,从后k-log2(k)个看log2(k-log2(k))个,在看剩下的,排序.第三个和第二个相似,尽可能用二分查找.

上面的值并非确切计算只是大致估计,如果k很大基本上释放的概率接近1/2.

QL · 发表于 2005-12-16 14:23:21

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.

constant · 发表于 2005-12-16 16:15:36

Reordering is not allowed

IQ75 · 发表于 2005-12-17 00:21:03

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.

constant · 发表于 2005-12-17 01:15:20

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.

QL · 发表于 2005-12-18 06:19:51

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

QL · 发表于 2005-12-18 06:25:08

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

QL · 发表于 2005-12-18 06:58: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

QL · 发表于 2005-12-18 16:01:09

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)

QL · 发表于 2005-12-18 16:17:33

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

constant · 发表于 2005-12-18 21:40:15

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

QL · 发表于 2005-12-18 22:42:10

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.

IQ75 · 发表于 2005-12-19 22:09:25

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

QFT · 发表于 2005-12-19 22:50:16

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

QL · 发表于 2005-12-20 05:07:26

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

QL · 发表于 2005-12-20 06:12:09

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

QFT · 发表于 2005-12-20 06:39:22

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

QL · 发表于 2005-12-20 14:31:59

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

QFT · 发表于 2005-12-20 20:25:25

Great solution!

		自动登录	找回密码
密码			立即注册

动态微博

新囚犯问题

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

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

回复：新囚犯问题

回复：新囚犯问题

Reordering is not allowed

回复：新囚犯问题

回复：回复：新囚犯问题

回复：新囚犯问题

回复：回复：新囚犯问题

回复：回复：回复：新囚犯问题

回复：回复：回复：回复：新囚犯问题

回复：回复：回复：回复：回复：新囚犯问题

回复：回复：回复：回复：回复：回复：新囚犯问题

回复：新囚犯问题

A question

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

回复：A question

回复：what if boxes are mixed up? as thrown back to b

回复：回复：what if boxes are mixed up?

回复：回复：回复：what if boxes are mixed up?

we like to discourage prisoners.[:B][:B]

动态微博

新囚犯问题

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

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

回复：新囚犯问题

回复：新囚犯问题

Reordering is not allowed

回复：新囚犯问题

回复：回复：新囚犯问题

回复：新囚犯问题

回复：回复：新囚犯问题

回复：回复：回复：新囚犯问题

回复：回复：回复：回复：新囚犯问题

回复：回复：回复：回复：回复：新囚犯问题

回复：回复：回复：回复：回复：回复：新囚犯问题

回复：新囚犯问题

A question

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

回复：A question

回复：what if boxes are mixed up? as thrown back to b

回复：回复：what if boxes are mixed up?

回复：回复：回复：what if boxes are mixed up?

we like to discourage prisoners.[:B][:B]

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