Maths Olympiad Prep

Library / NZMO Round One /1 of 39

NZMO Round One

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⌋+⌊201921⌋−2⌊2019126⌋=112+96−2×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,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.