# Finding the expected number of distinct intersections when four diagonals are randomly drawn in regular hexagon

Four diagonals are randomly drawn in a regular hexagon. Find the expected number of distinct intersections of these segments in the interior of the hexagon.

I believe that the maximum number of distinct intersections is $$3,$$ and the least is $$1.$$ So it suffices to calculate the expected value of having $$1$$ intersection, $$2$$ intersections, and $$3$$ intersections, and then add them up. However, I'm not really sure how to do this. I've tried using casework for depending on how many intersections there are but it doesn't seem to be very nice. I'm trying to somehow use linearity of expectation, but I'm not really sure how. May I have some help? Thanks in advance.

To clarify, this problem is #23 on an AoPS mock, called OIMC. Here is the link to the discussion thread. artofproblemsolving.com/community/c5h2886911

• can the diagonals only be drawn from one vertex to another? Commented Jul 23, 2022 at 22:51
• Yes, that is correct. To clarify, this problem is #23 on an AoPS mock, called OIMC. Here is the link to the discussion thread. artofproblemsolving.com/community/c5h2886911 Commented Jul 23, 2022 at 23:53
• Using linearity of expectation, $E=P_{\text{center}}+12\times P_{\text{outer}}$ Can you calculate those probabilities? Commented Jul 24, 2022 at 0:45
• I will attempt to. Here, $P_\text{center}$ means the center intersection of the hexagon and $P_\text{outer}$ means the non-center intersections, right? So your equation is essentially equivalent to saying the expected intersections is the expected value of getting a center intersection added to the expected value of getting an outer intersection? Commented Jul 24, 2022 at 0:49
• Side note: 4 intersections is possible. Commented Jul 24, 2022 at 0:53

Each vertex in the regular hexagon may be diagonally connected with three of the other vertices. Also, each diagonal is associated with two vertices. Therefore, there are

$$\frac{6 \times 3}{2} ~~\text{distinct diagonals} \tag1$$

that may be drawn.

Label the vertices, in clockwise order, $$P_1, P_2, P_3, P_4, P_5, P_6.$$ The challenge is to find an elegant enumeration method that permits shortcuts. The $$9$$ diagonals are listed below:

$$\begin{array}{| l | l | l |} \hline \text{Assigned Variable} & \text{Specific Diagonals} & \text{Diagonal Type} \\ \hline D_1 & \overline{(P_1,P_3)} & \text{Side} \\ \hline D_2 & \overline{(P_1,P_4)} & \color{red}{\text{Main}} \\ \hline D_3 & \overline{(P_1,P_5)} & \text{Side} \\ \hline D_4 & \overline{(P_2,P_4)} & \text{Side} \\ \hline D_5 & \overline{(P_2,P_5)} & \color{red}{\text{Main}} \\ \hline D_6 & \overline{(P_2,P_6)} & \text{Side} \\ \hline D_7 & \overline{(P_3,P_5)} & \text{Side} \\ \hline D_8 & \overline{(P_3,P_6)} & \color{red}{\text{Main}} \\ \hline D_9 & \overline{(P_4,P_6)} & \text{Side} \\ \hline \end{array}$$

So, approaching the problem combinatorically, the enumeration will be

$$\frac{N}{\binom{9}{4} = 126}, \tag1$$

since there are $$(126)$$ ways of selecting the $$(4)$$ diagonals. In (1) above, $$(N)$$ will be the sum of the number of intersection points, for all $$(126)$$ sets of $$(4)$$ diagonals.

Note that:

• Any two main diagonals will always intersect in the exact center of the hexagon.

• Of the $$~\displaystyle \binom{6}{2} = 15$$ possible side-side pairings, the only ones that will intersect will be the side-side pairing that do not share a vertex and are not parallel. There are $$6$$ such side-side pairings that share a vertex, and $$3$$ such pairings that are parallel.

Therefore, on average, $$~\displaystyle \frac{6}{15} = \frac{2}{5}~$$ such pairings will intersect.

• Any two main diagonals will always intersect in the center of the hexagon. Further, no side diagonal will pass through the center of the hexagon. Also, the only time that intersections between two different pair of diagonals will fall on the same point is when both of the diagonals are main diagonals.

That is, all side-side intersections will always be distinct, and all side-main intersections will always be distinct.

I will break up the analysis into cases, depending on how many of the $$(4)$$ diagonals chosen are main diagonals.

For $$k \in \{1,2,3,4\}$$, I will use $$T_k$$ to represent how many intersection points are enumerated for Case $$k$$.

• Case 1: all three main diagonals are chosen.
There are $$\displaystyle ~\binom{3}{3} \times \binom{6}{1} = 6~$$ corresponding sets of $$(4)$$ diagonals.
In each such set, the three main diagonals will all intersect in the exact center of the hexagon, and each side diagonal will add exactly one additional intersection point.

Therefore, the final total for this case is
$$T_1 = 6 \times [1 + 1] = 12.$$

• Case 2: Two of the three main diagonals are chosen, and these two intersect in the hexagon center.
There are $$\displaystyle ~\binom{3}{2} \times \binom{6}{2} = 45~$$ corresponding sets of $$(4)$$ diagonals.
By symmetry, you can assume without loss of generality, that the pertinent main diagonals are $$D_2, D_5.$$
So, the $$(15)$$ pertinent cases are analyzed as follows:

There will be $$(15)$$ intersections of the two main diagonals.

