Seven distinct pieces of candy are to be distributed among three bags. The red bag and the blue bag must each receive at least one piece of candy; the white bag may remain empty. How many arrangements are possible?
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
Every candy independently picks one of 3 bags (3^7 total); subtract the assignments that leave red empty or blue empty, adding back the one that leaves both empty.
Solution
The candies are distinct, so an arrangement is a choice of bag for each candy: assignments with no restriction.
Remove the bad ones by inclusion-exclusion:
- Red empty: each candy goes to blue or white, ways.
- Blue empty: likewise ways.
- Both empty: everything in white, way, which was subtracted twice.
Valid arrangements:
The answer is .
Why this works
"At least one" restrictions on distinguishable objects are handled by counting the complement: unrestricted assignments minus the ones that violate a condition, corrected for double subtraction. The answer choices differ by one precisely to punish forgetting the add-back term.
Alternative approach
Direct count: choose the nonempty red-and-blue portion of candies ( from to ), split it into two nonempty labeled bags in ways, and put the rest in white: .
The trap
Forgetting to add back the single arrangement with both red and blue empty (all candy in white), which gives 1931.
Common mistakes
- Forgetting to add back the single arrangement with both red and blue empty (all candy in white), which gives 1931.
- Treating the candies as identical and using stars and bars, or subtracting only once.
Techniques
Count the complement and subtract from the total