5
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for this answer. This one answered my question in the first two sentences! $\endgroup$ – user3898238 Sep 13 '14 at 4:58
  • $\begingroup$ You are welcome. $\endgroup$ – André Nicolas Sep 13 '14 at 5:01
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Should be 6 - 1 = 5 numbers. $\endgroup$ – paw88789 Sep 13 '14 at 4:27
  • $\begingroup$ @paw88789 Wow... thanks. I must be more tired than I thought. $\endgroup$ – apnorton Sep 13 '14 at 4:29
4
$\begingroup$

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.

Venn Diagram of 2 Sets

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???

$\endgroup$
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.