钥匙与锁的问题(1)
有N把钥匙和N把锁。每1把钥匙都只能开1把锁，每1把锁都只能由1把钥匙打开。
即钥匙与锁具有一一对应关系。
现在我们随机抽取$(N-1)$把钥匙，随机放进$(N-1)$个箱子里，每个箱子各放$1$把钥匙。
然后随机抽取$(N-1)$把锁，将$(N-1)$个箱子锁起来，每把锁各锁$1$个箱子。
（这些锁不需要钥匙就能锁上，但需要钥匙才能打开。）
现在我们要把所有的钥匙从箱子里取出来。
要打开一个箱子，有$2$种方案：
$1$、用钥匙开锁
$2$、暴力打开箱子
我们希望暴力打开箱子的次数尽量少。
问：不需要暴力打开箱子的概率是多少？需要暴力打开$k$个箱子的概率$p(k)$是多少？ fans总是出这种复杂度奇高的概率题，:L 我也觉得之前出的概率题难度太高，所以这次出一道容易一点的。
没想到wayne大牛的评价仍然是“复杂度奇高”啊。 3# KeyTo9_Fans
:lol 3# KeyTo9_Fans
不知道该如何理解这道题的随机性质。
貌似条件不足。
感觉需要给出一个确定的初始状态，即各个箱子与钥匙的拓扑排序关系。
于是就好分析 图中子环路的分布情况了。
还请帮我开导一下 猜一下，不需要暴力打开箱子的概率是$1/N$。 应该p(k)都是1/N 将剩余的钥匙也放进剩余的箱子中，用剩余的锁锁好。
将所有的锁编号，相应的钥匙也编相同的号。
将箱子按锁的编号从小到大顺序排列。
那么箱子中的钥匙编号按箱子的顺序排列成一个关于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$ 当每个数字独立成环，即N个环。那么概率=1/(N!)
即$p(0)=1/N$
$p(N-1)=1/(N!)$ p(k)等于N个数字排列形成k+1个环的概率
页:
[1]
2