Is this correct?
• Using the Principle of Inclusion-Exclusion, 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 seven-letter palindromes (not necessarily real words) begin with the letter S and contain at most three letter?
Thanks for any helpful replies!
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
I too am having trouble with that SUNUNUS problem, any idea how to approach it?
Any suggestions?
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?
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
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
Francesca,
INCLUSION/EXCLUSION PRINCIPLE:
Your post: 2011-04-12T15: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̅=2000-2351+960-160+9=458
So the count of numbers divisible by AT LEAST one of the four factors 2,3,5,7 is 2000-458=1542.
If you have questions, please post.
i was 1
Yes, your approach is correct for the first question. You defined sets A, B, C, and D to represent the numbers divisible by 2, 3, 5, and 7 respectively. You found the cardinality (number of elements) of each set by dividing 2000 by the respective number. Since the numbers could be repeated (e.g. a number that is divisible by both 2 and 3), you haven't considered the intersections between sets yet.
To find the number of integers between 1 and 2000 (inclusive) that are divisible by at least one of 2, 3, 5, or 7, you need to apply the Principle of Inclusion-Exclusion.
The Principle of Inclusion-Exclusion states that to find the cardinality of the union of multiple sets, you need to subtract the sum of the cardinalities of the individual sets, then add the sum of the cardinalities of the intersections of each pair of sets, then subtract the sum of the cardinalities of the intersections of each triplet of sets, and so on.
Applying the principle to this problem, you need to subtract the sum of |A|, |B|, |C|, and |D| from the sum of |A∩B|, |A∩C|, |A∩D|, |B∩C|, |B∩D|, and |C∩D|. Then you add back the sum of |A∩B∩C|, |A∩B∩D|, |A∩C∩D|, and |B∩C∩D|. Finally, you subtract |A∩B∩C∩D| to get the number of integers between 1 and 2000 (inclusive) that are divisible by at least one of 2, 3, 5, or 7.
For the second question, let's break it down step by step.
To form a seven-letter palindrome that begins with 'S' and contains at most three different letters, you have the following possibilities:
1. The first letter is 'S', and the remaining six letters can all be 'S'.
2. The first letter is 'S', and the remaining six letters contain two different letters (one of which is 'S').
3. The first letter is 'S', and the remaining six letters contain three different letters (one of which is 'S').
For the first case, there is only one possibility: 'SSSSSSS'.
For the second case, you have 'S' as the first letter, and the remaining six letters can be any of the other 25 letters of the alphabet. So, there are 25 possibilities for each of the remaining six positions, resulting in 25^6 possibilities.
For the third case, you have 'S' as the first letter, and the remaining six letters contain two different letters, one of which is 'S'. There are 25 choices for the first distinct letter, and 24 choices for the second distinct letter. The positions of these two distinct letters can be chosen in C(6, 2) ways. The remaining three positions can be filled with 'S', resulting in 25 * 24 * C(6, 2) possibilities.
To find the total number of palindromes, you sum up the possibilities for each case:
Total number of palindromes = 1 + 25^6 + 25 * 24 * C(6, 2)
I hope this helps!
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 inclusion-exclusion 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 inclusion-exclusion 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.