钥匙与锁的问题(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个环的概率