2022 AIME II Problema 9

Intenta el Problema 9 del 2022 AIME II a continuación y luego compara tu respuesta con la solución preparada profesionalmente de LIVE by Po-Shen Loh. También puedes intentar el examen cronometrado completo, ver todas las soluciones del 2022 AIME II, o revisar la clave de respuestas.

Todos los problemas se usan con el permiso legal oficial de la Mathematical Association of America (MAA).

9.

Sean ℓA\ell_A y ℓB\ell_B dos rectas paralelas distintas. Para enteros positivos mm y n,n, puntos distintos A1,A_1, A2,A_2, A3,A_3, …,\ldots, AmA_m están sobre ℓA,\ell_A, y puntos distintos B1,B_1, B2,B_2, B3,B_3, …,\ldots, BnB_n están sobre ℓB.\ell_B. Además, cuando se trazan los segmentos AiBj‾\overline{A_iB_j} para todos los i=1,i = 1, 2,2, 3,3, …,\ldots, mm y j=1,j = 1, 2,2, 3,3, …,\ldots, n,n, ningún punto estrictamente entre ℓA\ell_A y ℓB\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=7m = 7 y n=5.n = 5. La figura muestra que hay 88 regiones cuando m=3m = 3 y n=2.n = 2.
Let ℓA\ell_A and ℓB\ell_B be two distinct parallel lines. For positive integers mm and n,n, distinct points A1,A_1, A2,A_2, A3,A_3, …,\ldots, AmA_m lie on ℓA,\ell_A, and distinct points B1,B_1, B2,B_2, B3,B_3, …,\ldots, BnB_n lie on ℓB.\ell_B. Additionally, when segments AiBj‾\overline{A_iB_j} are drawn for all i=1,i = 1, 2,2, 3,3, …,\ldots, mm and j=1,j = 1, 2,2, 3,3, …,\ldots, n,n, no point strictly between ℓA\ell_A and ℓB\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=7m = 7 and n=5.n = 5. The figure shows that there are 88 regions when m=3m = 3 and n=2.n = 2.
Respuesta: 244
Conceptos:conteo de regionesFórmula de los poliedros de Eulerteoría de grafosconteo de intersecciones
Nivel de dificultad: 2840
Pista pequeña:
Cada elección de dos puntos AA y dos puntos BB produce exactamente un cruce interior, así que hay (72)(52)\binom{7}{2}\binom{5}{2} puntos de cruce
Each choice of two AA’s and two BB’s produces exactly one interior crossing, so there are (72)(52)\binom{7}{2}\binom{5}{2} crossing points
Pista grande:
Usa la fórmula de Euler V−E+F=2:V - E + F = 2: cada cruce parte dos segmentos, así que los segmentos aportan mn+2(m2)(n2)mn + 2\binom{m}{2}\binom{n}{2} aristas
Use Euler’s formula V−E+F=2:V - E + F = 2: each crossing splits two segments, so the segments contribute mn+2(m2)(n2)mn + 2\binom{m}{2}\binom{n}{2} edges
Solución:
Dos segmentos AiBj‾\overline{A_iB_j} y AkBl‾\overline{A_kB_l} se cruzan estrictamente entre las rectas exactamente cuando uno de los puntos AA va primero y el BB del otro va primero, lo cual ocurre para exactamente un emparejamiento de cualesquiera dos puntos AA con cualesquiera dos puntos BB. Por la hipótesis de posición general estos cruces son distintos, así que hay X=(m2)(n2)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+nm + n puntos marcados, los XX cruces, y los 44 extremos recortados de las rectas, así que V=m+n+X+4.V = m + n + X + 4. La recta ℓA\ell_A queda dividida en m+1m + 1 aristas y ℓB\ell_B en n+1;n + 1; cada cruce parte dos segmentos, así que los segmentos trazados aportan mn+2Xmn + 2X aristas, dando E=mn+m+n+2X+2.E = mn + m + n + 2X + 2. Entonces F=E−V+2=mn+X,F = E - V + 2 = mn + X, de las cuales una cara es no acotada, así que hay mn+X−1mn + X - 1 regiones acotadas. Para m=3,m = 3, n=2n = 2 esto da 6+3−1=8,6 + 3 - 1 = 8, coincidiendo con la figura.
Para m=7m = 7 y n=5:n = 5: 35+(72)(52)−135 + \binom{7}{2}\binom{5}{2} - 1 =35+21⋅10−1= 35 + 21 \cdot 10 - 1 =244.= 244.
Two segments AiBj‾\overline{A_iB_j} and AkBl‾\overline{A_kB_l} cross strictly between the lines exactly when one of the AA’s comes first and the other’s BB comes first, which happens for exactly one pairing of any two AA’s with any two BB’s. By the general-position hypothesis these crossings are distinct, so there are X=(m2)(n2)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+nm + n marked points, the XX crossings, and the 44 clipped line ends, so V=m+n+X+4.V = m + n + X + 4. Line ℓA\ell_A is divided into m+1m + 1 edges and ℓB\ell_B into n+1;n + 1; each crossing splits two segments, so the drawn segments contribute mn+2Xmn + 2X edges, giving E=mn+m+n+2X+2.E = mn + m + n + 2X + 2. Then F=E−V+2=mn+X,F = E - V + 2 = mn + X, of which one face is unbounded, so there are mn+X−1mn + X - 1 bounded regions. For m=3,m = 3, n=2n = 2 this gives 6+3−1=8,6 + 3 - 1 = 8, matching the figure.
For m=7m = 7 and n=5:n = 5: 35+(72)(52)−135 + \binom{7}{2}\binom{5}{2} - 1 =35+21⋅10−1= 35 + 21 \cdot 10 - 1 =244.= 244.
Problema 8#8
Examen completo

El Problema 9 en otros años