Question

1. A = {1,2,3,...,2016,2017,2018} S is a set whose elements are the subsets
of A such that one element of S cannot be a subset of another element. Let, S has
maximum possible number of elements. In this case, what is the number of
elements of S?

Answer 1

Answer on Question # 82739, Math / Combinatorics | Number Theory

Question 1.

$A=\{1,2,3,...,2016,2017,2018\}$, $S$ is a set whose elements are the subsets of $A$ such that one element of $S$ cannot be a subset of another element. Let, $S$ has maximum possible number of elements. In this case, what is the number of elements of $S$?

Solution. Consider the general case: $|A|=2n$. Say that two subsets of $A$ are incomparable if neither is a subset of the other, and say that a subset of $A$ is large if it has more than $n$ elements. Let $\mathcal{A}$ be any pairwise incomparable family of subsets of $A$. For any set $X$ let $X_{n}$ be the family of subsets of $X$ of cardinality $n$. Let

$\mathcal{B}=\{U\in\mathcal{A}\colon|U|\leqslant n\}\cup\bigcup\{U_{n}\colon U\in\mathcal{A},\,|U|>n\}.$

$\mathcal{B}$ is simply the result of replacing each large member of $\mathcal{A}$ by its $n$-element subsets. $\mathcal{B}$ is pairwise incomparable, and clearly $|\mathcal{B}|\geqslant|\mathcal{A}|.$ The strategy is easy: replace big sets with their $n$-element subsets, do an inverse, replace big sets again.

Now let $\mathcal{C}=\{A\setminus B\colon B\in\mathcal{B}\}$. $\mathcal{C}$ is pairwise incomparable, $|\mathcal{C}|=|\mathcal{B}|$, and $|C|\geqslant n$ for each $C\in\mathcal{C}$.

Repeat the process used to go from $\mathcal{A}$ to $\mathcal{B}$. Let

$\mathcal{D}=(\mathcal{C}\cap A_{n})\cup\bigcup\{C_{n}\colon C\in\mathcal{C}\setminus A_{n}\}.$

Then $|\mathcal{D}|\geqslant|\mathcal{C}|\geqslant|\mathcal{A}|$, and $\mathcal{D}\subset A_{n}$, so $|\mathcal{A}|\leqslant|A_{n}|={2n\choose n}$, so ${2n\choose n}$ is indeed an upper bound on the size of any family of pairwise incomparable subsets of $A$. Since $A_{n}$ is a pairwise incomparable family of cardinality ${2n\choose n}$, this upper bound is sharp.

Coming back to our case: $n=1009$, $S=A_{1009}$, $|S|={2018\choose 1009}$. $\Box$

Answer provided by https://www.AssignmentExpert.com