2008/09 AHSMC Part 1 Problem 15

Problem 15 of 16

A country has $100$ cities numbered from $1$ to $100$ . For all $m < n$ , there is a road linking the $m$ -th and the $n$ -th city if and only if $\dfrac{n}{m}$ is a prime number. One can travel in either direction on a road. The minimum number of roads one needs to use to go from the $99$ th city to the $100$ th city is

Show solution

Solution

In moving from city to city, we either pick up an extra prime or discard one. The numbers of prime divisors of $99 = 3 \times 3 \times 11$ and $100 = 2 \times 2 \times 5 \times 5$ are $3$ and $4$ respectively, and there are no common divisors. To change from one lot to the other, we need to make $7$ moves. The answer is (D).

University of Alberta

Answer choices

Solution