Subsets of Chair Arrangement

Question

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.

Attempt: I counted as "the method where all three chairs must be lined up next to each other", "the method where all four chairs must be lined up next to each other"...and so on. But there are many situations where there can be three adjacent chairs in the "four adjacent chairs". Because the inside can be exchanged at will...? Can I solve it that way?

Answer 1

It sounds like what you're doing might work. Here's an approach similar to yours, which takes care of the overcounting you mentioned through the "principle of inclusion-exclusion"

1. Consider the subsets with three chairs. The chairs in these subsets are all adjacent, so there're $10$ such subsets.
2. Consider the subsets with four chairs. If we ignore the $4$-th chair for a moment, we see that there're $10$ possible arrangements for the other three. There're $7$ ways to add in the $4$-th chair, which gives us $70$ ways. However, this results in overcounting: all arrangements with all $4$ chairs adjacent are counted twice. For instance, if we assign the chairs with numbers from $1$ through $10$, then $\{1,2,3,4\}$ will be counted once when we consider $1,2,3$ to be the adjacent triple, and once more when we consider $2,3,4$ to be the adjacent triple. So we must subtract $70$ by the number of adjacent quadruples, which gives $70 - 10 = 60$.
3. Use the same procedure for subsets with more chairs: "naively" find the number of subsets of adjacent chairs while ignoring overcounting, then subtract the overcounted subsets separately.

However, using "complementary counting" will be much, much easier, especially for this problem. Find the number of subsets of chairs that do not contain at least $3$ adjacent chairs, then subtract this from the total number of subsets.