Let be a natural number, and let be a family consisting of at most distinct subsets of the set with the property that one can consider distinct points in the plane, labeled with the numbers , then draw segments between some of these points such that, for any distinct numbers , the points labeled and are connected by a segment if and only if the number belongs to exactly subsets in . Find the maximum possible value of the sum of the number of elements of the sets in .
Solution
For , denote by .
Then , and the sum whose maximum we want to estimate is
The connection condition implies that if , then , for any . Conversely, any function satisfying this condition corresponds to a family verifying the hypothesis.
Therefore, the numbers form pairs of two distinct numbers; otherwise, if , then is connected both to and to , which would imply .
We deduce that
Finally, observe that the maximum is attained for any family for which for all ; for example, the family formed by .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.