Problem: Shoe laces

[•Cosmin]

http://www.infoarena.ro/blog/shoelaces

[•harababurel]

I think the following approach might work:

Let dp(i)(j) = the probability  of reaching a state with i untied lace ends and j cycles.

During an operation, two ends are chosen at random and tied together, so they won't be used in the future. This takes us to a state with i-2 untied ends.

Now, there is a 1/(i-1) (or something similar) probability that the two freshly tied ends will close a cycle, and an (i-2)/(i-1) probability that no new cycle will appear.

Therefore we can move to state (i-2)(j+1) with probability P and to (i-2)(j) with probability 1-P.

The trivial state is dp(2*n)(0) = 1.

[•devilkind]

Not 100% sure but I think this is equivalent with the expected number of cycles in a random permutation of size N.

Also I think the answer is N / 2, not proof of this yet, just a wild guess, because I have a feeling that P(i) = Probability you have i cycles = P(N - i + 1) (in other words the probability of having i cycles is the same as the probability N - i + 1 cycles).

[•atatomir]

I totally agree with Tiberiu regarding the equivalence between this problem and counting the expected number of cycles in a permutation of n elements , but I have a different formula .
I think that the answer is = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n .
As a proof, I am going to use induction . Let's note E(i) : the expected number of cycles in a permutation of degree i.

E(1) = 1
Let k be given (k > 1), suppose that E(k-1) is true.
Every permutation of n-1 elements can generate other n-1 permutations of n elements (each of them containing the last shoe lace in an already existing cycle)  and one additional permutation where the last shoe lace forms a cycle of length 1. Only the last case increses the expected value ,so we can conclude that E(i) = E(i-1) *  (n-1)/n + ( E(i-1) + 1 ) * 1/n = E(i-1) + 1/n.

I hope my solution is correct and easy to understand .  

[•Cosmin]

FIIAurelian has the right solution.