Problem 17 · 2004 AMC 8
Medium
Counting & Probability
stars-and-bars
Three friends have a total of 6 identical pencils, and each one has at least one pencil. In how many ways can this happen?
Show answer
Answer: D — 10 ways.
Show hints
Hint 1 of 2
Picture the 6 pencils in a row. To split them among 3 friends, you just need to drop 2 'dividers' into the gaps between pencils — the dividers cut the row into three piles. Counting splits becomes counting where the dividers go.
Still stuck? Show hint 2 →
Hint 2 of 2
This is stars and bars. With the 'each person ≥ 1' rule, there are 5 gaps between the 6 pencils, and you choose 2 of them for dividers: C(5, 2). (No gap gets two dividers, so nobody is left empty.)
Show solution
Approach: stars and bars (dividers in the gaps)
- Line up the 6 pencils. The 'at least one each' rule means each divider must land in a different gap between pencils — there are 5 such gaps, and we place 2 dividers.
- Choose 2 of the 5 gaps: C(5, 2) = 10. So there are 10 ways.
- The general tool: distributing n identical items into k groups with at least one each is C(n − 1, k − 1) — here C(6 − 1, 3 − 1) = C(5, 2) = 10.
Another way — give one away first, then distribute freely:
- Hand each friend 1 pencil up front (satisfying the rule); 3 pencils remain to share with no restriction.
- Splitting 3 identical pencils among 3 friends (zeros allowed) is C(3 + 3 − 1, 3 − 1) = C(5, 2) = 10.
Another way — list the partitions:
- The piles (unordered) are 4+1+1, 3+2+1, 2+2+2.
- Count ordered arrangements: 4+1+1 → 3 ways, 3+2+1 → 6 ways, 2+2+2 → 1 way. Total 3 + 6 + 1 = 10 — a solid check on the formula.
Mark:
· log in to save