Let S be a set with N elements and let A1,…,A101 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×1000−(1012)×200+(1013)×6
2) We know from property E that A1∩A2∩A3∩A4∩A5∩A6=∅
3) By associative law we have [A1∩A2∩A3]∩[A4∩A5∩A6]=∅
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 (1013)×6
7) However (1013)×6 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