The first challenges use Venn regions; later ones explore families of subsets, function images and infinite sets. Solutions are initially hidden. |A| denotes cardinality, A∖B set difference, AΔB=(A∖B)∪(B∖A) symmetric difference, and 𝒫(A) the collection of all subsets of A. C(n,k) counts k-element choices. Pairwise intersections include the triple intersection. Diagram areas are schematic, not proportional to cardinalities.
- Reconstructing eight overlapping regions
- Which triple intersections are possible?
- Symmetric distances do not tell the whole story
- An iterated symmetric difference
- An unknown set with multiple constraints
- Power sets do not distribute over union
- Four sets and an impossible archive
- When does an image preserve intersection?
- A large intersecting family with no common element
- Infinitely often does not mean eventually always
1. Reconstructing eight overlapping regions
In a universe of 120 elements, |A|=70, |B|=65, |C|=60, |A∩B|=40, |A∩C|=35 and |B∩C|=30. Ten elements lie outside all three. Find all eight regions and the numbers in exactly one and exactly two sets.
Hint
Start with the union and triple intersection.
Solution with diagram
1. The union has 110 elements. Inclusion–exclusion subtracts pairwise intersections and adds back the triple intersection t:
|A∪B∪C|=120−10=110 110=70+65+60−40−35−30+t t=20 AB: 40−20=20; AC: 35−20=15; BC: 30−20=10
2. The pair-only regions are 20,15,10. Only A is 70−40−35+20=15; only B and only C are also 15.
Check. Exactly one: 45; exactly two: 45; all three: 20; outside: 10. Their total is 120. Do not subtract the central region twice.
2. Which triple intersections are possible?
|U|=100, |A|=60, |B|=55, |C|=50. Pairwise intersections AB, AC, BC have sizes 35,30,25. Determine all possible integer values t=|A∩B∩C| and prove that every permitted value can occur.
Hint
Every atomic region, including the exterior, must have nonnegative size.
Solution with diagram
1. Only A has size 60−35−30+t=t−5, as do only B and only C. Each pair-only region has its stated pairwise size minus t.
|A∪B∪C|=165−90+t=75+t A only = B only = C only = t−5 AB only=35−t; AC only=30−t; BC only=25−t U ∖ (A∪B∪C): 25−t 5 ≤ t ≤ 25, t ∈ ℤ
2. Single-only regions require t≥5; BC-only and the exterior require t≤25. Other upper bounds are weaker.
3. For every integer 5 through 25, the eight quantities shown are nonnegative and sum to 100. Take disjoint groups of those sizes and define A,B,C by joining the indicated groups. This realizes every value, proving that 5,…,25 is the exact range.
3. Symmetric distances do not tell the whole story
In a universe of size 60, |AΔB|=24, |AΔC|=30, |BΔC|=26, |A∩B∩C|=8 and |A|+|B|+|C|=92. Find the counts in exactly one, two, three or none of the sets. Are individual atomic regions determined?
Hint
Every element belonging to one or two sets contributes twice to the three symmetric differences.
Solution with diagram
1. Let n₁,n₂,n₃ count elements in exactly one, two, three sets. Exterior and triple elements contribute zero to all symmetric differences. Every other element contributes twice:
2(n₁+n₂)=24+30+26=80 n₃=8 n₁+2n₂+3·8=92 n₂=28; n₁=12 |A∪B∪C|=12+28+8=48
2. Exactly one: 12; exactly two: 28; triple: 8; exterior: 12.
3. Atomic regions are not unique. Besides the diagram, another valid assignment is: A-only 5, B-only 1, C-only 6; AB-only 10, AC-only 9, BC-only 9; triple 8, exterior 12. Both match all given data. Aggregate information is not a complete configuration.
4. An iterated symmetric difference
For arbitrary A,B,C simplify E=((A∪B)∖C) Δ ((A∖B)∪(C∖A)), using no symmetric difference and at most one union, one triple intersection and one difference. Prove it on every region.
Hint
Track the three membership bits for a single element.
Solution with diagram
1. In region order 000,100,010,001,110,101,011,111, the first operand has values 0,1,1,0,1,0,0,0; the second 0,1,0,1,0,1,1,0.
2. Exclusive-or gives 0,0,1,1,1,1,1,0: all of B∪C except the triple intersection.
E=((A∪B)∖C) Δ ((A∖B)∪(C∖A)) E=(B∪C)∖(A∩B∩C)
3. The eight possibilities are exhaustive, so the identity holds for arbitrary sets, including infinite ones. Empty regions cause no problem.
5. An unknown set with multiple constraints
Let U={1,…,12}, A={1,…,7}, B={1,…,10}, C={2,4,6,8,10,12}, D={2,6,8,10}. Find every X⊆U with X∪A=B, X∩C=D and |X|=7. How many exist?
Hint
Separate forced, forbidden and optional elements.
Solution with diagram
1. The union constraint forces 8,9,10 and forbids 11,12. Elements in A remain optional initially.
2. The intersection constraint forces 2,6, confirms 8,10 and forbids 4,12. Optional elements are 1,3,5,7; five elements are already forced.
B∖A={8,9,10}
D∩A={2,6}
A∖C={1,3,5,7}
X={2,6,8,9,10}∪Y
Y⊆{1,3,5,7}, |Y|=2
C(4,2)=63. Choose two optional elements: 6 solutions. The possible Y are {1,3}, {1,5}, {1,7}, {3,5}, {3,7}, {5,7}. Add each to the forced group. This describes all and only valid X.
6. Power sets do not distribute over union
Finite A,B satisfy |A∩B|=2, |𝒫(A)|=2|𝒫(B)| and |𝒫(A)∪𝒫(B)|=44. Find |A|,|B| and the number of subsets of A∪B contained wholly in neither A nor B. Prove exactly when 𝒫(A∪B)=𝒫(A)∪𝒫(B).
Hint
Power sets preserve intersection, not always union.
Solution with diagram
1. Write a=|A|,b=|B|. A set with a elements has 2ᵃ subsets. Since 𝒫(A)∩𝒫(B)=𝒫(A∩B), that intersection has four members. Apply inclusion–exclusion:
a=|A|, b=|B| 2ᵃ=2·2ᵇ 2ᵃ+2ᵇ−2²=44 3·2ᵇ=48 ⇒ b=4, a=5 |A∪B|=5+4−2=7 2⁷−44=84
2. The sizes are 5 and 4. Of 128 subsets of the union, 44 lie wholly in at least one set; 84 do not.
3. Equality holds if A⊆B or B⊆A. Otherwise choose a∈A∖B,b∈B∖A. Then {a,b} is a subset of the union but of neither set. This proves necessity as well as providing a counterexample.
7. Four sets and an impossible archive
An archive claims 40 elements. Four categories A,B,C,D each contain 20; every one of the six pairwise intersections has size 8, each of the four triple intersections size 3, and the quadruple intersection size 1. Is this possible? Find the smallest universe realizing the data.
Hint
Use sixteen atomic regions, not four ordinary circles.
Solution with diagram
1. Four-set inclusion–exclusion gives a union of 43, so 40 is impossible.
2. To show 43 suffices, reconstruct exclusive regions: quadruple 1; each triple-only 3−1=2; each pair-only 8−3−3+1=3; each single-only 20−24+9−1=4.
|A∪B∪C∪D|=4·20−6·8+4·3−1=43 n₄=1 n₃=4(3−1)=8 n₂=6(8−3−3+1)=18 n₁=4(20−3·8+3·3−1)=16
3. Four groups of 4, six of 3, four of 2 and one of 1 total 43 and realize all intersections. The exterior may be empty. This proves attainability, not merely a lower bound.
8. When does an image preserve intersection?
Let U={1,…,8}, V={p,q,r,s}, with fibres f⁻¹({p})={1,2,3}, f⁻¹({q})={4,5}, f⁻¹({r})={6}, f⁻¹({s})={7,8}. Fix A={1,4,6,7}. How many B⊆U satisfy f(A∩B)=f(A)∩f(B)? Explain why equality is not automatic.
Hint
Treat each fibre separately.
Solution with diagram
1. A meets every fibre, so f(A)=V. In each fibre, B must be empty or include an element of A. Otherwise its image occurs on the right but not on the left.
2. For a fibre of size m with a elements in A, there is one empty choice. Nonempty allowed choices select a nonempty subset of those a elements and any subset of the other m−a.
N(m,a)=1+(2ᵃ−1)2ᵐ⁻ᵃ N(3,1)=5; N(2,1)=3; N(1,1)=2 5·3·2·3=90
3. Multiplying the independent combinatorial choices gives 90. Counterexample: B={2} gives right-hand side {p} but A∩B=∅. The inclusion from left to right always holds; equality need not.
9. A large intersecting family with no common element
For U={1,2,3,4,5,6}, find the largest family ℱ of distinct subsets such that every two distinct members intersect, but the intersection of the entire family is empty. Prove the bound and construct an example attaining it.
Hint
Pair each subset with its complement; construct using large sets and selected triples.
Solution with diagram
1. The 64 subsets form 32 complementary pairs. At most one member of each pair can be chosen, since the two are disjoint. Thus |ℱ|≤32.
2. Take all subsets of size at least four and all three-element subsets containing 1:
|𝒫(U)|=2⁶=64
|ℱ|≤64/2=32
ℱ={S⊆U: |S|≥4} ∪ {S⊆U: |S|=3, 1∈S}
|ℱ|=C(6,4)+C(6,5)+C(6,6)+C(5,2)
=15+6+1+10=323. Two large sets intersect. A large set and a triple have total size at least seven in a six-element universe, so also intersect. Selected triples share 1.
4. Every element is omitted by some four-element subset, which belongs to the family. The global intersection is empty. The maximum is therefore 32, without a universal common element.
10. Infinitely often does not mean eventually always
For n≥1 define Aₙ=[0,2−1/n]∪{3} when n is even, and Aₙ=[−1+1/n,1]∪{4} when n is odd. Find points belonging for all sufficiently large n (lim inf) and for infinitely many n (lim sup). Address −1,0,1,2,3,4 explicitly.
Hint
Separate even and odd indices; limiting endpoints need not be included.
Solution with diagram
1. Every point in [0,1] belongs to every set. Points in (−1,0) belong eventually along odd indices but never along even ones; points in (1,2) behave oppositely.
2. −1 and 2 never appear. 3 appears only at even indices, 4 only at odd ones. Every other point outside (−1,2)∪{3,4} is always absent.
lim inf Aₙ = ⋃ₘ₌₁∞ ⋂ₙ≥ₘ Aₙ = [0,1]
lim sup Aₙ = ⋂ₘ₌₁∞ ⋃ₙ≥ₘ Aₙ = (−1,2)∪{3,4}3. The lower limit is [0,1], the upper (−1,2)∪{3,4}. The quantifiers differ: “after some threshold, always” versus “beyond every threshold, at least once”. There is no single membership limit because the two sets differ.
