/sci/ - Science & Math » Thread #12543236

247KiB, 700x700, 1592666119993.jpg

View Same Google iqdb SauceNAO

Putnam/Olympiad Problem of the Day

Anonymous Mon 04 Jan 07:59:20 2021 No.12543236 View Reply Original Report

Quoted By: >>12543247 >>12543354 >>12543779

You have 10 idenitcal ropes, each rope with a red and a blue end. You randomly connect all the rope's ends, but red ends can only be connected to blue ends and vice versa. What's the expected number of loops of rope at the end?

Previous thread: >>12539169

Anonymous

Anonymous Mon 04 Jan 2021 08:04:59 No.12543247 Report

Quoted By: >>12543365 >>12543644

>>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

Anonymous

View Same Google iqdb SauceNAO 1329557812388s - Copy.jpg, 3KiB, 126x108

Anonymous Mon 04 Jan 2021 08:57:48 No.12543339 Report

Quoted By: >>12543783

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.

Anonymous

Anonymous Mon 04 Jan 2021 09:04:18 No.12543354 Report

Quoted By:

>>12543236
I only need 1 loop

Anonymous

Anonymous Mon 04 Jan 2021 09:09:00 No.12543365 Report

Quoted By:

>>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

Anonymous

Anonymous Mon 04 Jan 2021 11:05:46 No.12543576 Report

Quoted By:

is a rope allowed to connect to itself?

Anonymous

Anonymous Mon 04 Jan 2021 11:53:25 No.12543644 Report

Quoted By:

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

Anonymous

View Same Google iqdb SauceNAO 1606319710935.png, 117KiB, 294x271

Anonymous Mon 04 Jan 2021 13:13:50 No.12543779 Report

Quoted By:

>>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 $n$ (I'll call it $E_n$ ). This is a well known result, the answer is given by the harmonic numbers $E_n = H_n$ .

For a quick derivation, we obviously have $E_1 = 1$ . Larger rope structures can be built one by one. If we add a rope, we will connect it to itself with probability $\frac{1}{n}$ and increase the amount of loops by $1$ , or with probability $1 - \frac{1}{n}$ 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
$E_n = E_{n - 1} + \frac{1}{n} = H_n$

Anonymous

Anonymous Mon 04 Jan 2021 13:15:43 No.12543783 Report

Quoted By:

>>12543339
Continue with the threads please

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches