2005 AMC 10B Problem 18

P16-20~2 minPrint

Basic Counting Map the objects to something easier to count

All of David's telephone numbers have the form $555-abc-defg$ , where $a$ , $b$ , $c$ , $d$ , $e$ , $f$ , and $g$ are distinct digits and in increasing order, and none is either $0$ or $1$ . How many different telephone numbers can David have?

Show solution without answering

Key insight

Seven different digits in increasing order can be arranged only one way. So a phone number is fixed by which of the eight digits 2 through 9 is left out.

Solution

Which digits are allowed? Not $0$ or $1$ , so only $2, 3, 4, 5, 6, 7, 8, 9$ . That is $8$ digits.
How many are used? The letters $a$ through $g$ are $7$ different digits. So exactly one of the $8$ allowed digits is not used.
Order is decided for us. Once you know which $7$ digits are used, "increasing order" leaves just one way to write them. For example, if $6$ is left out, the number must be $555$ - $234$ - $5789$ .
Count. So each phone number matches exactly one choice of the digit to leave out. There are $8$ digits that could be left out, so there are $8$ phone numbers.

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

Why this works

"Different digits in increasing order" means the order is not a choice; only the set of digits matters. So count the sets, not the arrangements. Choosing $7$ of $8$ digits is the same as choosing the $1$ digit to leave out, which is much easier to count.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The allowed digits are $2, 3, 4, 5, 6, 7, 8, 9$ : eight of them. The seven positions $a$ through $g$ must be filled with seven distinct allowed digits.

Once we decide which seven digits to use, the increasing-order requirement leaves only one way to place them. So a telephone number corresponds exactly to a choice of $7$ digits out of $8$ , or equivalently to the one digit that is omitted.

There are $8$ digits that could be the omitted one, so there are $8$ telephone numbers.

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

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques
Introduction to Counting & Probability, Chapter 4: Committees and Combinations