How many integers in the range [1,999] are divisible by exactly 1 of 7 and 11?

Question

This is a question in Kenneth Rosen's Discrete Mathematics textbook 6th edition. I haven't had trouble with any other counting problems regarding "how many numbers in range [x,y] have divisibility property Z?" My issue is I have no idea what Rosen is asking for, i.e. I don't understand the question because I don't know what he wants me to compute.

Therefore this is not a duplicate of this question (1) https://math.stackexchange.com/questions/588160/how-many-positive-integers-less-than-1000-are-divisible, since while the answer is given, it doesn't explain the language of the question and what is being computed. I have no idea why the number of integers divisible by 7 or 11 minus the number of integer divisible by 77 (11 and 7) is the answer to this question. Both of these values I've already computed correctly (in separate questions).

In context: 20. How many positive integers less than 1000 e) are divisible by exactly one of 7 and 11?

Thus my question is: what/which numbers am I supposed to count/compute?

Answer 1

Call the numbers we are looking for good. A number is good if it is divisible by $7$ but not by $11$, or divisible by $11$ but not by $7$. That's what "divisible by exactly $1$ of $7$ and $11$" means.

Let $a$ be the number of numbers from $1$ to $999$ which are divisible by $7$, and let $b$ be the number of numbers which are divisible by $11$. If we add $a$ and $b$, we will have counted the numbers that are divisible by both $7$ and $11$ twice. However, we should not have counted them at all, they are not good.

So to get the count of the good numbers, we should find $a+b$, and take away twice the number of numbers that are divisible by both $7$ and $11$, like $77$, $154$, and a number of others.

Now the counts are straightforward. Let's find $a$. So we are counting the numbers $7\cdot 1$, $7\cdot 2$, $7\cdot 3$, and so on. What is the biggest $k$ such that $7\cdot k\le 999$? Note that $\frac{999}{7}\approx 142.71$. So the biggest integer $k$ such that $7\cdot k\le 999$ is $142$. It follows that $a=142$.

Finding $b$, and finding the number of numbers $\le 999$ divisible by $77$ is done similarly.

Answer 2

Let's look at a smaller example: the positive integers less than $10$ that are divisible by exactly one of $2$ and $3$.

Well, $2, 4, 6, 8$ are divisible by $2$, and $3, 6, 9$ are divisible by $3$. There are $6$ positive integers that are less than $10$ that are divisible by $2$ or $3$.

But, $6$ is divisible by both $2$ and $3$. We only should consider integers that are divisible by $2$ or $3$ but not both. So, we have $6-1=5$ integers that are divisible by exactly one of $2$ and $3$.

Does that help?

Answer 3

This question can be solved using PIE or Principle of Inclusion and Exclusion, which is a very useful technique in the field of combinatorics.

For the question you've got here, we let $A$ (see Venn Diagram below) be the set of natural numbers less than $1000$ that is divisible by $7$; whereas let $B$ be the set of natural numbers less than $1000$ that is divisible by $11$.

From the diagram, it is clear that we want the areas of $A + B - A \cap B$, where $A \cap B$ refers the intersection of sets $A, B$. Therefore, the number of integers divisible by $7$ or $11$ minus the number of natural numbers divisible by $77$ ($11$ and $7$) is the answer to the question.

In general, for the question asking how many natural numbers less than $k \in \mathbb{Z}$ which is divisible by the integers in the set ${a_1, a_2, \ldots a_n}$, we can represent the question in terms of $n$ sets (or circles in the Venn diagram) and then solve from there.

P.S. How can I adjust the size of the image???

Answer 4

Venn diagrams might help your intuition on this.

You've got two sets, $A$ an $B$; and some way to "count" sets (when we look at a Venn diagram we immediately think "area"; for your problem it's "elements divisible by"). If you want to "count" $A \cup B$, what you want is to "count" $A$, and "count" $B$" and sum them, but because you've "counted" the part of $A$ which is also part of $B$ as part of "count" of $A$ as well as for the "count" of $B$, you subtract the "count" of $A \cap B$ - which is (for your example) the elements divisible by 7 AND by 11.

This is formalized as "the inclusion-exclusion principle", which I encourage you to google!