$$(2)$$ of the $$(6)$$ side diagonals will not intersect with either main diagonal, and the other $$(4)$$ of the $$(6)$$ side diagonals will intersect with exactly $$(1)$$ of the main diagonals.
This implies that on average, each side diagonal will intersection with $$(2/3)$$ of the main diagonals.
So, the corresponding $$(15)$$ side diagonal pairs will create $$\displaystyle ~\left[2 \times \frac{2}{3} \times 15\right] = 20~$$ side-main intersections.

As discussed in the notes, there will be an additional $$~(15 - [6 + 3] = 6)~$$ side-side intersection points.

Therefore, the final total for this case is
$$T_2 = 3 \times (15 + 20 + 6) = 123$$ intersection points.

Incidentally, under the assumption that the $$(2)$$ main diagonals are $$~D_2,D_5, ~$$the added side pair of $$~D_3,D_4~$$ will have a total of $$(1)$$ intersection point, while the added side pair of $$~D_7,D_9~$$ will have a total of $$\color{red}{(4) ~\text{intersection points}}.$$

• Case 3: One of the three main diagonals is chosen.
There are $$\displaystyle ~\binom{3}{1} \times \binom{6}{3} = 60~$$ corresponding sets of $$(4)$$ diagonals.
Without loss of generality, it will be assumed that the main diagonal is $$~D_2$$. All of the analysis in Case 3 will merely represent a re-organization of the previous analysis.
So, the $$(20)$$ pertinent cases are analyzed as follows:

There are $$(0)$$ main-main intersections.

Only $$(2)$$ of the (6) side diagonals will intersect with a main diagonal.
So, on average, each side diagonal will intersect with $$~\dfrac{1}{3}~$$ of a main diagonal.
Therefore, in the $$(20)$$ pertinent cases, there will be
$$\displaystyle \left[20 \times \binom{3}{1} \times \frac{1}{3} = 20\right]~$$ side-main intersections.

As previously noted, $$~\displaystyle \frac{2}{5}~$$ of all possible side-side pairings will intersect.
Therefore, in the $$(20)$$ pertinent cases, there will be
$$\displaystyle \left[20 \times \binom{3}{2} \times \frac{2}{5} = 24\right]~$$ side-side intersections.

Therefore, the final total for this case is
$$T_3 = 3 \times (0 + 20 + 24) = 132$$ intersection points.

• Case 4: None of the three main diagonals is chosen.
There are $$\displaystyle ~\binom{3}{0} \times \binom{6}{4} = 15~$$ corresponding sets of $$(4)$$ diagonals.
All of the analysis in Case 4 will merely represent a re-organization of the previous analysis.
So, the $$(15)$$ pertinent cases are analyzed as follows:

There are $$(0)$$ main-main intersections.

There are $$(0)$$ side-main intersections.

As previously discussed, of the $$~\displaystyle 15 \times \binom{4}{2} = 90~$$ side-side pairings, only $$~\dfrac{2}{5}~$$ of these will result in an intersection.

Therefore, the final total for this case is
$$T_4 = 90 \times \dfrac{2}{5} = 36$$ intersection points.

$$\underline{\text{Final Computation}}$$

$$T_1 + T_2 + T_3 + T_4 = 12 + 123 + 132 + 36 = 303.$$

Therefore, the expected number of intersection points is

$$\frac{303}{126}.$$

Response to the comment of Daniel Mathias.

Linearity of expectation gives the same result without all the casework. See my comment above.

My response: $$\color{red}{\text{Wow!}}$$
I just confirmed his comment.
Using the vertex labeling at the start of my answer, and using the syntax $$[(a,b)::(c,d)]$$ to denote the intersection point of $$\overline{(P_a,P_b)}$$ and $$\overline{(P_c,P_d)},$$ you have the following intersection points:

• $$[(1,3)::(2,4)], [(1,3)::(2,5)], [(1,3)::(2,6)], [(1,4)::(2,6)], [(1,4)::(3,5)], [(1,5)::(2,6)], [(1,5)::(3,6)], [(1,5)::(4,6)], [(2,4)::(3,5)], [(2,4)::(3,6)], [(2,5)::(4,6)], [(3,5)::(4,6)].$$

• $$[(1,4)::(2,5)]$$.

In the first bullet point above, the $$(12)$$ outer intersection points will each occur $$~\displaystyle\binom{9-2}{4-2} = \binom{7}{2} = 21~$$ times in the $$~\displaystyle\binom{9}{4} = 126~$$ total ways of choosing $$(4)$$ of the diagonals at random.

For the second bullet point above, the internal intersection point can occur in $$(2)$$ different ways:

• A set of $$(4)$$ diagonals that contain exactly $$(2)$$ main diagonals:
Enumeration is $$~\displaystyle \binom{3}{2} \times \binom{6}{2} = 45.$$

• A set of $$(4)$$ diagonals that contain exactly $$(3)$$ main diagonals:
Enumeration is $$~\displaystyle \binom{3}{3} \times \binom{6}{1} = 6.$$

• So, the total number of ways that the inner intersection point will occur is $$(45 + 6 = 51).$$

Therefore, using the approach of Daniel Mathias, in the fraction :

$$\frac{N}{126},$$

the value of $$N$$ may be computed as

$$(12 \times 21) + (51) = 303.$$

• Linearity of expectation gives the same result without all the casework. See my comment above. Commented Jul 24, 2022 at 1:10
• @DanielMathias : +1 : Wow! I need some time to verify your analysis. Then, I will update my answer with an Addendum. Commented Jul 24, 2022 at 1:18
• Thanks to both of you! Commented Jul 24, 2022 at 1:19