Maths Olympiad Prep

Library / /1 of 41

Combinatorics Difficulty 4.1 AIME Find the answer New Zealand

Problem:

How many positive integers less than 20192019 are divisible by either 1818 or 2121, but not both?

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

Solution

Solution:

For any positive integer nn, the number of multiples of nn less than or equal to 20192019 is given by
2019n.\left\lfloor \frac{2019}{n} \right\rfloor.
So there are 201918=112\left\lfloor \frac{2019}{18} \right\rfloor = 112 multiples of 1818, and 201921=96\left\lfloor \frac{2019}{21} \right\rfloor = 96 multiples of 2121. Moreover, since lcm(18,21)=126\operatorname{lcm}(18,21) = 126 there are 2019126=16\left\lfloor \frac{2019}{126} \right\rfloor = 16 positive integers less than 20192019 which are a multiple of both 1818 and 2121.

Therefore the final answer is
201918+20192122019126=112+962×16=176. \left\lfloor \frac{2019}{18} \right\rfloor + \left\lfloor \frac{2019}{21} \right\rfloor - 2\left\lfloor \frac{2019}{126} \right\rfloor = 112 + 96 - 2 \times 16 = 176.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.