Maths Olympiad Prep

Library / /85 of 860

Number theory Difficulty 4.8 AIME Find the answer

Let DD be the set of divisors of 100. Let ZZ be the set of integers between 1 and 100, inclusive. Mark chooses an element dd of DD and an element zz of ZZ uniformly at random. What is the probability that dd divides zz?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

As 100=2252100=2^{2} \cdot 5^{2}, there are 33=93 \cdot 3=9 divisors of 100, so there are 900 possible pairs of dd and zz that can be chosen. If dd is chosen, then there are 100d\frac{100}{d} possible values of zz such that dd divides zz, so the total number of valid pairs of dd and zz is d100100d=d100d=(1+2+22)(1+5+52)=731=217\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 217900\frac{217}{900}.

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

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.