2020 AMC 10B Problem 17
Problem 17 of 25IntermediateCounting & Probability
There are people standing equally spaced around a circle. Each person knows exactly of the other people: the people standing next to her or him, as well as the person directly across the circle. How many ways are there for the people to split up into pairs so that the members of each pair know each other?
Answer choices
Show solution
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 -cycle. There are exactly alternating neighbor matchings.
With one opposite pair, choose that pair in ways. The remaining people form two paths of four vertices, and each path has only one perfect matching by neighbor pairs, so this gives 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 adjacent choices for the two unchosen opposite pairs, so there are matchings.
With all five opposite pairs, there is matching. The total is
Thus, the correct answer is C .