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
    9
    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
    9,838
    Thanks
    320
    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
    9
    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
    9,838
    Thanks
    320
    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, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum