VC- dimension calculate

Question

Let X = {1, 2, 3, ... , 100}. Let H be the class of all subsets of X that contain at least 20 and at most 80 elements. What is the VC-dimension of H?

Answer 1

The VC dimension is 80.

The set $C=\{1,\dotsc,80\}$ is shattered by $H$:
Let $A\subseteq C$. Note that $|A|\leq|C|=80$. If $|A|\geq20$, then $A\in H$ is already a witness. If $|A|<20$, then $h=A\cup\{81,\dotsc,100\}$ has size between 20 and 39, hence is in $H$, and $h\cap C=A$.

No set of size $\geq81$ is shattered by $H$:
Let $C$ be such a set, and consider $\emptyset\subseteq C$. For any $h\in H$, since $|h|\geq20$, we have $|h\cap C|=|h|+|C|-|h\cup C|\geq 20+81-100>0$, so $h\cap C\neq\emptyset$.