保险箱和钥匙

野菜花 · 发表于 2005-4-13 22:45:53

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

fzy · 发表于 2005-4-14 02:33:11

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:20

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

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

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

野菜花 · 发表于 2005-4-14 05:00:52

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:13

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:27

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:27

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:59

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:29

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

野菜花 · 发表于 2005-4-14 21:22:39

Great job!

野菜花 · 发表于 2005-4-14 21:27:11

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

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

动态微博

保险箱和钥匙

回复：保险箱和钥匙

真是非常难。我觉得跟置换群有关。

回复：回复：保险箱和钥匙

My consideration.

回复：回复：回复：保险箱和钥匙

Some typ0...

A complete and simple solution

It is pretty pretty.[@};-][@};-]

Great job! [@};-][@};-]

好厉害，佩服！ [@};-][@};-]

动态微博

保 险 箱 和 钥 匙

回复：保 险 箱 和 钥 匙

真是非常难。我觉得跟置换群有关。

回复：回复：保 险 箱 和 钥 匙

My consideration.

回复：回复：回复：保 险 箱 和 钥 匙

Some typ0...

A complete and simple solution

It is pretty pretty.[@};-][@};-]

Great job! [@};-][@};-]

好 厉 害 ， 佩 服 ！ [@};-][@};-]

保险箱和钥匙

回复：保险箱和钥匙

回复：回复：保险箱和钥匙

回复：回复：回复：保险箱和钥匙

好厉害，佩服！ [@};-][@};-]