Results 1 to 7 of 7

Math Help - Divisibility

  1. #1
    Junior Member
    Joined
    Feb 2006
    From
    Canada
    Posts
    45

    Divisibility

    Find the number of positive integers not exceeding 1000 that are not divisible by 3 or 5
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by suedenation View Post
    Find the number of positive integers not exceeding 1000 that are not divisible by 3 or 5

    There are 333 numbers that are divisible by 3 since 333*3=999.

    Among those 333 numbers there are 66 numbers that are also divisble by 5 since 333/5 =66.6
    So 333-66 = 267 numbers that are divisble only by 3.

    There are 200 numbers that are divisible by 5 since 200*5 = 1000.
    Among those 200 numbers there are 66 numbers that are also divisble by 3.
    So 200-66 = 134 numbers that are divisible only by 5.

    267 - numbers that are divisible only by 3.
    134 - numbers that are divisible only by 5.
    66 - numbers that are divisble both by 3 and 5.

    So we have 267+134+66 = 467 numbers that are divisble either by 3 or 5.

    1000-467 = 533 numbers that are not divisble either by 3 or 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by suedenation View Post
    Find the number of positive integers not exceeding 1000 that are not divisible by 3 or 5
    Here is an excellent demonstration of the Inclusion Exclusion Principle.
    Let

    B be the set of all integers from 1 to 1000 divisible by 3
    C be the set of all integers from 1 to 1000 divisible by 5

    By the Inclusion Exclusion Principle we have,
    |B u C|=|B| + |C| - |B n C|
    Now,
    |B n C| is the set of all numbers divisible by 3 and 5. Since gcd (3,5)=1 it is equivalent to saying divisible by 15.
    Let us count number of such integers,
    15,30,45,...,990
    Or in more elegant form,
    15(1),15(2),15(3),...,15(66)
    We can easily see 66 such integers exist
    Thus,
    |B n C|=66.
    You can easily find that,
    |B|=333
    |C|=200
    Thus,
    |B u C|=333+200-66=467
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker View Post
    Here is an excellent demonstration of the Inclusion Exclusion Principle.
    Let

    B be the set of all integers from 1 to 1000 divisible by 3
    C be the set of all integers from 1 to 1000 divisible by 5

    By the Inclusion Exclusion Principle we have,
    |B u C|=|B| + |C| - |B n C|
    Now,
    |B n C| is the set of all numbers divisible by 3 and 5. Since gcd (3,5)=1 it is equivalent to saying divisible by 15.
    Let us count number of such integers,
    15,30,45,...,990
    Or in more elegant form,
    15(1),15(2),15(3),...,15(66)
    We can easily see 66 such integers exist
    Thus,
    |B n C|=66.
    You can easily find that,
    |B|=333
    |C|=200
    Thus,
    |B u C|=333+200-66=467
    Elegant solution, better then mine. I like it.

    I thought also of counting numbers divisible by 15.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    Here is an excellent demonstration of the Inclusion Exclusion Principle.
    Let

    B be the set of all integers from 1 to 1000 divisible by 3
    C be the set of all integers from 1 to 1000 divisible by 5

    By the Inclusion Exclusion Principle we have,
    |B u C|=|B| + |C| - |B n C|
    Now,
    |B n C| is the set of all numbers divisible by 3 and 5. Since gcd (3,5)=1 it is equivalent to saying divisible by 15.
    Let us count number of such integers,
    15,30,45,...,990
    Or in more elegant form,
    15(1),15(2),15(3),...,15(66)
    We can easily see 66 such integers exist
    Thus,
    |B n C|=66.
    You can easily find that,
    |B|=333
    |C|=200
    Thus,
    |B u C|=333+200-66=467
    I'm writing that one down. That's like, a cool theorem. (I may ask for a proof later...)

    Now let's see if I can give you a rep point, always a task of considerable uncertainty.

    -Dan

    No joy on the rep. Sowwy! (Grumbles) Now I'll have to seriously consider giving Quick some...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    That theorem is the mathematical side of the Venn Diagram.
    ---
    In case you did not understand that crazy notation on Wikipedia heir is the general pattern.

    |A u B u C|=|A| + |B| +|C| - |A n B|-|A n C|-|B n C|+|A n B n C|

    If you have 4,

    |A u B u C u D|=|A|+|B|+|C|+|D|-|A n B| -|A n C| -|A n D| -|B n C|- |B n D| - |C n D|+|A n B n C|+|A n B n D|+|A n C n D| +|B n C n D|-|A n B n C n D|

    In general the number of terms is the sum of of binomials from 1 to n thus, it is, 2^n -1

    Actually the result is easy to prove.
    You need to Justify,
    |A u B|=|A| + |B| -|A n B|
    Then,
    |A u B u C|=|A u (B u C)|=|A|+|B u C|-|A n B n C|
    Get the idea, (just induction argument).

    From here you should realize how it gets its name, Inculsion-Exclusion.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    That theorem is the mathematical side of the Venn Diagram.
    ---
    In case you did not understand that crazy notation on Wikipedia heir is the general pattern.

    |A u B u C|=|A| + |B| +|C| - |A n B|-|A n C|-|B n C|+|A n B n C|

    If you have 4,

    |A u B u C u D|=|A|+|B|+|C|+|D|-|A n B| -|A n C| -|A n D| -|B n C|- |B n D| - |C n D|+|A n B n C|+|A n B n D|+|A n C n D| +|B n C n D|-|A n B n C n D|

    In general the number of terms is the sum of of binomials from 1 to n thus, it is, 2^n -1

    Actually the result is easy to prove.
    You need to Justify,
    |A u B|=|A| + |B| -|A n B|
    Then,
    |A u B u C|=|A u (B u C)|=|A|+|B u C|-|A n B n C|
    Get the idea, (just induction argument).

    From here you should realize how it gets its name, Inculsion-Exclusion.
    Oh! I see it now. Kinda silly of me not to have seen it before. (The Venn diagram comment was what I needed, thank you!)

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 03:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 02:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum