Maths Olympiad Prep

Library / /45 of 104

Combinatorics Difficulty 5.7 AIME, harder Prove it Bulgaria

Problem:

In a group of BB boys and GG girls it is known that G2B1G \geq 2 B-1. Some boys know some girls. Prove that it possible to arrange a dance in pairs in such a way that all boys will dance and every boy who does not know the girl in his pair knows only girls who do not dance.

Solution

Solution:

If for every s=1,2,,Bs=1,2, \ldots, B any ss boys know together at least ss girls then the Hall (marriages') theorem implies that every boy can dance with a known girl and the condition is satisfied.

Let us assume now the converse and choose the largest sBs \leq B, such that there are ss boys who know together at most s1s-1 girls.

Denote the set of these ss boys by SS and let LL be the set of girls known to the boys from SS. If some tt of the boys outside SS know together at most tt of the girls outside LL we have a contradiction with the choice of ss. Therefore every tt boys outside SS know together at least t+1t+1 of the girls outside LL.

Now the Hall theorem implies that every boy outside SS can dance with a known girl outside LL. Hence still non-dancing girls outside LL are at least
G(Bs)(s1)=G+1BB G-(B-s)-(s-1)=G+1-B \geq B
(the girls which dance with boys outside SS are BsB-s and the girls which are known to the boys from SS are at most s1s-1 ). If the boys from SS dance with some ss of these remaining non-dancing girls outside LL then the condition is satisfied.

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.