A group of the pupils in a class are called dominant if any other pupil from the class has a friend in the group. If it is known that there exists at least dominant group, then there exists one more dominant group.
Solution
It suffices to prove that the number of dominant groups are odd. Let be the set of all the pupils in the class and be the set of all nonempty subsets of . Thus, . Now let us define a graph on . We join and by edge iff there is no friends between and and .
Now we consider degree of in . If is dominant, there is no edge from . And furthermore, all the vertices with degree is clearly dominant. Now we say is not dominant. Let be the set of all the pupils that has no friends in . Then for any , and are joined by edge iff and . Since , degree of in is . It is well known that the number of vertices with odd degree must be even number. Thus, number of non-dominant sets in are even. Since is odd, the number of dominant sets are odd.