Problem:
Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.
Solution:
There is one subset of the chairs that contains all ten chairs. If a subset of the chairs does not contain all ten chairs and contains at least three adjacent chairs, then there is a sequence of four adjacent chairs where the first chair (counting clockwise) is not in the subset and the other three chairs are in the subset. There are ten possible places for this sequence of four chairs, and ways to determine which of the other chairs are in the subset. This double counts the subsets that contain two disconnected sequences of three or more adjacent chairs. The number of subsets containing two disconnected sequences of three or more adjacent chairs can be counted by noting that there are ways of selecting the two sequences of four chairs ( ways to select a first sequence of chairs times ways of selecting a second sequence of chairs from the remaining chairs divided by because each pair of chairs gets counted twice) and ways to decide which of the other two chairs are in the subset. It follows that the number of subsets of chairs containing at least three adjacent chairs is .
The problems on this page are the property of the MAA's American Mathematics Competitions