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 around the circle. Count by the number of pairs of opposite people.

With no opposite pairs, everyone must be paired with a neighbor around the 10-cycle. There are exactly $2$ alternating neighbor matchings.

With one opposite pair, choose that pair in $5$ ways. The remaining people form two paths of four vertices, and each path has only one perfect matching by neighbor pairs, so this gives $5$ matchings.

With two or four opposite pairs, the remaining neighbor-pairing paths have odd length somewhere, so no perfect matching is possible.

With three opposite pairs, the two opposite pairs not chosen must be adjacent around the five opposite-pair positions; otherwise the remaining people cannot be matched by neighbor pairs. There are $5$ adjacent choices for the two unchosen opposite pairs, so there are $5$ matchings.

With all five opposite pairs, there is $1$ matching. The total is $2+5+5+1=13.$

Thus, the correct answer is C .

2020 AMC 10B Problem 17

Solution:

Problem 17 in Other Years