Intersecting Subsets

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

Solution


|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 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.


[an error occurred while processing this directive]

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

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]