HMMT, 2014

Number theory Difficulty 5.1 AIME, harder Prove it United States

Problem:

Let $D$ be the set of divisors of $100$ . Let $Z$ be the set of integers between $1$ and $100$ , inclusive. Mark chooses an element $d$ of $D$ and an element $z$ of $Z$ uniformly at random. What is the probability that $d$ divides $z$ ?

Solution

Solution:

The answer is $\frac{217}{900}$ .

As $100 = 2^{2} \cdot 5^{2}$ , there are $3 \cdot 3 = 9$ divisors of $100$ , so there are $900$ possible pairs of $d$ and $z$ that can be chosen.

If $d$ is chosen, then there are $\frac{100}{d}$ possible values of $z$ such that $d$ divides $z$ , so the total number of valid pairs of $d$ and $z$ is $\sum_{d \mid 100} \frac{100}{d} = \sum_{d \mid 100} d = (1 + 2 + 2^{2})(1 + 5 + 5^{2}) = 7 \cdot 31 = 217$ .

The answer is therefore $\frac{217}{900}$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.