Olympiad Maths Prep

Track / Stage 6 / 192 of 400 #1192 of 2000

Problem 1192

National olympiad, first round
Combinatorics Difficulty 6.3 Find the answer

Compute the number of positive integers less than or equal to 20152015 that are divisible by 55 or 1313, but not both.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Count the numbers divisible by 5:
20155=403 \left\lfloor \frac{2015}{5} \right\rfloor = 403
So, there are 403 numbers less than or equal to 2015 that are divisible by 5.

2. Count the numbers divisible by 13:
201513=155 \left\lfloor \frac{2015}{13} \right\rfloor = 155
So, there are 155 numbers less than or equal to 2015 that are divisible by 13.

3. Count the numbers divisible by both 5 and 13 (i.e., divisible by their least common multiple, 65):
201565=31 \left\lfloor \frac{2015}{65} \right\rfloor = 31
So, there are 31 numbers less than or equal to 2015 that are divisible by 65.

4. Apply the Principle of Inclusion and Exclusion (PIE):
The number of integers less than or equal to 2015 that are divisible by 5 or 13 is given by:
403+15531=527 403 + 155 - 31 = 527

5. Count the numbers divisible by both 5 and 13 (i.e., divisible by 65) again to exclude them:
Since we need the numbers divisible by 5 or 13 but not both, we subtract the numbers divisible by 65 from the total:
52731=496 527 - 31 = 496

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