2020 AMC 12B Problem 15

Question

There are

10

people standing equally spaced around a circle. Each person knows exactly

3

of the other

9

people: the

2

people standing next to her or him, as well as the person directly across the circle. How many ways are there for the

10

people to split up into

5

pairs so that the members of each pair know each other?

11

12

13

14

15

Answer: C

Concepts:graph theory casework

Difficulty rating: 1730

Small hint:

Count perfect matchings using edges that are either adjacent (neighbor) pairs or diameters (across)

Big hint:

Organize by how many diameter pairs are used; only

0, 1, 3,

or

5

of them can occur

Solution:

Label the people

0

through

9.

Allowed pairings use neighbor edges

(i, i + 1)

or diameter edges

(i, i + 5).

Count perfect matchings by the number of diameter edges used.

Using no diameters, the ten people split into adjacent pairs in

2

ways (all “even” edges or all “odd” edges). Using exactly one diameter, choose it in

5

ways; the remaining two arcs of four people each pair up uniquely, giving

5.

Using all five diameters gives

1

matching.

If at least one diameter is used, following the forced adjacent pairings around the circle shows that the number of diameters must be odd. With exactly three diameters, the four remaining people must be two opposite adjacent pairs. The position of one such opposite pair determines the matching, giving

5

possibilities. Hence the total is

2+5+5+1=13.

Thus, the correct answer is C.