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

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.

2020 AMC 12B Problem 15

Answer: C

Difficulty rating: 1730

Solution:

Problem 15 in Other Years