Maths Olympiad Prep

Library / /12 of 12

, 2025

Combinatorics Difficulty 6.8 National Olympiad Prove it United States

Alex divides a disk into four quadrants with two perpendicular diameters intersecting at the center of the disk. He draws 25 more line segments through the disk, drawing each segment by selecting two points at random on the perimeter of the disk in different quadrants and connecting those two points. Find the expected number of regions into which these 27 line segments divide the disk.

Solution

Because the endpoints of the segments are chosen at random from a uniform distribution, the probability that two segments share an endpoint is 0, so that possibility can be ignored. For the same reason, it can be assumed that no more than two of the segments intersect at the same point. Before any of the 27 line segments are drawn, the disk consists of 1 region. As each new line segment is drawn, 1 more region is created for each region that the new line segment enters. This is equal to 1 plus the number of times the new line segment intersects one of the previously drawn line segments. It follows that the total number of regions created by the 27 line segments is 1+27+I=28+I1 + 27 + I = 28 + I, where II is the number of intersections of the line segments in the interior of the disk.

Label the four quadrants of the disk in order as 1, 2, 3, and 4. Then label each of the 25 randomly chosen line segments that Alex draws with the quadrants containing its endpoints; that is, each segment can be labeled 12, 13, 14, 23, 24, or 34, and each of these labels occurs with equal probability. The line segments labeled 12, 23, 34, and 14 connect adjacent quadrants and intersect one of the two diameters, but the line segments labeled 13 and 24 intersect both diameters. Thus the expected number of intersections of the 25 randomly drawn segments with the 2 diameters is 25(123+213)=100325 \cdot (1 \cdot \frac{2}{3} + 2 \cdot \frac{1}{3}) = \frac{100}{3}. There is also 1 intersection at the center of the disk where the two diameters intersect.

It remains to find the expected number of intersections between pairs of the 25 randomly drawn line segments. There are (252)=300\binom{25}{2} = 300 pairs of line segments. Each pair consists of two segments, and each segment is equally likely to be labeled 12, 13, 14, 23, 24, or 34. Of the 62=366^2 = 36 possible combinations of two labels, 30 of them consist of labels that share at least one quadrant; that is, there is a probability of 3036=56\frac{30}{36} = \frac{5}{6} that the two line segments will have at least one endpoint in the same quadrant. These pairs of segments will intersect with probability 12\frac{1}{2}. Of the 6 remaining possible combinations of labels, 4 consist of pairs that cannot intersect: (12, 34), (14, 23), (23, 14), and (34, 12). The other 2 consist of pairs that must intersect: (13, 24) and (24, 13). Thus the expected number of intersections of pairs is

300(5612+236)=4253. 300 \left( \frac{5}{6} \cdot \frac{1}{2} + \frac{2}{36} \right) = \frac{425}{3}.

The expected value of II is therefore 1003+1+4253=176\frac{100}{3} + 1 + \frac{425}{3} = 176. The expected number of regions is 28+176=20428 + 176 = 204.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.