a**********n
发帖数: 59 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: fcwrme (fcwrme), 信区: JobHunting
标 题: 一道概率踢 求解
发信站: BBS 未名空间站 (Fri Sep 5 22:41:20 2014, 美东)
The keys to n boxes are placed randomly in the boxes, one per box, The boxes
are closed, which locks them. I would like to know the probability that
breaking open k random boxes will allow all the remaining boxes to be
unlocked. Could you help me please? |
l*********g
发帖数: 1899 | 2 此概率 = 1/(n-k+1)，并且：当 n 是偶数时，k 至少是 n/2；当 n 是奇数时，k 至少
是 1+(n-1)/2
boxes
【在 a**********n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: fcwrme (fcwrme), 信区: JobHunting
: 标 题: 一道概率踢 求解
: 发信站: BBS 未名空间站 (Fri Sep 5 22:41:20 2014, 美东)
: The keys to n boxes are placed randomly in the boxes, one per box, The boxes
: are closed, which locks them. I would like to know the probability that
: breaking open k random boxes will allow all the remaining boxes to be
: unlocked. Could you help me please?
|
l*********g
发帖数: 1899 | 3 随便举个例子，如果n=11，k如果等于5,5个钥匙即使全中，怎么开剩下的6个boxes（题
目假设钥匙都是一对一）？ |
d********t
发帖数: 9628 | 4 绿皮书原题
boxes
【在 a**********n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: fcwrme (fcwrme), 信区: JobHunting
: 标 题: 一道概率踢 求解
: 发信站: BBS 未名空间站 (Fri Sep 5 22:41:20 2014, 美东)
: The keys to n boxes are placed randomly in the boxes, one per box, The boxes
: are closed, which locks them. I would like to know the probability that
: breaking open k random boxes will allow all the remaining boxes to be
: unlocked. Could you help me please?
|
l*********g
发帖数: 1899 | 5 我啥皮的书都没有看过。
这种题目其实有经验的都知道，面试官就是expect应试者几分钟内作答的。基本上繁复
公式计算是多余的。我就是数数手指头然后给个答案就是了。
【在 d********t 的大作中提到】
: 绿皮书原题
:
: boxes
|
a**********n
发帖数: 59 | 6 k doesnt need to be >= n/2, k could equal to 1 if for (i=1:n-1) box i has
the key for box i+1; then you only need to break box1, and all the boxes
would be opened by the key contained in the previous box
【在 l*********g 的大作中提到】
: 随便举个例子，如果n=11，k如果等于5,5个钥匙即使全中，怎么开剩下的6个boxes（题
: 目假设钥匙都是一对一）？
|
d********t
发帖数: 9628 | 7 绿皮书都是分钟题
【在 l*********g 的大作中提到】
: 我啥皮的书都没有看过。
: 这种题目其实有经验的都知道，面试官就是expect应试者几分钟内作答的。基本上繁复
: 公式计算是多余的。我就是数数手指头然后给个答案就是了。
|
a**********n
发帖数: 59 | 8 not quite right... when n=3 and k=1, the probability should be 1/6
【在 l*********g 的大作中提到】
: 此概率 = 1/(n-k+1)，并且：当 n 是偶数时，k 至少是 n/2；当 n 是奇数时，k 至少
: 是 1+(n-1)/2
:
: boxes
|
w*******x
发帖数: 489 | 9 k/n.
you can Google the solution.
boxes
【在 a**********n 的大作中提到】
: not quite right... when n=3 and k=1, the probability should be 1/6
|
t*****l
发帖数: 1 | |
|
|
s****o
发帖数: 11 | 11 只要被爆破的盒子的钥匙没有全部被拿到，就能继续打开盒子。所以成功的时候最后一个
被打开的盒子里面装的是爆破的k个盒子其中之一的钥匙，概率即k/n |
l*********g
发帖数: 1899 | 12 这个看起来是你思路的一部分。
或者你把最终概率的结果，例如它的表达式写写？这样我能更多地了解你的whole idea。
【在 a**********n 的大作中提到】
: k doesnt need to be >= n/2, k could equal to 1 if for (i=1:n-1) box i has
: the key for box i+1; then you only need to break box1, and all the boxes
: would be opened by the key contained in the previous box
|
l*********g
发帖数: 1899 | 13 1/6也不对，应该是1/3。
我之前对题意的理解有误，随之的表达式也有误。
按照网上答案的意思，举n=3, k=1的例子，在P(3,3)的6种排列中，只有其中2种排列在
k=1的时候will allow all the remaining boxes to be unlocked，即概率是 2/6 = 1
/3。
【在 a**********n 的大作中提到】
: not quite right... when n=3 and k=1, the probability should be 1/6
|
L*******t
发帖数: 2385 | 14 牛啊
1
【在 l*********g 的大作中提到】
: 1/6也不对，应该是1/3。
: 我之前对题意的理解有误，随之的表达式也有误。
: 按照网上答案的意思，举n=3, k=1的例子，在P(3,3)的6种排列中，只有其中2种排列在
: k=1的时候will allow all the remaining boxes to be unlocked，即概率是 2/6 = 1
: /3。
|
L*******t
发帖数: 2385 | 15 这种题目用数学归纳法能做不？
boxes
【在 a**********n 的大作中提到】
: not quite right... when n=3 and k=1, the probability should be 1/6
|
a**********n
发帖数: 59 | 16 you are right, i misunderstand the question previously...
1
【在 l*********g 的大作中提到】
: 1/6也不对，应该是1/3。
: 我之前对题意的理解有误，随之的表达式也有误。
: 按照网上答案的意思，举n=3, k=1的例子，在P(3,3)的6种排列中，只有其中2种排列在
: k=1的时候will allow all the remaining boxes to be unlocked，即概率是 2/6 = 1
: /3。
|
l******n
发帖数: 9344 | 17 把盒子固定，只考虑钥匙，打开k个盒子后，按照钥匙的对应的盒子做rotation,如果最
后能回到identity也就是1,..,n的状态而且每个位置都有变化过就可以打开，否则不行
。感觉和permutation group, generating set of a group有关，感觉有代数的方法求解
那位代数大牛来做做
boxes
【在 a**********n 的大作中提到】
: you are right, i misunderstand the question previously...
:
: 1
|
e*****t
发帖数: 16 | |
e*****t
发帖数: 16 | 19 具体来讲，首先定义cycle。 即存在一些子集的盒子，他们之间互相打开，而不会牵涉
到子集外面的其他盒子， 比如 1盒子里面的钥匙打开2盒子，2盒子里面的钥匙打开5盒
子，5盒子里面的钥匙打开3盒子，3盒子里面的钥匙打开1盒子，那么这四个元素子集所
构成的cycle就是： 1→2→5→3→1。
Generally， 盒子里面不同钥匙的排列，总可以把整个系统分割成互不交叉的多个
cycle。 比如n=7的时候， 假如能分割成三个cycles： 1→2→5→3→1， 4→7→4， 6
→6。 其中6→6这种叫做singleton。 那么如果炸开的盒子里面的钥匙能够打开所有的
盒子，相当于至少需要在上面三个cycles里面各取一个盒子，总共至少三个盒子。因为
每个cycle里面只要有一个盒子打开了，整个cycle都打开了。
下面考虑n个盒子中炸开k个盒子使得所有盒子打开的概率p：
假设炸开的k个盒子中的钥匙依次是1,2,3……k。穷举整个系统所有情况相当于所有盒
子做了一个permutation。 假设在n！多个permutation中， 有S（n，k）中情况， 使
得k个钥匙占据了系统分割出来的所有cycles，那么整个系统就是可以打开的。 再用数
学归纳法的思路， 考虑n+1的系统， 这时候多出来了一个元素n+1， 要让整个系统依
然被打开，显然不能让n+1自己构成singleton，即n+1→n+1。 正确的做法是把n+1这个
元素插入到任何一个已有的cycle中去。
比如把n+1插入到2个元素的cycle 4→7→4 中， 则可能是 4→n+1→7→4 或者 4→7→
n+1→4， 两种情况；
类似比如把n+1插入到4个元素的cycle 1→2→5→3→1 中， 则可能是 1→n+1→2→5→
3→1 或者 1→2→n+1→5→3→1……等一共4种情况；
依次类推。 因为原来的系统总共n个盒子，不管分成多少个cycles， 总共可以把n+1插
入n个不同的位置，所以按照数学归纳法的思维，此时k把钥匙能打开n+1系统的情况有：
S（n+1,k）=nS(n,k)
因为显然 S（k,k）=k！ （不管怎么permutation所有k把钥匙肯定能打开k个盒子）
所以S(n,k)=k!*k*(k+1)*...*(n-1)=k*(n-1)!
又因为n个盒子的系统总共permutation个数为n！
所以解开盒子的概率为：
P(n,k) = S(n,k)/n! = k/n
以上参考
http://math.stackexchange.com/questions/73896/keys-inside-close
第一个答案，只是更详细的写出来。 |
