Question

Let $\ell_A$ and $\ell_B$ be two distinct parallel lines. For positive integers $m$ and $n,$ distinct points $A_1, A_2, A_3, \ldots, A_m$ lie on $\ell_A,$ and distinct points $B_1, B_2, B_3, \ldots, B_n$ lie on $\ell_B.$ Additionally, when segments $\overline{A_iB_j}$ are drawn for all $i = 1, 2, 3, \ldots, m$ and $j = 1, 2, 3, \ldots, n,$ no point strictly between $\ell_A$ and $\ell_B$ lies on more than two of the segments. Find the number of bounded regions into which this figure divides the plane when $m = 7$ and $n = 5.$ The figure shows that there are $8$ regions when $m = 3$ and $n = 2.$

答案

Solution:

Two segments $\overline{A_iB_j}$ and $\overline{A_kB_l}$ cross strictly between the lines exactly when one of the $A$ 's comes first and the other's $B$ comes first, which happens for exactly one pairing of any two $A$ 's with any two $B$ 's. By the general-position hypothesis these crossings are distinct, so there are $X = \binom{m}{2}\binom{n}{2}$ of them.

Clip the two lines to long segments and apply Euler's formula. The vertices are the $m + n$ marked points, the $X$ crossings, and the $4$ clipped line ends, so $V = m + n + X + 4.$ Line $\ell_A$ is divided into $m + 1$ edges and $\ell_B$ into $n + 1;$ each crossing splits two segments, so the drawn segments contribute $mn + 2X$ edges, giving $E = mn + m + n + 2X + 2.$ Then $F = E - V + 2 = mn + X,$ of which one face is unbounded, so there are $mn + X - 1$ bounded regions. For $m = 3,$ $n = 2$ this gives $6 + 3 - 1 = 8,$ matching the figure.

For $m = 7$ and $n = 5:$ $35 + \binom{7}{2}\binom{5}{2} - 1 = 35 + 21 \cdot 10 - 1 = 244.$

2022 AIME II Problem 9

Solution:

Problem 9 in Other Years