钥匙与锁的问题(1)

KeyTo9_Fans

有$N$把钥匙和$N$把锁。 每$1$把钥匙都只能开$1$把锁，每$1$把锁都只能由$1$把钥匙打开。 即钥匙与锁具有一一对应关系。 现在我们随机抽取$(N-1)$把钥匙，随机放进$(N-1)$个箱子里，每个箱子各放$1$把钥匙。 然后随机抽取$(N-1)$把锁，将$(N-1)$个箱子锁起来，每把锁各锁$1$个箱子。 （这些锁不需要钥匙就能锁上，但需要钥匙才能打开。） 现在我们要把所有的钥匙从箱子里取出来。 要打开一个箱子，有$2$种方案： $1$、用钥匙开锁 $2$、暴力打开箱子 我们希望暴力打开箱子的次数尽量少。 问：不需要暴力打开箱子的概率是多少？需要暴力打开$k$个箱子的概率$p(k)$是多少？

wayne

fans总是出这种复杂度奇高的概率题，

KeyTo9_Fans

我也觉得之前出的概率题难度太高，所以这次出一道容易一点的。 没想到wayne大牛的评价仍然是“复杂度奇高”啊。

wayne

3# KeyTo9_Fans

wayne

3# KeyTo9_Fans 不知道该如何理解这道题的随机性质。 貌似条件不足。 感觉需要给出一个确定的初始状态，即各个箱子与钥匙的拓扑排序关系。 于是就好分析 图中子环路的分布情况了。 还请帮我开导一下

xbtianlang

猜一下，不需要暴力打开箱子的概率是$1/N$。

mathe

应该p(k)都是1/N

056254628

将剩余的钥匙也放进剩余的箱子中，用剩余的锁锁好。 将所有的锁编号，相应的钥匙也编相同的号。 将箱子按锁的编号从小到大顺序排列。 那么箱子中的钥匙编号按箱子的顺序排列成一个关于1至N的数字排列。 一个排列就代表一种情况。 比如：1号箱子（锁）中的钥匙开5号箱子的锁， 5号箱子（锁）中的钥匙开8号箱子的锁， ...... 12号箱子（锁）中的钥匙开1号箱子的锁。 这样1,5,......,12,1就形成了一个数字环。 1至N的一个数字排列中有k个环，取出所有的钥匙，就需要暴力打开k-1个箱子。 ------------------------------------------------------------------------------------------------------- 不要暴力打开，就是1至N的一个数字排列中只有1个环。 一个环一共有$(N!)/N$种情况。所以概率=$((N!)/N)/(N!)=1/N$

056254628

当每个数字独立成环，即N个环。那么概率=1/(N!) 即$p(0)=1/N$ $p(N-1)=1/(N!)$

056254628

p(k)等于N个数字排列形成k+1个环的概率