绳圈

constant · 发表于 2005-10-28 23:50:51

口袋里有 n 根绳子。随机选出两个绳头系在一起，这样重复 n 次。求最后连成一个大绳圈的概率。

乱弹 · 发表于 2005-10-29 02:13:41

What is the probability of not getting a loop of length 1 after one step (which leaves n-1 ropes)? I think it is (2n-2)/(2n-1) if we assume that all ropes are labeled 1, 2, ..., n and the rope ends of rope k are labeled 2k-1， 2k (so we think the two ends are different).

Then we use the principle of multiplication: p(1)=1, p(n+1)=2n/(2n+1)*p(n)=(2n)!!/(2n+1)!!.

Different setting may lead to different answer. For example, under some setting, p(n) could be just 1/n. However, the one I use might be the right one.

heavenarch · 发表于 2005-10-29 03:35:32

2^n *n!/(2*n)!

heavenarch · 发表于 2005-10-29 04:21:19

,wrong, but almost. 2^n *(n!)^2 /(2*n)!
: all possible knots: (2*n)!/(n! *2^n)
: big circles among them: n!

hope not wrong again

I am glad to find so many interesting quizs here and so many great men too, respect.

constant · 发表于 2005-10-29 05:07:58

Induction again?

husonghu · 发表于 2005-10-29 11:12:21

你也是高手。希望你也能多献好题，多显身手

husonghu · 发表于 2005-10-29 12:17:17

n根绳时，总的接法数是C(2n，2)，不成圈的接法数(每根头尾相接)
是n，能成圈(接成n-1根绳)的概率是(2n-2)/(2n-1)；

依次，n-1根绳时，能成圈(接成n-2根绳)的概率是(2n-4)/(2n-3)；

.............

所以，P(n)=(2n-2)!!/(2n-1)!!

不知做得对不对?

vicky3712 · 发表于 2005-10-29 13:07:10

if n = 1, p(1) = 0!!/1!! = 1; right

n = 2, p(2) = 2!!/3!! = 2/6! this is wrong.

the correct approach is

p(1) = 1;

for n > 1,

p(2) = (4/C(4, 2)) p(1) = 2/3;

p(3) = (C(6,2) - 3)/C(6,2)) P(2) = 8/15;

p(n) = (C(2n, 2) -n)/C(2n, 2)) p(n-1)

which is a ugly expression.

husonghu · 发表于 2005-10-29 19:43:09

You were wrong by saying 2!!/3!! = 2/6!

Instead, 2!!/3!! = 2/3

In fact, if you simplify your result, you will get exactly

the same thing:

P(n)=(2n-2)!!/(2n-1)!!

乱弹 · 发表于 2005-10-30 04:56:32

constant · 发表于 2005-10-30 06:07:06

I was thinking about using permutation groups. But somehow the answer was different. Probably "randomness" is defined differently.

QL · 发表于 2005-10-30 06:59:56

"Different setting may lead to different answer. For example, under some setting, p(n) could be just 1/n. "

Can you elaborate this?

乱弹 · 发表于 2005-10-30 12:52:08

My first thought: each permutation is corresponding to a way of tieing. There are n! permutations, with (n-1)! of them being cycles of length n.

However, later I thought this was wrong. This mapping is not one-one or in any sense constant-constant.

		自动登录	找回密码
密码			立即注册

动态微博

绳圈

回复：绳圈

回复：绳圈

回复：回复：绳圈

Induction again? [:X]

你也是高手。希望你也能多献好题，多显身手[@};-][@};-][>:D<]

不过你这答案好象不对。同意乱弹P(n)=(2n-2)!!/(2n-1)!!. 我是这样推的....

回复：不过你这答案好象不对。同意乱弹P(n)=(2n-2)!!/(2n-1)!!. 我是这样推的..

Seems nothing wrong with P(n)=(2n-2)!!/(2n-1)!! ..

[:P]

回复：[:P]

回复：回复：绳圈

回复：回复：回复：绳圈