b***z
发帖数: 921 | 1 There are N boxes and N keys. Each key opens exactly one box. Suppose we
lock each key inside a random box. We pick a box at random and break it in
order to get the key. What is the probability that with that key we will be
able to open the rest of the boxes without having to break any of the
remaining ones? |
d********t
发帖数: 9628 | 2 飞机排座题，1/2
be
【在 b***z 的大作中提到】
: There are N boxes and N keys. Each key opens exactly one box. Suppose we
: lock each key inside a random box. We pick a box at random and break it in
: order to get the key. What is the probability that with that key we will be
: able to open the rest of the boxes without having to break any of the
: remaining ones?
|
b***z
发帖数: 921 | 3 答案是1/N,不知道如何得到的。
【在 d********t 的大作中提到】
: 飞机排座题，1/2
:
: be
|
b********3
发帖数: 13 | 4 be able to open the rest of the boxes without having to break any of the
remaining ones 等价于 任何钥匙都没有放在它所对应的盒子里 这个概率是 1/n [算
法：(n-1)!/n!] |
t****w
发帖数: 12 | 5 不应该是1-1/2！+1/3！-1/4！+。。。么？
【在 b********3 的大作中提到】
: be able to open the rest of the boxes without having to break any of the
: remaining ones 等价于 任何钥匙都没有放在它所对应的盒子里 这个概率是 1/n [算
: 法：(n-1)!/n!]
|
b********3
发帖数: 13 | 6 确实是我错了， 应该是1-1/1!+1/2!-1/3!+1/4!.....
【在 t****w 的大作中提到】
: 不应该是1-1/2！+1/3！-1/4！+。。。么？
|
a***n
发帖数: 423 | 7 拿到一把钥匙之后，要能打开其他所有的盒子，则盒子(b_1-b_n)和钥匙(k_1-k_n)的对
应以下的方法,
b_1,可以是k_2-k_n,所以n-1个选择,assume it is k_i1;
b_i1, 可以有n-2个选择，因为不能选k_1和k_i1, assume it is k_i2;
b_i2, 可以有n-3个选择，因为不能选k_1,k_i1和k_i2.
...
b_in-2, 可以有1个选择，因为不能选k-1,k_i1,k_i2,...,k_in-2
b_in-1, 可以有1个选择，就是k-1
上面的组合排列有(n-1)!个。
如果没有任何限制，组合排列是n!个
所以得到一个钥匙，打开其他所有钥匙的概率是(n-1)!/n!. |
t****w
发帖数: 12 | 8 确实，不能有loop，所以并不完全等价于“任何钥匙都没有放在它所对应的盒子里”。
【在 a***n 的大作中提到】
: 拿到一把钥匙之后，要能打开其他所有的盒子，则盒子(b_1-b_n)和钥匙(k_1-k_n)的对
: 应以下的方法,
: b_1,可以是k_2-k_n,所以n-1个选择,assume it is k_i1;
: b_i1, 可以有n-2个选择，因为不能选k_1和k_i1, assume it is k_i2;
: b_i2, 可以有n-3个选择，因为不能选k_1,k_i1和k_i2.
: ...
: b_in-2, 可以有1个选择，因为不能选k-1,k_i1,k_i2,...,k_in-2
: b_in-1, 可以有1个选择，就是k-1
: 上面的组合排列有(n-1)!个。
: 如果没有任何限制，组合排列是n!个
|
a***n
发帖数: 423 | 9 拿到一把钥匙之后，要能打开其他所有的盒子，则盒子(b_1-b_n)和钥匙(k_1-k_n)的对
应以下的方法,
b_1,可以是k_2-k_n,所以n-1个选择,assume it is k_i1;
b_i1, 可以有n-2个选择，因为不能选k_1和k_i1, assume it is k_i2;
b_i2, 可以有n-3个选择，因为不能选k_1,k_i1和k_i2.
...
b_in-2, 可以有1个选择，因为不能选k-1,k_i1,k_i2,...,k_in-2
b_in-1, 可以有1个选择，就是k-1
上面的组合排列有(n-1)!个。
如果没有任何限制，组合排列是n!个
所以得到一个钥匙，打开其他所有钥匙的概率是(n-1)!/n!. |
f****g
发帖数: 207 | 10 记得在哪里看到过这个题, 好像是50 most challenging probabiltiy question什么的.
印象中是说:
给盒子上号, 假设 Hi, i对应1-100
给钥匙上号, 假设 Yi, i对应1-100
且假设每个Y_i可以开对应的H_i
因为已经强行开了一个盒子了 H1, 所以你会得到一个Y2, 则可用该钥匙, 去开他所对
应的那个盒子H2, 这样又会得到一个Y3,依次类推, 有点像指针的感觉.
那么根据题目, 如果不需要再开的话, 那就是代表剩下的盒子和钥匙, 只会产生一个链.
举例: H1(Y2),H2(Y3),H3(Y4),H4(Y5),H5(Y1). 这个是符合题目要求的
但是假如说:
H1(Y2), H2(Y3),H3(Y1) | H4(Y5),H5(Y4)
就会出现两个链, 这样是不符合题目要求的.
所以你只需要算出, 不会出现多个链的prob是多少, 大概这样 |
|
|
t***l
发帖数: 3644 | 11 prod_{k=2}^n (k-1)/k = 1/n
be
【在 b***z 的大作中提到】
: There are N boxes and N keys. Each key opens exactly one box. Suppose we
: lock each key inside a random box. We pick a box at random and break it in
: order to get the key. What is the probability that with that key we will be
: able to open the rest of the boxes without having to break any of the
: remaining ones?
|
n****e
发帖数: 629 | 12 P(N)=(N-1)/N*P(N-1)=...=1/N*P(1)=1/N
be
【在 b***z 的大作中提到】
: There are N boxes and N keys. Each key opens exactly one box. Suppose we
: lock each key inside a random box. We pick a box at random and break it in
: order to get the key. What is the probability that with that key we will be
: able to open the rest of the boxes without having to break any of the
: remaining ones?
|
T*****u
发帖数: 7103 | 13 n个node，随即生成directed graph，没有island得概率；大概也可以用markov
model做 |
s****i
发帖数: 475 | 14 能开别的箱子的琐的前提就是自己的钥匙不能放在自己的里面
假设有N个盒子，第一个盒子必须要放除第一个盒子意外的key，也就是(N-1)种可能，
第二个盒子只能放剩下的（N-2），以此类推，所以就是(N-1)!/N! = 1/N。
用了N=2和3试了，应该是对的。。。 |
l******8
发帖数: 1691 | 15 1/N
be
【在 b***z 的大作中提到】
: There are N boxes and N keys. Each key opens exactly one box. Suppose we
: lock each key inside a random box. We pick a box at random and break it in
: order to get the key. What is the probability that with that key we will be
: able to open the rest of the boxes without having to break any of the
: remaining ones?
|
l******8
发帖数: 1691 | 16 这个很简单啊。
如果第一个盒子的钥匙正好在最后一个盒子里，那么必然可以全打开。
如果第一个盒子的钥匙不在最后一个盒子里，比如是第m个盒子，m!=N，那么到了m个盒
子，线索就断了，开不下去了。
所以只要计算第一个盒子的钥匙在最后一个盒子的概率，显然是1/N啊。
be
【在 b***z 的大作中提到】
: There are N boxes and N keys. Each key opens exactly one box. Suppose we
: lock each key inside a random box. We pick a box at random and break it in
: order to get the key. What is the probability that with that key we will be
: able to open the rest of the boxes without having to break any of the
: remaining ones?
|
d******e
发帖数: 285 | 17 It is equal to the probability that none of the keys is in its own box.
which is (N-1) ! / N ! = 1/N.
More like a brain teaser rather than probability question.
【在 l******8 的大作中提到】
: 这个很简单啊。
: 如果第一个盒子的钥匙正好在最后一个盒子里，那么必然可以全打开。
: 如果第一个盒子的钥匙不在最后一个盒子里，比如是第m个盒子，m!=N，那么到了m个盒
: 子，线索就断了，开不下去了。
: 所以只要计算第一个盒子的钥匙在最后一个盒子的概率，显然是1/N啊。
:
: be
|
l*********g
发帖数: 1899 | 18 记得去年9月，我在这个版做过一道类似的题目： http://www.mitbbs.com/article/Quant/31368795_3.html
其实目前以下这道题就是以上提到的去年那道题的其中一种情况，就是去年那道题中当
k=1的时候的解。
be
【在 b***z 的大作中提到】
: There are N boxes and N keys. Each key opens exactly one box. Suppose we
: lock each key inside a random box. We pick a box at random and break it in
: order to get the key. What is the probability that with that key we will be
: able to open the rest of the boxes without having to break any of the
: remaining ones?
|
t********k
发帖数: 48 | 19 兄弟的名字真好
【在 d********t 的大作中提到】
: 飞机排座题，1/2
:
: be
|
s*******n
发帖数: 740 | 20 你这完全是瞎蒙的。当不是loop的时候，你如何定义“最后的盒子”？ 只有在能全部
打开的情况下，”最后的盒子“才是well-defined。
【在 l******8 的大作中提到】
: 这个很简单啊。
: 如果第一个盒子的钥匙正好在最后一个盒子里，那么必然可以全打开。
: 如果第一个盒子的钥匙不在最后一个盒子里，比如是第m个盒子，m!=N，那么到了m个盒
: 子，线索就断了，开不下去了。
: 所以只要计算第一个盒子的钥匙在最后一个盒子的概率，显然是1/N啊。
:
: be
|
|
|
l******8
发帖数: 1691 | 21 是我说得不够全，不是瞎蒙。你提出这个问题是有道理的，同时也是可以解决的。完整
解释起来太麻烦，又没人给我发工钱，说个大概方向该补的洞还有很多没补，你说的这
个还不是最大的洞。
【在 s*******n 的大作中提到】
: 你这完全是瞎蒙的。当不是loop的时候，你如何定义“最后的盒子”？ 只有在能全部
: 打开的情况下，”最后的盒子“才是well-defined。
|
c****e
发帖数: 2127 | 22 这个递归解释很好理解
【在 n****e 的大作中提到】
: P(N)=(N-1)/N*P(N-1)=...=1/N*P(1)=1/N
:
: be
|
O***T
发帖数: 114 | 23 不能有任何钥匙刚好放在自己的盒子里
所以直接 (N-1)/N * (N-2)/(N-1) * ... * 1/2 = 1/N 不就完了么 |
N*******3
发帖数: 2589 | 24
答案是对的，但思路上有个问题。
“b_i1, 可以有n-2个选择，因为不能选k_1和k_i1”
b_i1为什么不能选k_1 ? 又没违规。
比如假设abcd四个钥匙对应ABCD四个盒子，你的这个推论过程就是：
a不能在A里，只能在BCD (正确)
b不能B里，只能在CD。但是b显然可以在A里，所以还是有三个选择，怎么解释？
【在 a***n 的大作中提到】
: 拿到一把钥匙之后，要能打开其他所有的盒子，则盒子(b_1-b_n)和钥匙(k_1-k_n)的对
: 应以下的方法,
: b_1,可以是k_2-k_n,所以n-1个选择,assume it is k_i1;
: b_i1, 可以有n-2个选择，因为不能选k_1和k_i1, assume it is k_i2;
: b_i2, 可以有n-3个选择，因为不能选k_1,k_i1和k_i2.
: ...
: b_in-2, 可以有1个选择，因为不能选k-1,k_i1,k_i2,...,k_in-2
: b_in-1, 可以有1个选择，就是k-1
: 上面的组合排列有(n-1)!个。
: 如果没有任何限制，组合排列是n!个
|
N*******3
发帖数: 2589 | 25
将这个问题抽象为：“能开别的箱子的琐的前提就是自己的钥匙不能放在自己的里面”
是不对的。其实这个问题的要求更严格。否则答案也不是1/N。我之前也以为要这么抽
象，得出的结论就很矛盾。
正确的抽象不仅要钥匙都不在自己的盒子里，而且要是唯一一个链，不能是两个或以上
的链。上面fbwang的回复很好地说明了这个问题。
比如ABCD四个盒子对应abcd四个钥匙。
假设四个盒子不动，那么dabc就是个成功的排列，但是，badc这个排列，虽然满足了“
自己的钥匙不能放在自己的里面”的条件，但是却不能成功打开所有盒子，因为有两个
链。
【在 s****i 的大作中提到】
: 能开别的箱子的琐的前提就是自己的钥匙不能放在自己的里面
: 假设有N个盒子，第一个盒子必须要放除第一个盒子意外的key，也就是(N-1)种可能，
: 第二个盒子只能放剩下的（N-2），以此类推，所以就是(N-1)!/N! = 1/N。
: 用了N=2和3试了，应该是对的。。。
|
L*******t
发帖数: 2385 | 26 他其实是个玉面书生
【在 t********k 的大作中提到】
: 兄弟的名字真好
|
