CombinatoricsDifficulty 4.1AIMEFind the answerNew Zealand
Problem:
How many positive integers less than 2019 are divisible by either 18 or 21, 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 n, the number of multiples of n less than or equal to 2019 is given by ⌊n2019⌋. So there are ⌊182019⌋=112 multiples of 18, and ⌊212019⌋=96 multiples of 21. Moreover, since lcm(18,21)=126 there are ⌊1262019⌋=16 positive integers less than 2019 which are a multiple of both 18 and 21.
Therefore the final answer is ⌊182019⌋+⌊212019⌋−2⌊1262019⌋=112+96−2×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.