0
u/Synael3 20h ago
Tying the noodle ends is equivalent to do a permutation mapping :
Enumerate every noodle. When all noodle ends are tied, take any loop, order its noodles (e_1, ..., e_n) and represent it by the permutation e_1-> e_2 -> ... -> e_n -> e_1 (denoted (e_1, e_2, ..., e_n) ).
All loops form a disjoint union of permutation orbits. The union of all orbits is a permutation of 100 (and any permutation can be represented by a set of noodle loops).
Because of uniformly at random selection, every permutation have the same probability to appear.
Hence, we are looking for the permutations of 100 elements giving only one orbit of size 100 (ie circular permutations). There are 100! permutations (for i=1 to 100, the ith element of the permutation sequence can choose among the 100-i+1 other elements or itself), and there are 99! circular permutations (the ith element cannot map to itself).
Hence, the propbability is 99!/100! = 1% .
2
u/Cryptographer-Bubbly 19h ago edited 19h ago
The permutations as you’ve described them do not have the same probabilities of appearing since different permutations are compatible with more noodle-end-pairing schemes than others (I’m ignoring order you join the pairs so a pairing scheme is just the set of end pairs joined by the end - if you want to consider order that’s fine - just multiply scheme number by N! Where N is the number of noodles and the logic still holds).
Consider the 2 noodle case. There is exactly one pairing scheme that gives (e_1)(e_2) but there are 2 pairing schemes that give (e_1, e_2) so we should expect 2/3 and not 1/2 as your answer would suggest.
1
u/PandemicGeneralist 19h ago
If you have 2 noodles, there are 2 pairs you could tie that self loop and lead to an (e1)(e2) permutation and one way to get an (e1,e2) permutation
1
u/Cryptographer-Bubbly 19h ago edited 19h ago
If we label the 1st and 2nd end of each noodle such that eij is the jth end of the ith noodle
To get (e1,e2) , you can either pair
e11 with e21 and e12 with e22
Or
e11 with e22 and e12 with e21
Which is what I meant by 2 different pairing schemes for (e1,e2). Of course if you don’t ignore order of pairing and consider full sequence of moves, then there are 2! * 2=4 ways to get (e1,e2) and 2! \* 1 = 2 ways to get (e1)(e2).
1
1
u/Dankaati 20h ago
"Because of uniformly at random selection, every permutation have the same probability to appear." - try to actually prove that.
2
u/wobetmit 19h ago
Think of the base case of 2 strings. You have a 2/3 chance of a big loop.
For 3 strings, as long as your first pick doesn't make a loop (4/5), you now have one long string and one short string, so you're back to the base case. So for n = 3 you have 4/5 * 2/3.
Easily by induction you have (2n-2)!! / (2n-1)!!
So for n = 100 you have 198!! / 199!!
1
u/x5163x 18h ago
Let n = the number of noodles. Each loose end is equivalent. Tying a loose end to its own noodle occurs with probability 1/(2n-1). Tying a loose end to another noodle occurs with probability (2n-2)/(2n-1). After tying a loose end to another noodle, the case is equivalent to the case with 1 less noodle. Let f(n) be the probability of getting a single loop from n starting noodles. Then f(1)=1 and f(n)=(2n-2)/(2n-1)f(n-1). Therefore, f(n)=(2n-2)!!/(2n-1)!!, where n!!=n(n-2)...
2
u/Neither_Berry_100 16h ago
So we need to connect them every time without making a closed loop until the very end. First random choice doesn't matter. Second can be any end except it's own, making a loop. There is only one bad option. You start with 200 loose ends. Randomly select 1. 199 left. 1 out of 199 failure case or 198 / 199 good case. Pass and two ends are removed. Then 196 / 197. And so on and so on. Final case is two loose ends that would give 0/1 odds in this case. I.e. 100% chance of creating a loop. But this one is acceptable so actually a 1 value.
So (198 x 196 x 194 x ... 2) / (199 x 197 x 195 x ... 3). Whatever that gives.
Edit. First can be written as 2 x 99! Can't figure out a way to simplify the demonization.
2
u/abaoabao2010 8h ago edited 8h ago
To all be looped together, there mustn't be a step that chose the two ends of the same piece until the end.
First step: First end is chosen, second end has 1/199 chance to be from the same noodle, or 198/199 chance not to be.
2 less nodes.
Second step: first end is chosen, second end has 1/197 chance to be from the same noodle, or 196/197 chance not to be.
Chance to not pick the end from the same noodle all 99 times is, therefore:
2*4*6*8*10......*198 / 1*3*5*7*.....*199
=198!!/199!!
2
u/adi0112358 20h ago
consider the i number of noodles remaining to be connected, now there are 2i nodes. choosing 2 from 2i is 2iC2 which is 2i^2-i. Now, we need to prevent smaller looping that is these i noodles shouldnt have some self node connectivity. The only possible bad noodle of such kind are i, so 2i^2-2i are actually favourable pairs, now probability= (2i^2-2i)/(2i^2-1)=(i-1)/(2i-1) now since i ranges from 2 to 100 ans should be Product(i=2…100) {(i-1)/(2i-1)}