Maths Olympiad Prep

Library / /49 of 108

Combinatorics Difficulty 6.0 AIME, harder Prove it Mongolia

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 100100 dominant group, then there exists one more dominant group.

Solution

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

Now we consider degree of HH in GG. If HH is dominant, there is no edge from HH. And furthermore, all the vertices with degree 00 is clearly dominant. Now we say HH is not dominant. Let H1H_1 be the set of all the pupils that has no friends in HH. Then for any H2VH_2 \in V, H2H_2 and HH are joined by edge iff H2H1H_2 \subseteq H_1 and H2H_2 \neq \emptyset. Since V\emptyset \notin V, degree of HH in GG is 2H112^{|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 VV are even. Since V|V| is odd, the number of dominant sets are odd.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.