0

Met this in an interview. Basically this is a different version of the old familiar rope connecting problem. In that problem, we are asked what's the expected number of loops after connecting n ropes in random.

This problem ask for probability of getting a single rope without any loops at the end. Detailed problem set up is as: You have N 1 inch long ropes, and you could connect two nodes together N-1 times. What is the probability for you to finally get a whole N-inch long rope without any loop?

Is this just 1 - P(has any loop in N ropes) = $$ 1 - \frac{N}{{2N \choose 2}} $$ ?

Thanks

vvtt
  • 1
  • I'm probably missing something, but there's a (N-1)/N chance your second rope will be different from your first (assuming we're allowing self-looping), (N-2)/N that the next one will be different, (N-3)/N that third one will be, etc. Thus, it seems the answer would be N!/(N^N). This may be equal to what you wrote down, but I don't think it is. –  Jan 26 '16 at 19:11

1 Answers1

0

function L:

  • The possibilities of getting $N$ inch rope is $L(N)$

Considering ropes A,B,C... with adges $(a_0,a_1)$,$(b_0,b_1)$, ...

For a first arbitrary leftmost rope $(a_0,a_1)$, a variation of two sides of $N-1$ ropes are candidate to be tied, means $2*(N-1)$

For any sequence $a_0,(a_1,b_0),b_1$ or $a_0,(a_1,b_1),b_0$, a variation of two sides of $N-2$ ropes are posed to be connected, means $2*(N-2)$

$L(N)=2^{N-1}*(N-1)!$

function C:

$C$ is a function noted for summing all possible ties between $N$ ropes which equals to the orderings of edges of ropes divided on all similar cases of ordering two adjacent edges.

$C(N)=\frac{(2(N))!}{2^{N}}$

Calculating probablity

P(rope)=$\frac{L(N)}{C(N)}=\frac{2^{N-1}*(N-1)!}{\frac{(2N)!}{2^{N}}}=\frac{2^{2N-1}(N-1)!}{(2N)!}$

PS: Order of actions isnt taken to count.

Abr001am
  • 746