Applications of Inclusion and Exclusion Principle

In this class, We discuss the Applications of Inclusion and Exclusion Principle.

The reader should have prior knowledge of inclusion and exclusion formulae. Click Here.

Example 1:

Determine the numbers not exceeding 100 and not divisible by 2, 3, 5, and 7.

Solution:

P1 = numbers divisible by 2

P2 = numbers divisible by 3

P3 = numbers divisible by 5

P4 = numbers divisible by 7

We need to identify the numbers not divisible by any of the numbers 2, 3, 5, and 7.

Numbers divisible by any one of the 2, 3, 5, and 7 are given as |P1 ∪ P2 ∪ P3 ∪ P4|

Not divisible by any = N – |P1 ∪ P2 ∪ P3 ∪ P4|

N is the total number from 2 to 100. So N = 99

|P1| = 100/2 = 50

|P2| = 100/3 = 33

|P3| = 100/5 = 20

|P4| = 100/7 = 14

|P1 ∩ P2| = 100/(2*3) = 16

|P1 ∩ P3| = 100/(2*5) = 10

|P1 ∩ P4| = 100/(2*7) = 7

|P2 ∩ P3| = 100/(3*5) = 6

|P2 ∩ P4| = 100/(3*7) = 4

|P3 ∩ P4| = 100/(5*7) = 2

|P1 ∩ P2 ∩ P3| = 100/(2*3*5) = 3

|P1 ∩ P3 ∩ P4| = 100/(2*5*7) = 1

|P2 ∩ P3 ∩ P4| = 100/(3*5*7) = 0

|P1 ∩ P2 ∩ P3 ∩ P4| = 100/(2*3*5*7) = 0

|P1 ∪ P2 ∪ P3 ∪ P4| = |P1| + |P2| + |P3| + |P4| – |P1 ∩ P2| – |P1 ∩ P3| – |P1 ∩ P4| – |P2 ∩ P3| – |P2 ∩ P4| – |P3 ∩ P4| + |P1 ∩ P2 ∩ P3| + |P1 ∩ P3 ∩ P4| + |P2 ∩ P3 ∩ P4| – |P1 ∩ P2 ∩ P3 ∩ P4|

On substituting the values and finding |P1 ∪ P2 ∪ P3 ∪ P4|

Finally N – |P1 ∪ P2 ∪ P3 ∪ P4| = 21

Total 21 numbers that are not divisible by 2, 3, 5, and 7.

x (A + B) y =