Discrete Math
posted by Francesca
Is this correct?
• Using the Principle of InclusionExclusion, find the number of integers between 1 and 2000 (inclusive) that are divisible by at least one of 2, 3, 5, 7.
A = {n 1 ≤ n ≤ 2000, 2 n}
B = {n 1 ≤ n ≤ 2000, 3 n}
C = {n 1 ≤ n ≤ 2000, 5 n}
D = {n 1 ≤ n ≤ 2000, 7 n}
A = [2000/2] = 1000
B = [2000/3] = 666
C = [2000/5] = 400
D = [2000/7] = 285
Also, I'm kind of confused with how to approach this problem:
• John Sununus was once the governor of New Hampshire, and his name reminds one of the authors of a palindrome (a words which is spelt the same way forwards as backwards, such as SUNUNUS).
How many sevenletter palindromes (not necessarily real words) begin with the letter S and contain at most three letter?
Thanks for any helpful replies!

Count Iblis
You can add up the A , B etc. and then say that you have double counted the elements that are in both A and B, A and C, etc. etc. So, you subtract these. But then you have counted the elements that are in the intersection of A, B and C a total of zero times, because they are counted in
A one time
B one time
C one time
Intersection of A and B minus 1 time
Intersection of A and c minus 1 time
Intersection of B and C minus 1 time
So, you need to add the number of elements in the intersection of A, B and C, and thus also all other pairs of intersections of 3 sets.
Proceeding in this way, you will find the usual inclusionexclusion rule. You can derive this more formally, by first computing the number of elements that are not divisible by any of the numbers.
You can then directly apply the inclusionexclusion formula in its usual formulation, so you then find that this is the total number of elements minus A, minus B,.. plus A intersection B, etc. etc. etc.
This is then also N minus the number of elements divisible by either of the numbers, you get the same result. 
Francesca
Okay I continued the first problem:
A ∩ B = [2000/6] = 333
B ∩ C = [2000/15] = 133
C ∩ D = [2000/35] = 57
A ∩ D = [2000/14] = 142
A ∩ B ∩ C ∩ D = [2000/210] = 9
1000 + 666 + 400 + 285  333  133  57  142 + 9 = 1695 <Answer 
James
I too am having trouble with that SUNUNUS problem, any idea how to approach it?

Francesca
Any suggestions?

James
The only thing I can think of is starting with the method from the first problem and plugging in the numbers? How have you started it?

Francesca
To be honest I haven't started yet, but your method sounds like a step in the right direction. . .I'll play around with it for a little and see what I get. . .If you figure out anything post. Hopefully someone who knows something will post cuz I'm lost

James
Yeah same here and it's due tomorrow lol. So far I got this for #2 but I think it's wrong.
A.) 1 x 26 x 25 x 24 = 15,600
B.) 26 x 25 x 24 x 23 = 14,398
C.) 25 x 24 x 23 = 13,800 
MathMate
Francesca,
INCLUSION/EXCLUSION PRINCIPLE:
Your post: 20110412T15:08
I believe the present problem can be solved using the principle to calculate the count of numbers NOT divisible by ANY of the 4 factors (2,3,5,7). Subtract that from 2000 to get the count of numbers divisible by at least one of the four factors.
The inclusion/exclusion principle works as follows:
For a two set case, and using u to denote the cardinality of the universal set (2000),
a=count of numbers divisible by 2,
b=count of numbers divisible by 3, then
ab=count of numbers not divisible by 2*3 (i.e. A∩B)
Count of numbers NOT divisible by either factor (2 or 3) is:
N̅=u(a+b)+ab
=2000(1000+666)+333
=667
For the case of 3 factors,
N̅=u(a+b+c)+(ab+bc+ca)(abc)
For the case of 4 factors:
N̅=u  (a+b+c+d) + (ab+ac+ad+bc+bd+cd)  (abc+abd+bcd+acd) +abcd
where
a=count of numbers divisible by 2
ab=count of numbers divisible by 2*3
abc=count of numbers divisible by 2*3*5
abcd=count of numbers divisible by 2*3*5*7
If you proceed this way, you should get the count of numbers NOT divisible by any of the 4 factors as:
N̅=20002351+960160+9=458
So the count of numbers divisible by AT LEAST one of the four factors 2,3,5,7 is 2000458=1542.
If you have questions, please post.
Respond to this Question
Similar Questions

discrete math
Find how many positive integers with exactly four decimal digits, that is, positive integers between 1000 and 9999 inclusive, have the following properties: (a) are divisible by 5 and by 7. (b) have distinct digits. (c) are not divisible … 
Discrete Math
1.Using the principle of inclusionexclusion find the numbers of integers between 1 and 1000 (inclusive)that are divisible by at least one of 2,3,5,or 7? 
math
The integers from 1 through 10 (inclusive) are divided into three groups, each containing at least one number. These groups satisfy the additional property that if x is in a group and 2x≤10, then 2x is in the same group. How … 
math
The integers from 1 through 10 (inclusive) are divided into three groups, each containing at least one number. These groups satisfy the additional property that if x is in a group and 2x≤10, then 2x is in the same group. How … 
heeeeeeeeeeelp math
The integers from 1 through 10 (inclusive) are divided into three groups, each containing at least one number. These groups satisfy the additional property that if x is in a group and 2x≤10, then 2x is in the same group. How … 
heeeeeeeeeeeeelp math
The integers from 1 through 10 (inclusive) are divided into three groups, each containing at least one number. These groups satisfy the additional property that if x is in a group and 2x≤10, then 2x is in the same group. How … 
math
The integers from 1 through 10 (inclusive) are divided into three groups, each containing at least one number. These groups satisfy the additional property that if x is in a group and 2x≤10, then 2x is in the same group. How … 
Math
What is the smallest natural number divisible by each of the integers 110, inclusive? 
Maths
How many integer solutions of x1 + x2 + … x6 = 20 satisfies 1 ≤ xi ≤ 9? 
Math
Find the sum of all integers between 1200 and 2900, inclusive, which are not divisible by 9.