2023 AMC 10A Problem 14

P11-15~4 minPrint

Conditional Probability & States Divisibility & Factors Map the objects to something easier to count Exploit symmetry to reduce work or pair up objects

A number is chosen at random from among the first $100$ positive integers, and a positive integer divisor of that number is then chosen at random. What is the probability that the chosen divisor is divisible by $11$ ?

Show solution without answering

Key insight

Only the 9 multiples of 11 up to 99 can work. For each, exactly half its divisors are multiples of 11, because each divisor d pairs with 11 times d.

Solution

There are two random steps: first pick a number, then pick one of its divisors.

1. Which numbers can work? If a divisor is a multiple of $11$ , the number itself must be a multiple of $11$ . From $1$ to $100$ these are $11, 22, 33, \ldots, 99$ : $9$ numbers. So the first step succeeds with probability $\frac{9}{100}$ .
2. Look at one example. Take $22$ . Its divisors are $1, 2, 11, 22$ . The ones divisible by $11$ are $11$ and $22$ : $2$ out of $4$ , exactly half.
3. Another example. Take $66 = 11 \times 6$ . The divisors of $6$ are $1, 2, 3, 6$ . The divisors of $66$ are those four, plus $11, 22, 33, 66$ (each one times $11$ ). Again exactly half are multiples of $11$ .
4. Why it is always half. Each of the nine numbers is $11 \times k$ with $k$ from $1$ to $9$ , so $11$ appears only once. Its divisors split into two groups of the same size: the divisors of $k$ (no factor $11$ ), and those same divisors times $11$ . So the second step succeeds with probability $\frac12$ every time.
5. Multiply the two steps:
$\frac{9}{100} \times \frac12 = \frac{9}{200}.$

The answer is $\boxed{\textbf{(B)}\ \frac{9}{200}}$ .

Why this works

When a random choice happens in two steps, multiply the chance of a good first step by the chance of a good second step. The second chance looks like it should change from number to number, but the pairing " $d$ goes with $11 \times d$ " shows it is always one half. This works whenever a prime appears exactly once in a number: half the divisors include it and half do not.

Concise solution

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

A divisor divisible by $11$ can only come from a number that is itself divisible by $11$ . Among $1, \ldots, 100$ these are $11, 22, \ldots, 99$ : nine numbers, each of the form $11k$ with $1 \le k \le 9$ . Since $k < 11$ , the factor $11$ appears exactly once in each.

For such a number $n = 11k$ , pair each divisor $d$ of $k$ with $11d$ . The divisors of $n$ not divisible by $11$ are exactly the divisors of $k$ , and the divisors divisible by $11$ are exactly the numbers $11d$ . The pairing is a perfect match, so exactly half of the divisors of $n$ are multiples of $11$ .

Therefore the probability is
$\frac{9}{100} \cdot \frac12 = \frac{9}{200}.$

The answer is $\boxed{\textbf{(B)}\ \frac{9}{200}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.5)
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)