Intersecting Subsets

Solution

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

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|