1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Basic Combinatorics Inclusion-Exclusion Principle Clarification

  1. Jun 14, 2010 #1
    1. The problem statement, all variables and given/known data

    How many integers between 1 and 2009, inclusive are (a) not divisible by 3,2, and 10 (b) not divisible by 3,2, or 10?

    2. Relevant equations

    The number of objects of the set S that have none of the properties is given by the alternating expression:

    [tex]
    \mid S \mid -\sum \mid A_{i} \mid + \sum \mid A_{i} \cap A_{j} \mid - ....
    [/tex]

    The number of objects of S which have at least one of the properties is given by

    [tex]
    \sum \mid A_{i} \mid - \sum \mid A_{i} \cap A_{j} \mid + ....
    [/tex]


    3. The attempt at a solution

    Well i=1,2,3 where i=1 is the property that its divisible by 3 and i=2 for the property that its divisible by 2 and i=3 for the property its divisible by 10

    [tex]
    \mid S \mid = 2009
    \mid A_{1} \mid = 669
    \mid A_{2} \mid = 1004
    \mid A_{3} \mid = 200
    \mid A_{1} \cap A_{2} \mid = 334
    \mid A_{1} \cap A_{3} \mid = 66
    \mid A_{2} \cap A_{3} \mid = 100
    \mid A_{1} \cap A_{2} \cap A_{3} \mid = 66
    [/tex]

    So for the part a I thought it would be the first equation because I am looking for the number of objects that don't have all these properties at the same time so my answer came to 570.

    For part b I thought it'd be the second equation which comes to 1439.

    But shouldn't the number of integers that are not divisible by 3,2, and 10 be larger than the number of integers that are not divisible by 3,2, or 10?
     
  2. jcsd
  3. Jun 14, 2010 #2
    Ok, so pretty much I just had my two answers backwards. 570 is the answer to (b) by the first equation because I found an example and I did it the exact same way. Which makes part (a) equal to 1439 by the second equation. Correct?
     
  4. Jun 14, 2010 #3
    (a) [tex]\sim{A_1} \cap \sim{A_2} \cap \sim{A_3}=\sim (A_1 \cup A_2 \cup A_3)=2009-1439=570[/tex]

    (b)[tex]\sim{A_1} \cup \sim{A_2} \cup \sim{A_3}=\sim (A_1 \cap A_2 \cap A_3)=2009-66=1943[/tex]
     
  5. Jun 14, 2010 #4
    Don't you have those backwards though.

    (a) not divisible by 3,2, and 10 which is just
    [tex]
    \sim (A_1 \cap A_2 \cap A_3)=2009-66=1943
    [/tex]

    so obviously the 2009 - 66 would make sense here and

    (b) not divisible by 3,2, or 10
    would be the other method.
     
  6. Jun 14, 2010 #5
    And what made you think that I did those backwards?

    Just follow what the task is asking for.

    Regards.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook