LX OM - I - Task 5

For each integer $ n \geqslant 1 $, determine the largest possible number of different subsets of the set $ \{1,2,3, \cdots,n\} $ with the following property: Any two of these subsets are either disjoint or one is contained in the other.
Answer: $ 2n $ subsets.
Let the number of sought subsets be denoted by $ a_n $.
It is not difficult to observe that for $ n =1,2,3,\cdots $ the following $ 2n $
subsets of the set $ \{1,2,3, \cdots,n\} $ have the property described in the problem statement:






Indeed, any of the first $ n+1 $ sets has at most one element, so it is contained in any set with which it is not disjoint. On the other hand, for any two of the remaining
$ n - 1 $ sets, the set that is listed earlier in the above sequence is contained in the other set.
In this way, we have proved that






On the other hand, let $ B_1, B_2, \cdots, B_t $ be different
subsets of the set $ \{1, 2, \cdots,m\} $ with the property described in the problem statement. If among the listed subsets the set
$ \{1,2, \cdots,m\} $ does not appear, we can add it, increasing the number of these
subsets by $ 1 $ without violating the validity of the postulated condition.
Let us assume, then, that $ B_t = \{1,2, \cdots,m\} $.
Among the sets $ B_1, B_2, \cdots, B_{t-1} $, let us choose the one that has the most elements. For the sake of argument, let it be $ B_1 $
and let $ d $ denote the number of its elements. Then $ d < n $.
Moreover, the equality $ d = 0 $ means that $ B_1 $ is the empty set, which, given the choice of the set $ B_1 $, is possible only if
$ t = 2 $. In the further part of the reasoning, we assume, then, that $ 0 < d < n $.
By the definition of the set $ B_1 $, each of the sets
$ B_i $ ($ i=1,2,\cdots,t - 1) $ is either a subset of the set $ B_1 $,
or is disjoint from it. By renumbering, we can assume that the sets $ B_1, B_2, \cdots, B_r $ are subsets of the set
$ B_1 $, while the sets $ B_{r+1}, B_{r+2}, \cdots, B_{t-1} $ are
disjoint from $ B_1 $.
The sets $ B_1, B_2, \cdots, B_r $ are different subsets of
the $ d $-element set $ B_1 $, any two of which are either
disjoint or one is contained in the other. It follows that
$ r \leqslant a_d $. Among the $ t-r-1 $ sets
$ B_{r+1}, B_{r+2}, \cdots, B_{t-1} $, any two are either disjoint,
or one is contained in the other, and they are subsets of the
$ (m-d) $-element set $ {1, 2, \cdots,m}\setminus B_1 $,
and moreover, the empty set does not appear among them, as it
is a subset of $ B_1 $. Hence we obtain
$ t-r -1 \leqslant a_{m-d} -1 $ and consequently






As a result, the number of subsets of the set $ \{1,2, \cdots,m\} $
with the desired property does not exceed the number $ a_d +a_{m-d} $.
We have thus shown that $ a_m $ does not exceed the maximum of the numbers






If, then, in the inequality (1) equality holds for
$ n =1, 2, \cdots,m - 1 $, then it also holds for $ n = m $.
Since for $ n = 1 $ the inequality (1) becomes an equality, using
induction, we finally conclude that $ a_n =2n $ for $ n =1,2,3, \cdots $.