Let $S$ be a set with $N$ elements and let $A_1,\dots ,A_{101}$ be $101$ (possibly non disjoint) subsets of $S$ with the following properties:
a) each element of $S$ belongs to at least one of these subsets
b) each subset contains exactly $1000$ elements of $S$
c) the intersection of any pair of subsets contains exactly $200$ elements
d) the intersection of any three subsets contains exactly $6$ elements
e) the intersection of any $4$ or more distinct subsets is empty
Prove this set cannot exist
My Proof
1) We know from inclusion-exclusion we can compute the cardinality by $101\times1000 - \binom{101}{2}\times200 + \binom{101}{3}\times6$
2) We know from property E that $A_1\cap A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6 = \emptyset$
3) By associative law we have $[A_1\cap A_2 \cap A_3] \cap [A_4 \cap A_5 \cap A_6] = \emptyset$
4) We can do this with any distinct intersection of 3 subsets. Therefore, all our intersections with 3 sets are disjoint from each other.
5) Since they are all disjoint, we can write the cardinality as the sum of all intersections of 3 distinct sets
6) The sum of all distinct intersections of 3 sets can be written as $\binom{101}{3}\times6$
7) However $\binom{101}{3}\times6$ does not equal our computation in step 1. So, the set is a contradiction. Valid ways of counting compute different cardinalities for it.
My Question
I want to know if the proof is sensible, readable and most importantly correct.
No comments:
Post a Comment