Maths Olympiad Prep

Library / /11 of 29

Combinatorics Difficulty 5.4 AIME, harder Prove it Croatia

How many positive integers less than 20112011 are divisible by either 22 or 77, but are not divisible by 55?

Solution

Let N=2011N = 2011.

Let AA be the set of positive integers less than 20112011 divisible by 22 or 77.
Let BB be the set of positive integers less than 20112011 divisible by 55.
We are to find AB|A \setminus B|.

First, count the number of positive integers less than 20112011 divisible by 22 or 77.

Let S2S_2 be the set divisible by 22.
Let S7S_7 be the set divisible by 77.
Let S14S_{14} be the set divisible by 1414.

Number divisible by 22: 20102=1005\left\lfloor \dfrac{2010}{2} \right\rfloor = 1005
Number divisible by 77: 20107=287\left\lfloor \dfrac{2010}{7} \right\rfloor = 287
Number divisible by 1414: 201014=143\left\lfloor \dfrac{2010}{14} \right\rfloor = 143

By inclusion-exclusion:
Number divisible by 22 or 77 is 1005+287143=11491005 + 287 - 143 = 1149.

Now, subtract those divisible by 55.

Let S2,5S_{2,5}: divisible by 22 and 55 (1010)
201010=201\left\lfloor \dfrac{2010}{10} \right\rfloor = 201

Let S7,5S_{7,5}: divisible by 77 and 55 (3535)
201035=57\left\lfloor \dfrac{2010}{35} \right\rfloor = 57

Let S14,5S_{14,5}: divisible by 1414 and 55 (7070)
201070=28\left\lfloor \dfrac{2010}{70} \right\rfloor = 28

By inclusion-exclusion, the number of integers less than 20112011 divisible by 22 or 77 and also by 55 is:
201+5728=230201 + 57 - 28 = 230

Therefore, the answer is 1149230=9191149 - 230 = 919.

Answer: 919919

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.