2022 AIME II Problem 9

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.

Answer

Answer: 244

Concepts:counting regions Euler’s Polyhedron Formula graph theory counting intersections

Difficulty rating: 2840

Small hint:

Each choice of two

A

’s and two

B

’s produces exactly one interior crossing, so there are

\binom{7}{2}\binom{5}{2}

crossing points

Big hint:

Use Euler’s formula

V - E + F = 2:

each crossing splits two segments, so the segments contribute

mn + 2\binom{m}{2}\binom{n}{2}

edges

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.