wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Rope Loops
        
(Message started by: ThudanBlunder on Jul 18^th, 2007, 12:37pm)

Title: Rope Loops
Post by ThudanBlunder on Jul 18^th, 2007, 12:37pm

Jill has six ropes. Randomly choosing two of the twelve loose ends (possibly of the same rope), she ties them together, leaving ten loose ends. Now she again randomly chooses two loose ends and joins them and continues like this until there are no loose ends. What is the expected number of loops Jill ends up with?

Title: Re: Rope Loops
Post by SMQ on Jul 18^th, 2007, 4:19pm

Given n ropes:

[hide]After picking one loose end, there is a 1 in 2n-1 chance of picking the other end of the same rope and thus forming a loop.[/hide]

[hide]After picking two loose ends, whether or not a loop was formed, there are now n-1 ropes remaining (where a "rope" may consist of multiple original ropes tied end-to-end.[/hide]

[hide]So at every step there is a 1/(2n-1) chance of forming a loop. Since these events are independent, the expected number of loops is sum from 1 to n of 1/(2k-1).[/hide]

I'm sure there's a closed form of that, but to answer the riddle as posed, for n=6, the expected number of loops is [hide]19524/10395 or approximately 1.87821[/hide]

Title: Re: Rope Loops
Post by birbal on Mar 9^th, 2011, 12:00am

I was just wondering if we can say anything about the sizes of the loops.
Lets say to start with, we have n ropes and we keep on repeating the process until all the ends are vanished. What is the expected size of the maximum number of the loops?

Title: Re: Rope Loops
Post by Noke Lieu on Apr 18^th, 2011, 6:32pm

Or, if the loops are linked (like a chain) or separate... :-/

Title: Re: Rope Loops
Post by ThudnBlunder on May 28^th, 2011, 6:02am

on 07/18/07 at 16:19:12, SMQ wrote:

I'm sure there's a closed form of that, but to answer the riddle as posed, for n=6, the expected number of loops is [hide]19524/10395 or approximately 1.87821[/hide]

Sum_n = H_2n - (1/2)*H_n (where H_n = 1 + 1/2 + 1/3 + 1/4 + ..... + 1/n)
= (1/2)*H_n + log_e2
--> (1/2)*log_en + 0.981755.... as n --> http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif

Title: Re: Rope Loops
Post by Hippo on Sep 12^th, 2011, 11:36am

on 05/28/11 at 06:02:45, ThudnBlunder wrote:

Sum_n = H_2n - (1/2)*H_n (where H_n = 1 + 1/2 + 1/3 + 1/4 + ..... + 1/n)
= (1/2)*H_n + log_e2
--> (1/2)*log_en + 0.981755.... as n --> http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif

I would use \approx ... instead of =