There are $e^{O(n)}$ subsets of $\{1,2, \ldots, n\}$ s.t. symmetric difference of any two of them has size $\geq n / 3$.

Question

Prove that there are $e^{O(n)}$ subsets of $\{1,2, \ldots, n\}$ such that the symmetric difference of any two of them has size at least $n / 3$.

I can see this conclusion may be related to Dilworth's TH, Sperner's TH, Erdős-Ko-Rado TH. Can someone help me?

Answer 1

For $n=3$ note that $\{1,2\},\{1,3\},\{2,3\}$ satisfies the requirement. Now assume $n$ is a multiple of $3$ and $k=\frac n3$. By breaking $n$ into $k$ sets of three, we can get $3^k=3^{n/3}$ subsets that satisfy the requirement. Then $3^{n/3}=e^{\frac n3 \log 3}\in e^{O(n)}$