AMC12 2020 B

Answer (C): This problem can be modeled by a regular decagon with the 5 diagonals connecting each point to the point opposite to it. A line segment between two vertices indicates that the people represented by those vertices know each other. See the figure below. The required pairings are then sets of 5 of the 15 line segments in this figure such that no 2 line segments in a set share an endpoint. (This is known as a perfect matching in graph theory.) The number of pairings can be counted by focusing on the number of diagonals used in the pairing. • There is 1 pairing using all 5 diagonals, and any pairing that includes 4 of the diagonals must use all of them. • Suppose a pairing uses exactly 3 diagonals. If 3 of the endpoints of these diagonals are consecutive points on the decagon, then a pairing can be formed by including sides of the decagon as the other 2 segments. There are 5 different pairings of this form. On the other hand, any pairing that includes 3 of the diagonals whose endpoints are not consecutive points on the decagon must use all the diagonals. • There are no pairings using exactly 2 of the diagonals, because any pairing that includes 2 of the diagonals will force at least 3 of the diagonals to be used. • If a pairing uses exactly 1 diagonal, then the rest of the pairing is uniquely determined. There are 5 different pairings of this form. • If a pairing uses no diagonals, then it must use nonadjacent sides of the decagon, and there are 2 different pairings of this form. As shown in the figure, the requested number of pairings is $1+5+5+2=13$.