MOG 2019 Q3
Seth wants to know how many positive whole numbers from one to one hundred are divisible by two or five. He thinks that the answer is 70 because there are fifty multiples of two and twenty multiples of five from one to one hundred. Explain why his answer is too large.(2 marks)
Consider the list of 1800 fractions\[\frac{1}{1800}, \frac{2}{1800}, \dots, \frac{1799}{1800}, \frac{1800}{1800}.\]How many are not in simplest form? Explain your reasoning.(8 marks)
[Note: The fraction \(\frac{900}{1800}\) is not in simplest form because it can be simplified to \(\frac{1}{2}\).]
Mathematical Olympiad for Girls 2019, Question 3. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (b) 1320
Commentary
The main part of the question (part (b)) asks how many of the fractions can be simplified. How can you tell when a fraction can be simplified? Part (a) should help you avoid a common trap when counting multiples.
It may help to start by writing out some multiples of 2 and 5. Which numbers will be listed more than once? This tells you not only why 70 is too large, but also helps you find the correct answer to Seth’s question.
In part (b) you need to think carefully what exactly you want to count. For example, 1800 is divisible by both 3 and 9, but do you need to count the multiples of 3 and 9 separately?
You also need to extend the reasoning from part (a) to avoid Seth’s trap. You may find it helpful to use a Venn diagram to represent the number of multiples.
If we list all 50 multiples of 2 and all 20 multiples of 5, all the multiples of 10 will appear in both lists. Since some numbers are counted twice, the real answer is smaller than 70.
A fraction will not be in simplest form when the numerator shares at least one factor with 1800. Since \(1800 = 2^3 \times 3^2 \times 5^2\), we need to count how many of the numbers from 1 to 1800 are divisible by 2, 3 or 5.
Imagine making three separate lists: one containing the multiples of 2, one containing the multiples of 3 and one containing the multiples of 5. There are \(\frac{1800}{2} = 900\) numbers in the first list, \(\frac{1800}{3} = 600\) in the second and \(\frac{1800}{5} = 360\) in the third, a total of 1860 numbers.
The multiples of 6, 10 and 15 appear twice, so we need to take away \(\frac{1800}{6} + \frac{1800}{10} + \frac{1800}{15} = 600\).
However, the multiples of 30 have now been taken away three times. But they appear three times in the original three lists, so they should have only been taken away twice. Hence we need to add back \(\frac{1800}{30} = 60\).
The required total is therefore \(1860 - 600 + 60 = 1320\). Thus 1320 of the fractions are not in simplest form.
Commentary
Try drawing a Venn diagram to show the number of multiples of 2, 3 and 5. Does that make our calculation clearer?
This idea can be extended to count the total number of elements in more than three overlapping sets, resulting in what is know as the inclusion-exclusion principle.
Solution © UK Mathematics Trust, from the MOG 2019 solutions.