/sci/ - Science & Math

>>12543236
I like to solve these by shrinking n=10 down to something smaller
n=1 is fake and gay aka 0
n=2 is 1, only one possible configuration

Today's isn't a putnam or olympiad problem. I intend to post one of these threads every day (new years' resolution), so I've preserved the namesake for continuity purposes, but I'm not sure what I want these threads to be.

I will leave it up to you. How would you like these to proceed? I want your stupid ideas.

>>12543236
I only need 1 loop

>>12543247
n=3 is also fake and gay. We can't have one loop, since the only choices are (RB BR RB) and (BR RB BR), and we can't have two or three loops because there is no size-1 loop
I think there are only admissible loops for even n

is a rope allowed to connect to itself?

>>12543247
If n is equal to one you could make a loop out of one rope

>>12543236
"Connecting the ends" is equivalent to a map from each rope to the rope its red end is connected to. Since all ropes are connected, this is a permutation and the question is equivalent to finding the expected number of cycles in a random permutation of size [math]n[/math] (I'll call it [math]E_n[/math]). This is a well known result, the answer is given by the harmonic numbers [math]E_n = H_n[/math].

For a quick derivation, we obviously have [math]E_1 = 1[/math]. Larger rope structures can be built one by one. If we add a rope, we will connect it to itself with probability [math]\frac{1}{n}[/math] and increase the amount of loops by [math]1[/math], or with probability [math]1 - \frac{1}{n}[/math] we break up two already connected ends and insert our new rope in the middle (which does not increase the number of loops). This means that
[eqn] E_n = E_{n - 1} + \frac{1}{n} = H_n[/eqn]

>>12543339
Continue with the threads please