f*******s
发帖数: 57 | 1 不是面试题，一个国内的朋友问的，我不知道我的答案是否对，发到这里可以和牛人确
认一下:)
题目如下：
有7个箱子，每个箱子的钥匙随机锁在7个箱子里面的任意一个，随机砸开一个箱子，问
能打开所有箱子的概率是多少？（任意一个箱子可以没有任何钥匙或有一把或者多把钥
匙）。 |
w******g
发帖数: 313 | 2 1/n吧
【在 f*******s 的大作中提到】
: 不是面试题，一个国内的朋友问的，我不知道我的答案是否对，发到这里可以和牛人确
: 认一下:)
: 题目如下：
: 有7个箱子，每个箱子的钥匙随机锁在7个箱子里面的任意一个，随机砸开一个箱子，问
: 能打开所有箱子的概率是多少？（任意一个箱子可以没有任何钥匙或有一把或者多把钥
: 匙）。
|
p*******o
发帖数: 20 | 3 恩，1/n.
【在 w******g 的大作中提到】
: 1/n吧
|
f*******s
发帖数: 57 | 4 我是用recursion做的，假设有k把钥匙能打开n个盒子的概率是f(n,k)
可以证明 f(n,k)=k/n，原题实际上就是f(n,1)；感觉应该有更简单的做法
【在 w******g 的大作中提到】
: 1/n吧
|
w******g
发帖数: 313 | 5 我和你的做法完全一样
【在 f*******s 的大作中提到】
: 我是用recursion做的，假设有k把钥匙能打开n个盒子的概率是f(n,k)
: 可以证明 f(n,k)=k/n，原题实际上就是f(n,1)；感觉应该有更简单的做法
|
f*******s
发帖数: 57 | 6 看来就这样了，多谢。
我最开始的方法还复杂点 number of trees with n nodes / n^(n-1) = n^(n-2) / n^
(n-1) = 1/ n
这个更难解释。
【在 w******g 的大作中提到】
: 我和你的做法完全一样
|
a***n
发帖数: 423 | 7 Did you use Cayley's formula? Could you please explain it?
n^
【在 f*******s 的大作中提到】
: 看来就这样了，多谢。
: 我最开始的方法还复杂点 number of trees with n nodes / n^(n-1) = n^(n-2) / n^
: (n-1) = 1/ n
: 这个更难解释。
|
y******6
发帖数: 61 | 8 可以先固定路径，在根据对称性来。
固定Box1 是我们第一个打破的，然后固定一个连锁打破的路径。就假设这个顺序是1，
2，3，。。。n
我们知道，要能够解锁的充分必要条件是第k个箱子要有第k+1个箱子的钥匙。
所以，第n个箱子的钥匙必须在（1，2，。。n-1）；。。。第K个箱子的钥匙必须在（1
，2，。。，k-1）。。
一共有（n-1）！组合满足条件。
共有 n！种组合，所以概率是1／n 如果我们固定一个路径。
根据对称性，或者全概率公式，不固定路径的概率还是1／n。
【在 f*******s 的大作中提到】
: 不是面试题，一个国内的朋友问的，我不知道我的答案是否对，发到这里可以和牛人确
: 认一下:)
: 题目如下：
: 有7个箱子，每个箱子的钥匙随机锁在7个箱子里面的任意一个，随机砸开一个箱子，问
: 能打开所有箱子的概率是多少？（任意一个箱子可以没有任何钥匙或有一把或者多把钥
: 匙）。
|
w****r
发帖数: 67 | 9 What if there are multiple duplicated keys to one box?
What if there are some boxes without keys? |
w******g
发帖数: 313 | 10 这是考虑过你说的问题的答案啊
【在 w****r 的大作中提到】
: What if there are multiple duplicated keys to one box?
: What if there are some boxes without keys?
|
|
|
w****r
发帖数: 67 | 11 举例来说：
综合所有箱子里的所有钥匙，放在一起，
其中有3把可以开 3 号箱子，
没有钥匙 能开4号箱子，
（即假设不是每个箱子都有一把配对的钥匙）
n个箱子里可能总共有 2n 把钥匙
n个箱子里也可能总共只有 n-2 把钥匙
楼主的问题就不是那么简单了
【在 w******g 的大作中提到】
: 这是考虑过你说的问题的答案啊
|
y******6
发帖数: 61 | 12 all included.
【在 w****r 的大作中提到】
: What if there are multiple duplicated keys to one box?
: What if there are some boxes without keys?
|
f*******g
发帖数: 79 | 13 The key of the first box should not be in the first box then we have the
probability n-1/n. The key of the first box should not be in the second box
we manage to open then. this process go on and on, we have
(n-1/n)(n-2/n-1)(n-3/n-2)...(1/2)=1/n |
y******6
发帖数: 61 | 14 the key of the first box could be in the first box to make all boxes open if
you just break the first box firstly.
box
【在 f*******g 的大作中提到】
: The key of the first box should not be in the first box then we have the
: probability n-1/n. The key of the first box should not be in the second box
: we manage to open then. this process go on and on, we have
:
: (n-1/n)(n-2/n-1)(n-3/n-2)...(1/2)=1/n
|
M****n
发帖数: 46 | |
m********l
发帖数: 4394 | 16 这好像是Birthday problem的一种吧
不是1/n
...
看糊涂了.
只能砸一个, 但是要开所有箱子?
【在 f*******s 的大作中提到】
: 不是面试题，一个国内的朋友问的，我不知道我的答案是否对，发到这里可以和牛人确
: 认一下:)
: 题目如下：
: 有7个箱子，每个箱子的钥匙随机锁在7个箱子里面的任意一个，随机砸开一个箱子，问
: 能打开所有箱子的概率是多少？（任意一个箱子可以没有任何钥匙或有一把或者多把钥
: 匙）。
|
y******6
发帖数: 61 | 17 可以发到joke 版。。。
【在 M****n 的大作中提到】
: (1/7)^7
|
o**o
发帖数: 3964 | 18 不符合题意。
（1
【在 y******6 的大作中提到】
: 可以先固定路径，在根据对称性来。
: 固定Box1 是我们第一个打破的，然后固定一个连锁打破的路径。就假设这个顺序是1，
: 2，3，。。。n
: 我们知道，要能够解锁的充分必要条件是第k个箱子要有第k+1个箱子的钥匙。
: 所以，第n个箱子的钥匙必须在（1，2，。。n-1）；。。。第K个箱子的钥匙必须在（1
: ，2，。。，k-1）。。
: 一共有（n-1）！组合满足条件。
: 共有 n！种组合，所以概率是1／n 如果我们固定一个路径。
: 根据对称性，或者全概率公式，不固定路径的概率还是1／n。
|
y******6
发帖数: 61 | 19 why?
【在 o**o 的大作中提到】
: 不符合题意。
:
: （1
|
p*******o
发帖数: 20 | 20 ?? how?
if
【在 y******6 的大作中提到】
: the key of the first box could be in the first box to make all boxes open if
: you just break the first box firstly.
:
: box
|
|
|
y******6
发帖数: 61 | 21 If all keys are in one box and you happen to break that box.
【在 p*******o 的大作中提到】
: ?? how?
:
: if
|
p*******o
发帖数: 20 | 22 哦，我理解的是一个箱子放一个钥匙，而不是所有钥匙放在一个箱子里面。题目难道是
后一种？
【在 y******6 的大作中提到】
: If all keys are in one box and you happen to break that box.
|
y******6
发帖数: 61 | 23 看原题最后一句话。
【在 p*******o 的大作中提到】
: 哦，我理解的是一个箱子放一个钥匙，而不是所有钥匙放在一个箱子里面。题目难道是
: 后一种？
|
o**o
发帖数: 3964 | 24 ”充分必要“不等价
【在 y******6 的大作中提到】
: why?
|
y******6
发帖数: 61 | 25 什么 充分必要的，不要这么brief 好不好。
【在 o**o 的大作中提到】
: ”充分必要“不等价
|
f*******g
发帖数: 79 | 26 assume only n boxes out of the seven have keys. the problem of opening all
boxes is the same problem of finding keys. The keys for the empty boxes are
irrelevant because once we open all the boxes with keys we can open all
empty boxes. The probability to open n boxes with one key in each boxes is 1
/n. So the probability to open 7 boxes is (n/7)(1/n)=1/7, which is
independent of n. So the answer is 1/7 |
y******6
发帖数: 61 | 27 搞笑请到joke版。
are
1
【在 f*******g 的大作中提到】
: assume only n boxes out of the seven have keys. the problem of opening all
: boxes is the same problem of finding keys. The keys for the empty boxes are
: irrelevant because once we open all the boxes with keys we can open all
: empty boxes. The probability to open n boxes with one key in each boxes is 1
: /n. So the probability to open 7 boxes is (n/7)(1/n)=1/7, which is
: independent of n. So the answer is 1/7
|
o**o
发帖数: 3964 | 28 我觉得从某个固定的盒子出发能解锁的所有path等概率这个隐含假设不一定对。当然答
案可能是对的。脑子里凭空想像了一下，只有3个盒子的情况全排列是27个pattern, 从
任选的一个盒子出发能走通的好像是9个
【在 y******6 的大作中提到】
: 什么 充分必要的，不要这么brief 好不好。
|
l******u
发帖数: 1174 | 29 答案应该比 1/n 小得多。
【在 m********l 的大作中提到】
: 这好像是Birthday problem的一种吧
: 不是1/n
: ...
: 看糊涂了.
: 只能砸一个, 但是要开所有箱子?
|
f*********5
发帖数: 367 | 30 “共有n!种组合”似乎是不对的。打破box1, 固定了一个连锁打破路径后，我们只关心
箱子2,3,..., n的钥匙存放。满足要求的有(n-1)!种存放方法，但这n-1把钥匙共有n^(
n-1)种存放可能性，如果一个箱子里可以放任意把钥匙的话。
（1
【在 y******6 的大作中提到】
: 可以先固定路径，在根据对称性来。
: 固定Box1 是我们第一个打破的，然后固定一个连锁打破的路径。就假设这个顺序是1，
: 2，3，。。。n
: 我们知道，要能够解锁的充分必要条件是第k个箱子要有第k+1个箱子的钥匙。
: 所以，第n个箱子的钥匙必须在（1，2，。。n-1）；。。。第K个箱子的钥匙必须在（1
: ，2，。。，k-1）。。
: 一共有（n-1）！组合满足条件。
: 共有 n！种组合，所以概率是1／n 如果我们固定一个路径。
: 根据对称性，或者全概率公式，不固定路径的概率还是1／n。
|
|
|
s***e
发帖数: 267 | 31 Nice. I was thinking in terms of loops, the same result but not as clean.
are
1
【在 f*******g 的大作中提到】
: assume only n boxes out of the seven have keys. the problem of opening all
: boxes is the same problem of finding keys. The keys for the empty boxes are
: irrelevant because once we open all the boxes with keys we can open all
: empty boxes. The probability to open n boxes with one key in each boxes is 1
: /n. So the probability to open 7 boxes is (n/7)(1/n)=1/7, which is
: independent of n. So the answer is 1/7
|
l******u
发帖数: 1174 | 32 按你的意思，number of trees with n nodes = n^(n-2)?
你怎样定义不同的tree？你试过n = 2， n = 3 或 n = 4吗？
n^
【在 f*******s 的大作中提到】
: 看来就这样了，多谢。
: 我最开始的方法还复杂点 number of trees with n nodes / n^(n-1) = n^(n-2) / n^
: (n-1) = 1/ n
: 这个更难解释。
|
l******u
发帖数: 1174 | 33 首先，他没定义什么是一个unique的组合。对n个箱子来说，n个钥匙有n^n种放法。他
可能将其中一些组合算成一个unique的组合了。
从他的（n-1）！的推导来看，他可能用固定路径来定义unique的组合。如何用“固定
路径”将 n^n 种放法map到“n!种组合”，他没有说明。
其实，算一下n=3的组合，就知道原题的答案不是1/3.
^(
（1
【在 f*********5 的大作中提到】
: “共有n!种组合”似乎是不对的。打破box1, 固定了一个连锁打破路径后，我们只关心
: 箱子2,3,..., n的钥匙存放。满足要求的有(n-1)!种存放方法，但这n-1把钥匙共有n^(
: n-1)种存放可能性，如果一个箱子里可以放任意把钥匙的话。
:
: （1
|
s***e
发帖数: 267 | 34 应该是1/N
你仔细看看firstbing 的SOLUTION
【在 l******u 的大作中提到】
: 首先，他没定义什么是一个unique的组合。对n个箱子来说，n个钥匙有n^n种放法。他
: 可能将其中一些组合算成一个unique的组合了。
: 从他的（n-1）！的推导来看，他可能用固定路径来定义unique的组合。如何用“固定
: 路径”将 n^n 种放法map到“n!种组合”，他没有说明。
: 其实，算一下n=3的组合，就知道原题的答案不是1/3.
:
: ^(
: （1
|
f*********5
发帖数: 367 | 35 他这个是对的，你直接google "number of trees with n nodes"就能看到你想看的了
，包括different trees的定义。不过我觉得wiki上那个tree的定义和这里的不太一样
，但可能有一一映射，所以和这里需要的different trees的数量似乎是一致的。n=4的
我也懒得求证了。
【在 l******u 的大作中提到】
: 按你的意思，number of trees with n nodes = n^(n-2)?
: 你怎样定义不同的tree？你试过n = 2， n = 3 或 n = 4吗？
:
: n^
|
f*********5
发帖数: 367 | 36 除了上面我说过的他在固定路径后，所有可能分布是n^(n-1)而非n!之外，我觉得用固
定路径来考虑也是不合适的，因为不同路径并非独立的。比如假如总共有n条可能路径
，但却总有且只有一条能走通，概率均等，那么你说固定某条路径后，这条路径能走通
的概率是1/n，然后想推广说存在能走通的路径的概率是1/n，这明显是不对的，因为有
且只有一条能走通，概率是1.
但是他的结果1/n应该是对的.N=3的时候，假如先砸破box1，那么box2和box3对应的两
把钥匙有9种分布可能，其中有3种可以让我们打开所有box: 两把钥匙都在1；box2的钥
匙在box1里, BOX3的钥匙在box2了；Box3的钥匙在Box1里，Box2的钥匙在Box3里，所以
概率还是1/3;
【在 l******u 的大作中提到】
: 首先，他没定义什么是一个unique的组合。对n个箱子来说，n个钥匙有n^n种放法。他
: 可能将其中一些组合算成一个unique的组合了。
: 从他的（n-1）！的推导来看，他可能用固定路径来定义unique的组合。如何用“固定
: 路径”将 n^n 种放法map到“n!种组合”，他没有说明。
: 其实，算一下n=3的组合，就知道原题的答案不是1/3.
:
: ^(
: （1
|
w******g
发帖数: 313 | 37 我完全没看懂你那段概率是1的话说的是啥意思
【在 f*********5 的大作中提到】
: 除了上面我说过的他在固定路径后，所有可能分布是n^(n-1)而非n!之外，我觉得用固
: 定路径来考虑也是不合适的，因为不同路径并非独立的。比如假如总共有n条可能路径
: ，但却总有且只有一条能走通，概率均等，那么你说固定某条路径后，这条路径能走通
: 的概率是1/n，然后想推广说存在能走通的路径的概率是1/n，这明显是不对的，因为有
: 且只有一条能走通，概率是1.
: 但是他的结果1/n应该是对的.N=3的时候，假如先砸破box1，那么box2和box3对应的两
: 把钥匙有9种分布可能，其中有3种可以让我们打开所有box: 两把钥匙都在1；box2的钥
: 匙在box1里, BOX3的钥匙在box2了；Box3的钥匙在Box1里，Box2的钥匙在Box3里，所以
: 概率还是1/3;
|
f*********5
发帖数: 367 | 38 我是说，即使固定任何一定路径，能到达终点的概率是1/n，都不能说明存在到达终点
路径的概率是1/n，这两样没有啥联系。
【在 w******g 的大作中提到】
: 我完全没看懂你那段概率是1的话说的是啥意思
|
l******u
发帖数: 1174 | 39 firstbing 解的是另一个题吧 -- 每个箱子里只有一把钥匙。那个题比较容易。
【在 s***e 的大作中提到】
: 应该是1/N
: 你仔细看看firstbing 的SOLUTION
|
l******u
发帖数: 1174 | 40 给个link？
即使那个公式是对的，也不能用在此处 -- unique tree 的定义不一样。
【在 f*********5 的大作中提到】
: 他这个是对的，你直接google "number of trees with n nodes"就能看到你想看的了
: ，包括different trees的定义。不过我觉得wiki上那个tree的定义和这里的不太一样
: ，但可能有一一映射，所以和这里需要的different trees的数量似乎是一致的。n=4的
: 我也懒得求证了。
|
|
|
s*******0
发帖数: 3461 | 41 来了 才发现啊 纽约还是很大 比上海繁华的地方多很多 呵呵 |
