2015 AMC 10B Problem 16

P16-20~4 minPrint

Basic Probability Divisibility & Factors Organized listing / direct enumeration Split into exhaustive cases and handle each

Al, Bill, and Cal will each randomly be assigned a whole number from $1$ to $10$ , inclusive, with no two of them getting the same number. What is the probability that Al's number will be a whole number multiple of Bill's and Bill's number will be a whole number multiple of Cal's?

Show solution without answering

Key insight

Each number must be a bigger multiple of the next, so Cal gets 1 or 2. There are 9 good outcomes out of 720.

Solution

1. Count all outcomes. Al can get any of $10$ numbers, then Bill any of the $9$ left, then Cal any of the $8$ left. That is $10 \cdot 9 \cdot 8 = 720$ equally likely outcomes.
2. Understand the good outcomes. Al's number is a multiple of Bill's, and Bill's is a multiple of Cal's. Since the numbers are all different, each multiple must be at least double. So Cal < Bill < Al, with Al at most $10$ .
3. Cal's number is small. If Cal had $3$ or more, Bill would need at least $6$ and Al at least $12$ , which is too big. So Cal has $1$ or $2$ .
4. Cal has 1. Every number is a multiple of $1$ , so Bill can be anything that still leaves room for Al:
- Bill $2$ : Al is $4, 6, 8$ or $10$ . That is $4$ ways.
- Bill $3$ : Al is $6$ or $9$ . That is $2$ ways.
- Bill $4$ : Al is $8$ . That is $1$ way.
- Bill $5$ : Al is $10$ . That is $1$ way.
- Bill $6$ or more: the next multiple is at least $12$ . No ways.

That makes $8$ good outcomes.
5. Cal has 2. Bill must be a multiple of $2$ and Al a multiple of Bill. Bill $4$ with Al $8$ is the only choice (Bill $6$ , $8$ or $10$ leaves no room for Al). That is $1$ good outcome.
6. Probability. There are $8 + 1 = 9$ good outcomes, so the probability is
$\frac{9}{720} = \frac{1}{80}.$

The answer is $\boxed{\textbf{(C)}\ \frac{1}{80}}$ .

Why this works

A chain of different numbers where each divides the next has to at least double at every step. That makes the smallest number tiny, and the list of cases is short. Start with the most limited person (Cal) and build outward. Also make sure the top and bottom of the probability count the same kind of thing: here both count who-gets-which-number assignments, where order matters.

Concise solution

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

The assignment is an ordered triple of distinct numbers, so there are $10 \cdot 9 \cdot 8 = 720$ equally likely outcomes.

Let the numbers be $a$ (Al), $b$ (Bill), $c$ (Cal) with $b \mid a$ and $c \mid b$ . Since the numbers are distinct, each multiple is a proper multiple, so $c < b < a \le 10$ . In particular $c \le 2$ (if $c \ge 3$ then $b \ge 6$ and $a \ge 12$ ).

Case $c = 1$ : choose $b$ , then $a$ a larger multiple of $b$ up to $10$ .
- $b = 2$ : $a \in \{4, 6, 8, 10\}$ , $4$ ways.
- $b = 3$ : $a \in \{6, 9\}$ , $2$ ways.
- $b = 4$ : $a = 8$ , $1$ way.
- $b = 5$ : $a = 10$ , $1$ way.
- $b \ge 6$ : no $a$ .

That is $8$ triples.

Case $c = 2$ : $b \in \{4, 6, 8, 10\}$ , and $a$ must be a larger multiple of $b$ at most $10$ ; only $b = 4$ , $a = 8$ works. That is $1$ triple.

Total favorable: $8 + 1 = 9$ . The probability is $\frac{9}{720} = \frac{1}{80}$ .

The answer is $\boxed{\textbf{(C)}\ \frac{1}{80}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)