Discrete Math

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!

  1. 👍
  2. 👎
  3. 👁
  1. 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.

    1. 👍
    2. 👎
  2. 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

    1. 👍
    2. 👎
  3. I too am having trouble with that SUNUNUS problem, any idea how to approach it?

    1. 👍
    2. 👎
  4. Any suggestions?

    1. 👍
    2. 👎
  5. 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?

    1. 👍
    2. 👎
  6. 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

    1. 👍
    2. 👎
  7. 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

    1. 👍
    2. 👎
  8. 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.

    1. 👍
    2. 👎

Respond to this Question

First Name

Your Response

Similar Questions

  1. chemistry

    Suppose you take a trip to a distant universe and find that the periodic table there is derived from an arrangement of quantum numbers different from the one on Earth. The rules in that universe are: 1. principal quantum number n

  2. calculus

    find two positive integers such that the sum of the first number and 4 times the second number is 1000 and the product of the numbers is as large as possible

  3. algebra

    Find three consecutive even integers such that the sum of the smallest number and twice the middle number is 20 more than the largest number.

  4. Math

    2. The sum of the reciprocals of two consecutive positive integers is 17/72. Write an equation that can be used to find the two integers. What are the integers? Steve helped me yesterday and gave me the hint 8+9=17. Then I thought

  1. Maths help asap please.

    The product of two consecutive positive integers is added to the larger of the two integers. Prove that the result is always a square number. Thank you for your help.

  2. Mathmatics

    Prove algebraically that the difference between the square of any two consecutive integers is equal to the sum of these two integers. First number = n Second number = n+1 Square the second number: (?????)^2 Difference between the

  3. Algebra II

    Choose the correct rewriting of this algebraic fraction and give the exclusion represented by your choice. 4y(8y+24)^ - 1 : 2y/2y+3 OR y/(2)(y+3)? y ≠ : +3 OR -3 ?

  4. Number Line

    If an integer a is pictured on the number line then the distance from the point on the number line that represents the integer to the origin is ƒaƒ. Using this idea answer the following. a. Explain why ƒa 2 bƒ is the distance

  1. Math

    Dori claims that 3.52 is not a rational number because it is not written as a ratio of integers. Is she correct? Explain why or why not.

  2. Pre Calc 12

    Four consecutive integers have a product of 360 Find the integers by writing a plynomial equation that represents the integers and then solving algebraically.

  3. probability

    If a number is chosen at random from the integers 5 to 25 inclusive, find the probability that the number is a) multiple of 5 or 3 b) even or prime numbers c) less or greater than 18

  4. Math

    The sum of four consecutive even integers is the same as the least of the integers. Find the integers. I'm not sure how to solve it and put it in an equation!

You can view more similar questions or ask a new question.