2007 AMC 10A Problem 12
Two tour guides are leading six tourists. The guides decide to split up. Each tourist must choose one of the guides, but with the stipulation that each guide must take at least one tourist. How many different groupings of guides and tourists are possible?
Show solution without answering
Key insight
Each tourist has 2 choices, giving 64 ways with no rule. Only 2 of them leave a guide with nobody, so the answer is 62.
Solution
Count everything first, then take away the bad cases.
1. No rule yet. Tourist 1 picks a guide: choices. Tourist 2 picks: choices. And so on for all tourists. That gives
2. Bad cases. The rule fails only when one guide gets nobody. That happens in exactly ways: all six go with the first guide, or all six go with the second guide.
3. Take them away. .
The answer is .
Why this works
"Each group gets at least one" is often easiest to handle by counting all the ways and removing the few that break the rule. Here the bad cases are just two, and they are easy to list. The guides are different people, so the two bad cases are different, which is why we subtract and not .
Alternative approach
Count by how many tourists go with the first guide. It can be or (not and not ). The number of ways to choose that many tourists out of is
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Ignore the restriction first. Each of the six tourists has two choices of guide, and the choices are independent, so there are ways to assign tourists to guides.
Exactly two of those assignments violate the rule: all six choose the first guide, or all six choose the second. Remove them:
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
- Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.3)
- Introduction to Counting & Probability, Chapter 4: Committees and Combinations
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.