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?
- A)
- B)
- C)
- D)
- E)
Answer
D
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
The trap
Dividing by 2 because the two groups seem interchangeable. The guides are different people, so sending everyone to one guide differs from sending everyone to the other.
Concise solution
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
Techniques
Count the complement and subtract from the total