Pat is to select six cookies from a tray containing only chocolate chip, oatmeal, and peanut butter cookies. There are at least six of each of these three kinds of cookies on the tray. How many different assortments of six cookies can be selected?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
Cookies of the same kind are identical, so an assortment is just how many of each kind. Count the ways three whole numbers can add to 6.
Solution
Two oatmeal cookies are the same as any other two oatmeal cookies, so an assortment is described completely by three counts: how many chocolate chip, how many oatmeal, how many peanut butter. These are whole numbers (zero allowed) that add to . There are at least six of each kind, so every such split is possible.
The cleanest way to list them is by the number of chocolate chip cookies.
- 0 chocolate chip. The other are oatmeal and peanut butter: oatmeal can be or , and peanut butter is the rest. That is assortments.
- 1 chocolate chip. The other are split between two kinds: oatmeal can be to . That is assortments.
- 2 chocolate chip. The other split in ways.
- 3 chocolate chip: ways. 4 chocolate chip: ways. 5 chocolate chip: ways. 6 chocolate chip: way.
Total:
The answer is .
Why this works
When the items of each kind are identical, only the counts matter, so the question becomes "how many ways can a few whole numbers add up to a total?" Fixing one count at a time turns it into a short, orderly list. The phrase "different assortments" is the signal that order does not matter and the cookies of one kind are interchangeable.
Alternative approach
Stars and bars. Draw the cookies as stars in a row and put bars among them to split them into three groups: chocolate chip, then oatmeal, then peanut butter. For example
means , , , and means all are chocolate chip. Each row of symbols ( stars, bars) matches one assortment, and each assortment matches one row. Choosing which of the spots hold the bars gives rows.
The trap
Treating the six cookies as if they were picked one at a time in order, with 3 choices each, and answering 3 to the sixth power = 729, choice (E).
Concise solution
Cookies of the same kind are interchangeable, so an assortment is determined by the counts of chocolate chip, oatmeal and peanut butter cookies, which are nonnegative integers with . The "at least six of each" clause guarantees every such triple is actually available.
Represent a triple as a row of stars split by bars: for example means . Every arrangement of symbols with bars corresponds to exactly one assortment, so the count is
The answer is .
Review in the AoPS books
- Intermediate Counting & Probability, Chapter 7: Distributions (§7.2, §7.3)
- Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
- Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.4)
Techniques
Map the objects to something easier to count