## Get knotted

Posted by Chris on April 24, 2013 – 7:33 pm

You have a box with n shoelaces in it. You randomly pick two ends and tie them together. You then repeat this process until there are no free ends left.

On average, how many loops will you have created?

How many laces are needed to get (just over) 2 loops on average?

### 6 Responds so far- Add one»

### Post a reply

« Blockbuster 2
Snap »

April 28th, 2013 at 3:59 am

If n = 1 then only one single-lace loop can be formed.

If n = 2 then after picking the first end there is a 1/3 chance of picking the other end of the same lace (therefore 2 loops) and a 2/3 chance of picking an end of the other lace (therefore one loop). Average number of loops is therefore 4/3.

For n = 3 we have 1/5 * 1/3 = 1/15 chance of three one-lace loops and a 4/5 * 2/3 = 8/15 chance of one three-lace loop, so the chance of two koops must be the difference, i.e. 6/15. Average is therefore (3*1 + 2*6 + 1*8)/15 = 21/15.

Having other things to do right now I’ll stop and make a guess at the answer approaching about 1.5 as n increases.

I would have expected it to be a lot higher.

April 28th, 2013 at 6:54 am

Hi Wiz. Good start. In view of your guessed answer, I’ve added a second question.

I’ll confirm that your probabilities for 3 1-loops and 1 3-loop are correct.

You made a silly error:

(3*1 + 2*6 + 1*8)/15 = 23/15, not 21/15. Other than that, the calculation is correct.

As you’ve probably already realised, continuing with your current approach, is going to become quite difficult. In fact that’s for much the same reason that Blockbuster 2 is hard, and why I chose to limit that to exactly 3 green blocks. (2 green blocks isn’t trivial either, but 3 gives a taste of just how much hard work is needed). However, the posted problem is dead easy, even with an arbitrary number of laces.

May 1st, 2013 at 1:01 pm

Here’s a clue. With 3 laces, pick an end. The probability of picking the other end is 1/5. If you do that you get 1 loop and have 2 laces remaining. There is a probabilty of 4/5 that you’ll pick another lace. In which case you won’t make a loop, and you’ll have 2 laces remaining (one is double length now). i.e. either way you are left with 2 laces. With 2 laces, the average number of loops is 4/3, as Wiz has shown.

So the average number of loops = (1/5)*(1 + 4/3) + (4/5)*(0 + 4/3) = 23/15

May 9th, 2013 at 12:51 pm

n laces so pick an end then we have 1/(2n-1) chance that we make a loop. Whether we make a loop or not by tying two together we reduce our problem to the same problem with n-1 laces. The expected number of loop by making this step is 1/(2n-1).

So the average number of loops made is equal to the following sum: sum from i=1 to n of 1/(2*i-1).

Lets see what n we need for an average over 2:

1+1/3+1/5+1/7+1/9+1/11+1/13+1/15 which is approximately 2.0218 and 1/15>0.05 so we need 8 laces.

May 9th, 2013 at 3:43 pm

Hi jan. That’s the answer I was looking for. Thank you for explaining how you worked it out.

May 9th, 2013 at 4:12 pm

Let E(n) be the expected/average number of loops that would be created if you had n shoelaces.

Pick an end, then pick another end. The probability of you picking the other end of the same shoelace is 1/(2n-1), and then you’d form a loop and have n-1 laces left. There is a probability of (2n – 2)/(2n-1) that you’ll pick another shoelace. You are also left with n-1 laces, but you won’t have made a loop. Either way, the average number of loops left to be created is E(n-1).

So E(n) = (1/(2n-1))(1 + E(n-1)) + ((2n-2)/(2n-1))(0 + E(n-1))

Re-arrange that to get the recursion: E(n) = E(n-1) + 1/(2n-1)

With only 1 shoelace, we must get 1 loop and so that => E(1) = 1.

Then the recursion => E(2) = 1 + 1/3.

Repeating => E(3) = 1 + 1/3 + 1/5, etc.

So E(n) = 1 + 1/3 + 1/5 + 1/7 + … + 1/(2n-1)

Add and subtract 1/2 + 1/4 + 1/5 + … + 1/(2n)

= (1/2)(1 + 1/2 + 1/3 + … + 1/n) to get

E(n) = (1 + 1/2 + 1/3 + … + 1/(2n)) – (1/2)(1 + 1/2 + 1/3 + … + 1/n)

The harmonic function is H(n) = 1 + 1/2 + 1/3 + … + 1/n, so we get

E(n) = H(2n) – H(n)/2

wolframalpha includes the Harmonic(n) function, so pop that into it to get e.g.:

E(30) = H(2*30)-H(30)/2 = 2.6823 7684749… laces.

H(n) ≈ ln(n) + γ + 1/(2n)

ln() – natural log i.e. log base e

(gamma) γ = 0.57721566490… is the Euler-Mascheroni constant

So E(n) ≈ ln(2n) + γ + 1/(4n) – (ln(n) + γ + 1/(2n))/2

= ln(n)/2 + 0.9817550…

= 2.6823 5…

There is no maximum average.

Number of laces required to get an average of at least 2 loops. Using wolframalpha or a calculator we find E(7) = 1.9551… and E(8) = 2.0218…, so 8 is the number of laces required.