Question

Sean $\ell_A$ y $\ell_B$ dos rectas paralelas distintas. Para enteros positivos $m$ y $n,$ puntos distintos $A_1, A_2, A_3, \ldots, A_m$ están sobre $\ell_A,$ y puntos distintos $B_1, B_2, B_3, \ldots, B_n$ están sobre $\ell_B.$ Además, cuando se trazan los segmentos $\overline{A_iB_j}$ para todos los $i = 1, 2, 3, \ldots, m$ y $j = 1, 2, 3, \ldots, n,$ ningún punto estrictamente entre $\ell_A$ y $\ell_B$ está en más de dos de los segmentos. Halla el número de regiones acotadas en las que esta figura divide el plano cuando $m = 7$ y $n = 5.$ La figura muestra que hay $8$ regiones cuando $m = 3$ y $n = 2.$

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.$

Respuesta

Solución:

Dos segmentos $\overline{A_iB_j}$ y $\overline{A_kB_l}$ se cruzan estrictamente entre las rectas exactamente cuando uno de los puntos $A$ va primero y el $B$ del otro va primero, lo cual ocurre para exactamente un emparejamiento de cualesquiera dos puntos $A$ con cualesquiera dos puntos $B$ . Por la hipótesis de posición general estos cruces son distintos, así que hay $X = \binom{m}{2}\binom{n}{2}$ de ellos.

Recorta las dos rectas a segmentos largos y aplica la fórmula de Euler. Los vértices son los $m + n$ puntos marcados, los $X$ cruces, y los $4$ extremos recortados de las rectas, así que $V = m + n + X + 4.$ La recta $\ell_A$ queda dividida en $m + 1$ aristas y $\ell_B$ en $n + 1;$ cada cruce parte dos segmentos, así que los segmentos trazados aportan $mn + 2X$ aristas, dando $E = mn + m + n + 2X + 2.$ Entonces $F = E - V + 2 = mn + X,$ de las cuales una cara es no acotada, así que hay $mn + X - 1$ regiones acotadas. Para $m = 3,$ $n = 2$ esto da $6 + 3 - 1 = 8,$ coincidiendo con la figura.

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

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 Problema 9

Solución:

El Problema 9 en otros años