Intersecting Subsets
|
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 ai, 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 ai's.
Hence the average value of the ai is 60/55>1, and so some ai 2. This
means some 2-element subset is contained in two of the given 4-element
subsets.
Copyright © 1996-2009 Alexander Bogomolny
|
