2022 AIME II Problem 9

Attempt Problem 9 of the 2022 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2022 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

9.

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.

Answer: 244
Concepts:counting regionsEuler’s Polyhedron Formulagraph theorycounting intersections
Difficulty rating: 2840
Small Hint:

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

Big Hint:

Use Euler’s formula VE+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

Solution:

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=EV+2=mn+X,F = E - V + 2 = mn + X, of which one face is unbounded, so there are mn+X1mn + X - 1 bounded regions. For m=3,m = 3, n=2n = 2 this gives 6+31=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+21101= 35 + 21 \cdot 10 - 1 =244.= 244.

Problem 8#8
Full Exam

Problem 9 in Other Years