Maths Olympiad Prep

Library / /19 of 128

Combinatorics Difficulty 4.9 AIME Find the answer Philippines

Problem:

How many numbers between 11 and 20162016 are divisible by exactly one of 44, 66, or 1010?

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

Solution

Solution:

Let AA be the set of numbers between 11 and 20162016 divisible by 44.
Let BB be the set of numbers divisible by 66.
Let CC be the set of numbers divisible by 1010.

We are to find A(BC)+B(AC)+C(AB)|A \setminus (B \cup C)| + |B \setminus (A \cup C)| + |C \setminus (A \cup B)|.

First, compute the sizes of the sets:

A=20164=504|A| = \left\lfloor \dfrac{2016}{4} \right\rfloor = 504

B=20166=336|B| = \left\lfloor \dfrac{2016}{6} \right\rfloor = 336

C=201610=201|C| = \left\lfloor \dfrac{2016}{10} \right\rfloor = 201

Now, intersections:

AB|A \cap B| is numbers divisible by lcm(4,6)=12\operatorname{lcm}(4,6) = 12:
AB=201612=168|A \cap B| = \left\lfloor \dfrac{2016}{12} \right\rfloor = 168

AC|A \cap C| is numbers divisible by lcm(4,10)=20\operatorname{lcm}(4,10) = 20:
AC=201620=100|A \cap C| = \left\lfloor \dfrac{2016}{20} \right\rfloor = 100

BC|B \cap C| is numbers divisible by lcm(6,10)=30\operatorname{lcm}(6,10) = 30:
BC=201630=67|B \cap C| = \left\lfloor \dfrac{2016}{30} \right\rfloor = 67

ABC|A \cap B \cap C| is numbers divisible by lcm(4,6,10)=60\operatorname{lcm}(4,6,10) = 60:
ABC=201660=33|A \cap B \cap C| = \left\lfloor \dfrac{2016}{60} \right\rfloor = 33

Now, for exactly one:

Numbers divisible by 44 only:
AABAC+ABC=504168100+33=269|A| - |A \cap B| - |A \cap C| + |A \cap B \cap C| = 504 - 168 - 100 + 33 = 269

Numbers divisible by 66 only:
BABBC+ABC=33616867+33=134|B| - |A \cap B| - |B \cap C| + |A \cap B \cap C| = 336 - 168 - 67 + 33 = 134

Numbers divisible by 1010 only:
CACBC+ABC=20110067+33=67|C| - |A \cap C| - |B \cap C| + |A \cap B \cap C| = 201 - 100 - 67 + 33 = 67

Total: 269+134+67=470269 + 134 + 67 = 470

Answer: 470470

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.