Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving a inclusion-exclusion problem

  1. Nov 18, 2014 #1
    Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. One of my friend told me that he can determine the number of ways with inclusion-exclusion principle and found the result 195 for given N=10 and the positive integers are 12,46,100,131,5,6,7,8,9.

    I can not still catch how he used inclusion-exclusion principle to find out the number of ways.Hence I need an expert's help.
    If the value of N varies how can I find out the number of ways using inclusion-exclusion principle? I'm a novice in learning inclusion-exclusion principle.So I need better explanation
     
  2. jcsd
  3. Nov 18, 2014 #2
    Given that the number of distinct ##4##-sets that can be constructed from the given set is ##{10\choose4}=210## and that the number of ##4##-sets that include both 6 and 8 (and therefore would not have the desired property) is ##{8\choose 2}=28##, I'd say that your friend's solution is incorrect.

    So I think you should demand a more in-depth explanation from your friend.
     
  4. Nov 24, 2014 #3
    I think the meaning is that, choosing 4 numbers {a,b,c,d}, we then examine whether gcd(a,b,c,d) = 1. Choosing 6 and 8 does not shut down that possibility.

    Clearly we do need at least one odd number, and while 7 and 131 are co-prime to all the other possible choices, 5 and 9 are not.

    More difficult is finding the 10th number when only 9 are specified.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving a inclusion-exclusion problem
  1. Problem Solving (Replies: 0)

Loading...