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$

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.

Using exactly three diameters accounts for the remaining cases: there are $5$ such matchings (two diameters can never be used without forcing an unmatchable odd arc). In total, $2 + 5 + 5 + 1 = 13.$

Thus, the correct answer is C.

2020 AMC 12B Problem 15

Solution:

Problem 15 in Other Years