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?
N3 = LCM(2,3,4) = 12.
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 . :)
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).