珍珠湾ART

标题: 保险箱和钥匙 [打印本页]

作者: 野菜花 时间: 2005-4-13 22:45
标题: 保险箱和钥匙

10 个保险箱， 10把钥匙，每把钥匙恰好能开一个保险箱，每个保险箱也只有一把钥匙能打开。钥匙锁在保险箱里，每个保险箱里一把钥匙，方法是随机的。先打破 3 个箱子取出钥匙。问其余的保险箱均能用钥匙打开的概率是多少？

作者: fzy 时间: 2005-4-14 02:33
标题: 回复：保险箱和钥匙

The problem looks very hard. I have only this silly method, and have not yet got the number.

Let P(n,k) be the probability of open all n safes with k keys. We need P(10,3).

P(n,1) = 1/n.

P(n,2) = [2*(n-2)/C(n,2)]*P(n-2,1) + [C(n-2,2)/C(n,2)]*P(n-2,2)

P(n,3) = [3*(n-3)/C(n,3)]*P(n-3,1) + [3*C(n-3,2)/C(n,3)]*P(n-3,2) + [C(n-3,3)/C(n,3)]*P(n-3,3)

From these recursive relations we should be able to get P(10,3). Need to write a program to calculate the number.

作者: 乱弹 时间: 2005-4-14 02:56
标题: 真是非常难。我觉得跟置换群有关。

能开的情况是最多有三个轮换，并且每个轮换里都有一个被抓出来。这样是能直接计算出来的。可惜我对这些组合关系不熟悉，要做的话，又要查书，几乎每步都要仔细验证，非一时半会可以做好。

也许野菜花有简单办法吧。

不管怎样，这题目实在有意思。

作者: 野菜花 时间: 2005-4-14 05:00
标题: 回复：回复：保险箱和钥匙

In the original problem, in stead of 10 and 3, n and k are used just as you did in your solution.

In the solution i know, comjecture the answer first (the answer looks very simple), then use the induction.

Don't hurry, take your time, otherwise you guys would feel bored again.

作者: 乱弹 时间: 2005-4-14 06:31
标题: My consideration.

Let q(n,k) be the probability that not all safes can be opened, i.e., q(n,k)=1-p(n,k). Then in the total C(n,k) n! combinations, there are C(n,k) n!q(n,k) combinations that not all safes can be opened. For 1<=i <=n-k, there are C(n,i)i!(1-q(n-i, k))C(n-i, k) (n-i)! cases in which exactly i safes can not be opened (these i safes form some cycles...).

Therefore, we have:

C(n,k) n!q(n,k)=C(n,1)1!(1-q(n-1, k))C(n-1, k)(n-1)!+....+C(n, n-k)(1-q(k,k))C(k,k)k!.

Now we are left to prove by induction on n-k that q(n,k)=1-k/n, which can be done easily.

作者: fzy 时间: 2005-4-14 06:42
标题: 回复：回复：回复：保险箱和钥匙

It is k/n. I did use induction (and still hate it!) There should be a more beautiful proof for such a beautiful result.

I tried 置换群 and it does not work (for me) either.

作者: 乱弹 时间: 2005-4-14 06:56
标题: Some typ0...

C(n,k) n!q(n,k)=C(n,1)1!(1-q(n-1, k))C(n-1, k)(n-1)!+....+C(n, n-k)(n-k)!(1-q(k,k))C(k,k)k!.

I did use 置换群, but not much.

作者: fzy 时间: 2005-4-14 18:09
标题: A complete and simple solution

Still let P(n,k) be the probability of opening all n boxes given k keys. We first open one box and get another key. The probability of getting a new key (not already have) is (n-k)/n. So we have this simple recursive relation:

P(n,k) = k/n * P(n-1,k-1) + (n-k)/n * P(n-1,k)

From this and a double induction on n and k (DOUBLE! ) we get P(n,k) = k/n.

作者: 乱弹 时间: 2005-4-14 20:02
标题: It is pretty pretty.[@};-][@};-]

To save yourself from double induction, you can try it on n+k. Anyway, it is not important.

作者: 野菜花 时间: 2005-4-14 21:22
标题: Great job! [@};-][@};-]

Great job!

作者: 野菜花 时间: 2005-4-14 21:27
标题: 好厉害，佩服！ [@};-][@};-]

I thought this question could last a little longer. It seems I could not find any problems which can beat you

欢迎光临珍珠湾ART (http://www.zzwav.com/)