Sets: guaranteed minima and counting formulas

How many people must have every required characteristic? The data do not always determine the exact number: often they determine a guaranteed minimum. We start with a puzzle, derive a formula for any number of sets and distinguish this question from exact counting.

Lab: counting with sets · Visual Venn lab

1. The 100 doctors puzzle

A hospital employs 100 doctors: 75 speak English, 80 Spanish, 85 French and 90 German. What is the guaranteed minimum number who speak all four languages? The same doctors can belong to several groups.

The answer is not “exactly 30”: it is “at least 30, and 30 is possible”.

Calculate and explain

2. Count missing memberships instead

Fix a universe U of N elements and k subsets A₁,…,Aₖ. Write aᵢ=|Aᵢ| for group i’s size. S=a₁+⋯+aₖ counts memberships, not distinct people, and may exceed N. Anyone in every group has no missing membership.

Group i is missing N−aᵢ elements. Total missing memberships are M=(N−a₁)+⋯+(N−aₖ)=kN−S. One person may be missing from several groups, so the number with at least one missing membership is at most M, and cannot exceed N. The complement of the intersection is the union of the complements: U∖(A₁∩⋯∩Aₖ)=(U∖A₁)∪⋯∪(U∖Aₖ).

x ≥ N−min(N,M) = max(0,N−M) = max(0,S−(k−1)N)

3. General formula and counting proof

Let x=|A₁∩⋯∩Aₖ| be the common count. These x people contribute kx memberships. Each of the other N−x people belongs to at most k−1 groups. Hence:

S ≤ kx+(k−1)(N−x)
S ≤ kx+(k−1)N−(k−1)x
S ≤ x+(k−1)N
x ≥ S−(k−1)N.

Since x≥0, the desired formula follows when only N and group sizes are known, with 0≤aᵢ≤N:

x minimum = max(0, a₁+⋯+aₖ−(k−1)N)

For two groups subtract N; for three, 2N; for four, 3N. For the doctors: max(0,75+80+85+90−3×100)=max(0,330−300)=30. Taking the maximum with zero prevents a negative answer. “Minimum zero” means that no common person is guaranteed, not that the intersection must be empty.

4. Why the bound can be attained

An inequality alone does not prove attainability. If M≤N, assign the N−aᵢ missing memberships of each group to completely different people. Exactly M people have one missing membership, leaving N−M with none: the formula’s minimum.

If M≥N, imagine the N people in a circle. Assign the first group’s missing memberships to consecutive people; continue with the second group from where you stopped, then with the others, wrapping around when needed. Every block has at most N people, so nobody is missing twice from the same group. At least N consecutive assignments cover everyone: nobody belongs to all groups. The formula correctly gives zero.

This construction preserves each initial group size. It assumes no additional constraints: prescribed intersections would require separate checks. The lab constructs and checks a configuration even when M≥N.

Calculate and explain

5. The maximum: certain versus possible

The intersection cannot contain more elements than the smallest group. Nesting the sets from smallest to largest attains the maximum.

x maximum = min(a₁,…,aₖ)

For the doctors the maximum is 75. Put all 75 English speakers inside the 80 Spanish speakers, these inside the 85 French speakers, and these inside the 90 German speakers; 10 doctors lie outside every group. The totals are the same as in the minimum-30 construction, but now 75 speak all languages. Thus the four totals cannot determine an exact count between 30 and 75.

If minimum and maximum coincide, the count is determined. An empty group forces zero common members; if every group equals U, the count is N. A negative size or aᵢ>N is not a difficult case: it is impossible input.

Calculate and explain

6. Another class: exact counts with two sets

For N elements we know a=|A|, b=|B| and i=|A∩B|. The sum a+b counts common members twice, so subtract one copy. Unlike the guaranteed-minimum problem, the intersection is known.

|A∪B| = a+b−i
only A = a−i; only B = b−i
exactly one = a+b−2i
none = N−a−b+i

