Mongolian Mathematical Olympiad

It suffices to prove that the number of dominant groups are odd. Let $S$ be the set of all the pupils in the class and $V$ be the set of all nonempty subsets of $S$. Thus, $|V| = 2^{|S|} - 1$. Now let us define a graph $G$ on $V$. We join $A \in V$ and $B \in V$ by edge iff there is no friends between $A$ and $B$ and $A \cap B = \emptyset$.

Now we consider degree of $H$ in $G$. If $H$ is dominant, there is no edge from $H$. And furthermore, all the vertices with degree $0$ is clearly dominant. Now we say $H$ is not dominant. Let $H_1$ be the set of all the pupils that has no friends in $H$. Then for any $H_2 \in V$, $H_2$ and $H$ are joined by edge iff $H_2 \subseteq H_1$ and $H_2 \neq \emptyset$. Since $\emptyset \notin V$, degree of $H$ in $G$ is $2^{|H_1|} - 1$. It is well known that the number of vertices with odd degree must be even number. Thus, number of non-dominant sets in $V$ are even. Since $|V|$ is odd, the number of dominant sets are odd.