Combinatorics question about downsets Prove that if
$\mathcal{A}$
is a downset then the average size
of sets in
$\mathcal{A}$
is at most
$\frac{n}{2}$
($\mathcal{A} ⊂ \mathcal{P}(n)$ is a
downset
if, for every
$A∈\mathcal{A}$
, every subset
of
$A$
belongs to
$\mathcal{A}$)
Have tried using induction but got stuck at the inductive step.  Any help greatly appreciated!
 A: This might be using a cannon to kill a fly, but...
It can be proved that it is possible to partition $\mathcal{P}(n)$ into symmetric chains. Here, and chain $A_1,A_2,\dots, A_k$ is a sequence of sets such that $A_1 \subsetneq A_2 \subsetneq \dots$, and it is symmetric if $\# A_i + \# A_{k+1-i} = n $ for any $i$. The claim is not extremely difficult, and you can do it by induction on $n$. [For a proof of this, see e.g. these notes, p.78, Thm 8.3]
Knowing this, the solution is easy. Consider any chain $A_1,A_2,\dots, A_k$.  Because $\mathcal{A}$ is assumed to be a downset, whenever $A_l \in \mathcal{A}$ then also $A_i \in \mathcal{A}$ for $i < l$. Hence, there is some $l$ such that the sets from the chain which belong to $\mathcal{A}$ are precisely $A_1,A_2,\dots, A_l$. Pairing $A_i$ with $A_{l+1-i}$ we see that on average, $A_i \in \mathcal{A} $ have at most $n/2$ elements. Averaging this over all chains in the partition (and using the fact that the chains are disjoint), we conclude that the average size of $A \in \mathcal{A} $ is at most $n/2$.
