AMC 10 Step by Step

2007 AMC 10A Problem 12

P11-15~2 minPrint

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?

Log in to save your progress.
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: 22 choices. Tourist 2 picks: 22 choices. And so on for all 66 tourists. That gives
2×2×2×2×2×2=64 ways.2 \times 2 \times 2 \times 2 \times 2 \times 2 = 64 \text{ ways}.
2. Bad cases. The rule fails only when one guide gets nobody. That happens in exactly 22 ways: all six go with the first guide, or all six go with the second guide.
3. Take them away. 64−2=6264 - 2 = 62.

The answer is (D) 62\boxed{\textbf{(D)}\ 62}.

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 22 and not 11.

Alternative approach

Count by how many tourists go with the first guide. It can be 1,2,3,41, 2, 3, 4 or 55 (not 00 and not 66). The number of ways to choose that many tourists out of 66 is
6+15+20+15+6=62.6 + 15 + 20 + 15 + 6 = 62.

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 26=642^6 = 64 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:
64−2=62.64 - 2 = 62.

The answer is (D) 62\boxed{\textbf{(D)}\ 62}.

Review in the AoPS books

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.