Learning mode > Inclusion-exclusion principle (Difficulty: Medium)

Question: In a city there are three clubs. The football club has 18 members, the allotment club 17 and the shooting club 13. 2 of the football players and 3 of the allotment club go shooting, 8 inhabitants play football and own a small garden, and 1 very dedicated person is involved in all three clubs. The allotment garden and the shooting club celebrate a common summer party. How many people come at most, if one calculates that each of the club members brings an accompaniment?

Help (How do I enter my solution?)

Question 1 / 5

Rule of sum applies to disjoint sets.

The inclusion-exclusion principle can be used as rule of sum for determining the summation of any N sets regardless of being disjoint or non-disjoint. Size of the union of N disjoint or non-disjoint sets can be determined by summing up sizes of each set, minus sizes of the N times pairwise intersections, plus sizes of the N-1 times intersections between every three sets, minus sizes of the N-2 times intersections of each four sets, and so on. In case of having only two sets, the size of the union of two sets is equal to the summation of size of each set, minus the sizes of the intersections because they are counted two times. For the case of three sets there are three pairwise intersections that we remove, this is why the size of the intersection of the three sets should be added again, as shown below. The same concept can be extended for any N disjoint or non-disjoint sets.

Two sets
|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∩ B| = |A| + |B| - |A ∪ B|

Three sets
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
|A ∩ B ∩ C| = |A ∪ B ∪ C| - |A| - |B| - |C| + |A ∩ B| + |A ∩ C| + |B ∩ C|

(The lower formula in each case results from reformulating the upper formula)