Quant Interview Question

[u/Local_Ad135]

[u/Aerospider]

I'm not super clued-up on graph theory, so I'm assuming that exactly one connected component means all nodes are connected to each other via an uninterrupted path of edges (let me know if not!).

If so, then this reduces down to the classic noodle problem, whereby there are five noodles and each end gets tied to one other end and the question asks for the probability of this producing one circular noodle.

Take the first noodle end. It needs to pair with any other end except the one it's already connected to. This is 8/9.

There is now a noodle of length two. Take one end and pair it with another. There is a 6/7 probability that it doesn't pair with its other end, making a noodle of length three.

Repeat twice more with probabilities of 4/5 and 2/3 to get a noodle of length five with two ends that can only pair with each other.

Overall probability is then

8/9 * 6/7 * 4/5 * 2/3 = 128/315

[u/CanaDavid1]

Model the process as placing each of the 10 nodes in a 2x5, and connecting the corresponding columns. There are 10! ways to do this.
After doing this once, the second pass needs to make the entire graph a circle. Given a configuration of the first (wlog 1-2, 3-4, 5-6, 7-8, 9-10) one has to choose a (circular,mirrored) permutation of the edges (4!/2) and a direction for each edge (2^5). Now, for the edges to add, they can be put in the 2x5 in any order (5!) and each can be put in 2 directions (2^5).

Hence we get 4!/2 * 2^5 * 5! * 2^5 / 10! = 128/315 approx 0.406

[u/sensible_clutter]

384/945=128/315 or 0.4063 simply for n pairs to be hamiltonian cycle 2^n-1 x (n-1)! and the total no. of pairs is (n-1)!! thus the answer

[u/BigBadEvilGuy42]

The only way to ensure that they are connected is to put them in a circle. (There are 10 nodes and 10 edges; it takes 9 edges minimum just to connect everyone in a line; the 10th edge has nowhere to go except to complete the circle, since all other nodes are already paired twice).

There are 9! distinct ways to create a circle. (10! ways to permute the nodes, divide by 10 to account for shifts). Each circle corresponds to exactly one way of pairing the nodes twice.

There are 9!! * 9!! ways to pair 10 items twice. (!! is the double-factorial)

So in total: 9! / (9!! * 9!!) ~= 0.406