## Intersecting Subsets

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

Solution

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.

### Related materialRead more...

• Sum of Integers
• More than half of the integers from {1, 2, ..., 2n}
• Consequences of Getting More Than a Half
• Remainder Multiples of 1997
• Over-The-Counter Pigeonhole
• Women in a theatre: Pigeonhole Principle
• Pigeonhole Among Friends
• Not Exceeding 24