gagantheroyal's blog

Finding number of integers divisible by 2, 3 or 4 using inclusion-exclusion principle.
By gagantheroyal, history, 9 years ago, In English

I want to find number of integers from 1 to 19 (both included) which are divisible by 2 or 3 or 4. Lets denote it by N. So counting and enumerating them gives N = 12. Integers are 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16 and 18.

I thought of applying inclusion-exclusion principle for finding N. Here is how I proceeded:

Lets denote the followings:

N1 = (Number of integers which are divisible by 2) + (Number of integers which are divisible by 3) + (Number of integers which are divisible by 4)

N2 = (Number of integers which are divisible by 2*3 = 6) + (Number of integers which are divisible by 3*4 = 12) + (Number of integers which are divisible by 2*4 = 8)

N3 = (Number of integers which are divisible by 2*3*4 = 24)

Then using inclusion-exclusion principle we have: N = N1 — N2 + N3

Finding N1, N2 and N3 (denoting Greatest Integer Function using floor function):

N1 = floor(19 / 2) + floor(19 / 3) + floor(19 / 4) = 9 + 6 + 4 = 19

N2 = floor(19 / 6) + floor(19 / 12) + floor(19 / 8) = 3 + 1 + 2 = 6

N3 = floor(19 / 24) = 0

Therefore, N = N1 — N2 + N3 = 19 — 6 + 0 = 13.

From here, I am getting N = 13 which is wrong as I counted them manually above (N = 12).

Can anyone point out the mistake I am making here and suggest the correct way of doing this using inclusion-exclusion principle?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

N3 = LCM(2,3,4) = 12.

→ Reply
»
9 years ago, # |
← Rev. 7   Vote: I like it +6 Vote: I do not like it

If you look at the Venn diagram then area common to A and B represents numbers which are divisible by both 2 and 4 which means numbers divisible by LCM of 2 and 4 same holds for other common areas.

So N1 will remain same as you said.

N2 = (Number of integers which are divisible by 2 and 3 i.e. LCM( 2, 3 ) which is 6) +

(Number of integers which are divisible by 3 and 4 i.e. LCM( 3, 4 ) which is 12) +

(Number of integers which are divisible by 2 and 4 i.e. LCM( 2, 4 ) which is 4)

N3 = (Number of integers which are divisible by 2, 3 and 4 i.e. LCM( 2, 3, 4 ) which is 12)

This will change values of N2 and N3 which will be 8 and 1. So our answer will be 19 — 8 + 1 = 12.

PS — Thanks for this question. Because of this question i could easily solve This problem . :)

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The mistake is in calculation of N1,N2,N3: You have to take the no. of integers divisible by the LCM of divisor(e.g. LCM(2,3,4) not (2*3*4) ) instead of multiplying it for calculating N1,N2,N3 because for above set of integers(1..19) ,the divisor (2,3,4) should be prime number(i.e. prime divisor).

→ Reply