## Intersecting Subsets

Given any 10 4-element subsets of an 11-set, some two of the subsets intersect in at least two elements.

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny
Given any 10 4-element subsets of an 11-set, some two of the subsets intersect in at least two elements.

Count the ordered pairs (A,B), where A is a given 4-element
subset and B is one of A's 2-element subsets, in two ways. There are
10 choices for A and, for each choice, there are 6 2-element subsets B
of A. Hence there are 10*6=60 such ordered pairs. There are 55
2-element subsets of the 11-set. Let a_{i}, for i=1,...,55 be the number
of given 4-element subsets which contain the i-th 2-element subset.
Then the number, 60, of ordered pairs (A,B) is the sum of the 55 a_{i}'s.
Hence the average value of the a_{i} is 60/55>1, and so some a_{i}≥2. This
means some 2-element subset is contained in two of the given 4-element
subsets.

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny