Set
S has
1600 members.
Sb is a collection of
16000 subsets of
S, each having
80 members.
Prove (or disprove) that there must be at least two members of Sb containing 3 or less members in common.
If the statement was
"Prove (or disprove) that there must be at least two members of Sb having 3 or more members in common."
it would be (a little) more difficult:
An 80-elements subset contains C(80,3) triples, so 16000 such subsets contain 16000*C(80,3) = 1314560000 triples. Since there are only C(1600,3)=681387200 different triples in total, some must show up in more than one subset.
|
|
Posted by JLo
on 2020-01-24 09:18:59 |
Alternative problem?