Among 30 students, 18 do sport, 16 music and 7 both. How many do at least one activity, exactly one, or neither?

The data are feasible if and only if max(0,a+b−N)≤i≤min(a,b). Equivalently, all four region counts must be nonnegative.

Calculate and explain

7. Inverse problems: find the overlap

If z elements belong to neither set, the union has N−z members. Starting from N−z=a+b−i, isolate i rather than inventing a new rule:

i = a+b−N+z

Of 40 people, 25 read magazine A, 22 magazine B and 5 neither. How many read both?

Always check 0≤i≤min(a,b). For example, N=20, a=8, b=7, z=0 gives i=−5: impossible data, since the groups cannot cover all 20 people. Do not replace −5 with zero; report the inconsistency.

Calculate and explain

8. Three sets: union, exactly one, exactly two

Write a=|A|, b=|B|, c=|C|, p=|A∩B|, q=|A∩C|, r=|B∩C| and t=|A∩B∩C|. Pairwise intersections include t: p does not mean “A and B but not C”. Set S₁=a+b+c and S₂=p+q+r.

|A∪B∪C| = S₁−S₂+t
none = N−S₁+S₂−t
exactly one = S₁−2S₂+3t
exactly two = S₂−3t
at least two = S₂−2t

In the first formula a member of all three is counted 3−3+1=1 time. “Only A”, “only B” and “only C” have counts a−p−q+t, b−p−r+t and c−q−r+t. “Only AB”, “only AC” and “only BC” have counts p−t, q−t and r−t. All of these, the triple intersection and the outside region must be nonnegative.

Example: N=100, a=60, b=50, c=40, p=30, q=25, r=20, t=15.

Calculate and explain

9. Percentages and checks: use the same base

The formulas also work for proportions on the same universe. For percentages p₁,…,pₖ, the minimum common percentage is max(0,p₁+⋯+pₖ−100(k−1))%. The doctors’ 75%, 80%, 85%, 90% guarantee at least 30%. Convert an exact percentage to a count with N×p/100, checking whole-number compatibility. Rounded percentages are not exact inputs.

Do not combine 70% of all school students with 60% of only the sporty students: their denominators differ. First put them on the same universe. The lab takes whole-number counts, not percentages: convert them before entering data.

10. Which formula should you choose?

• Only group sizes, asking “at least how many in all”? Use the guaranteed minimum.
• Two sets with known sizes and overlap? Use inclusion–exclusion for exact counts.
• The outside count is known? Find the union first, then the overlap.
• Three sets with all required intersections? Start at the triple overlap and reconstruct eight regions.

Always identify the universe; translate “all”, “at least one”, “exactly one”; check inputs; apply the formula; verify using disjoint regions. Do not mistake a guarantee for an exact count, or use max(0,…) to conceal inconsistent exact-count data.

Ten exercises: try before revealing the solution

1. Of 50 people, 35 are in A and 40 in B. Common minimum and maximum?

2. Three groups have 20, 18, 17 members out of 30 people: how many must be in all?

3. Five skills: 95, 94, 93, 92, 91 people out of 100. Common minimum?

4. For the 100 doctors, does a distribution with 75 speaking all four contradict the minimum 30?

5. N=25, |A|=16, |B|=14, |A∩B|=8. Find union, exactly one, neither.

6. N=60, |A|=35, |B|=30; 10 are in neither. Find the overlap.

7. N=20, |A|=15, |B|=12, overlap=3. Possible data?

8. N=100; a=60, b=50, c=40; p=30, q=25, r=20, t=15. How many belong to at least two groups?

9. 90% and 85% of the same population have two attributes. Minimum percentage with both?

10. N=10 and group sizes 10, 10, 7. Is more information needed to know the common count?

Review elements and operations · Ten advanced set problems · Lab: counting with sets

Further reading

MIT · Mathematics for Computer Science, Cardinality Rules