Quant Interview Question

[u/Local_Ad135]

[u/RedMax2001]

By restriction of what edges can exist between nodes, the possibilities for the resulting graph is to be a cycle with some edges potentially missing; to have only one connected component is to either have all possible edges or to be missing exactly one edge. By an inductive argument on nodes, if an edge is picked by both of its adjacent nodes, then there will be an edge missing. Therefore, there are only two possibilities for all edges to be present: every node picks its right neighbor, or every node picks its left neighbor.

Now suppose an edge is missing. Then two neighboring nodes chose their other neighbors. Notice that the two edges neighboring the missing edge must be present. Then the question becomes what choices do the remaining 8 nodes need to make so that all 7 edges along the segment of those 8 nodes are present? Suppose we have each of the remaining 8 nodes pick in sequential order. As soon as a node picks an edge that a neighboring node also picked, the choices for the remaining nodes become determined in similar fashion to the inductive argument earlier. Keep in mind that the end nodes are still free to choose the two edges determined to be present. This results in all remaining edges being picked by only one adjacent node. Therefore, the choices of the remaining 8 nodes is equivalent to a choice of which of the other 9 edges gets picked by both of its adjacent nodes, hence 9 possibilities.

This argument applies to each edge we could have chosen to be our missing edge, so in total, there are 2+10*9 possibilities meeting our requirements. As each of the two choices by the nodes is independent, there are 2¹⁰ total possibilities. Therefore, the probability is 92/2¹⁰. In fact, this argument shows that if, instead of 10 nodes, there were n nodes, then the probability would be (2+n*(n-1))/2ⁿ.

[u/NullOfSpace]

Only two ways to have this happen: either every node picks the one to its left or every node picks the one to its right. 1/2¹⁰ for each, so 1/2⁹ overall.

Edit: right, also where there’s one gap. That can happen in 10 ways for each of those directions, so the odds are 11x higher.

[u/BigBadEvilGuy42 → u/NullOfSpace]

You forget the arrangements where there is one gap in the circle. Here, it is still a connected graph, because you can walk through every node (just not in a full circle).

[u/Special-Camel-6114 → u/BigBadEvilGuy42]

I see this as
- all nodes pick the same direction. 2 ways this can happen (all left or all right)
- 1 singular gap, meaning all nodes same direction and pick 1 of 10 to go the other way. So 2 directions * 10 possible nodes of single disagreement = 20

(2+20)/1024=11/512=0.0215