2002 AMC 10B Problem 9

P1-10~2 minPrint

Basic Counting Set up the equation/formula and compute; no special trick needed

Using the letters $A$ , $M$ , $O$ , $S$ , and $U$ , we can form five-letter "words". If these "words" are arranged in alphabetical order, then the "word" $USAMO$ occupies position

Show solution without answering

Key insight

Count the words that come before USAMO in blocks: first all words starting with A, M, O or S, then the words starting UA, UM or UO. USAMO is next.

Solution

In alphabetical order the letters go $A, M, O, S, U$ . The plan is to count how many words come before $USAMO$ , then add $1$ .

Words starting with an earlier letter than $U$ . The first letter can be $A$ , $M$ , $O$ or $S$ ( $4$ choices). The other four letters can then be arranged in $4 \times 3 \times 2 \times 1 = 24$ ways. That is $4 \times 24 = 96$ words.
Words starting with $U$ whose second letter is earlier than $S$ . The second letter can be $A$ , $M$ or $O$ ( $3$ choices), and the last three letters can be arranged in $3 \times 2 \times 1 = 6$ ways. That is $3 \times 6 = 18$ words.
Words starting with $US$ . The last three letters are $A$ , $M$ , $O$ . The first such word puts them in alphabetical order: $USAMO$ itself.
So $96 + 18 = 114$ words come before $USAMO$ , and $USAMO$ is word number $115$ .

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

Why this works

Alphabetical order sorts by the first letter, then breaks ties with the second letter, and so on. So the words before a target come in blocks, one block for each smaller letter you could have put in each position. Each block has size "number of arrangements of the letters still unused." Remember the last step: words before it plus one gives its position.

Alternative approach

Count from the end. There are $5 \times 4 \times 3 \times 2 \times 1 = 120$ words in total. The ones after $USAMO$ all start with $US$ and put $A, M, O$ in a later order: $USAOM$ , $USMAO$ , $USMOA$ , $USOAM$ , $USOMA$ . That is $5$ words, so $USAMO$ is number $120 - 5 = 115$ .

Concise solution

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

Alphabetically the letters are $A < M < O < S < U$ . Count how many words are listed before $USAMO$ .

First letter earlier than $U$ : any of $A, M, O, S$ , followed by any arrangement of the other four letters. That is $4 \cdot 4! = 96$ words.

First letter $U$ , second letter earlier than $S$ : the second letter is $A$ , $M$ or $O$ , then any arrangement of the remaining three. That is $3 \cdot 3! = 18$ words.

First two letters $US$ : the remaining letters $A, M, O$ in alphabetical order spell $AMO$ , so $USAMO$ is the first word in this block.

So $96 + 18 = 114$ words precede $USAMO$ , and it sits in position $115$ .

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

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques
Introduction to Counting & Probability, Chapter 4: Committees and Combinations