Browse · MathNet
Print58th Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
students arrived to the summer camp. Every child (boy or girl) in the camp knows exactly one boy and one girl. Is it possible if
a) ;
b) .
a) ;
b) .
Solution
a) Suppose boys and girls arrived to the camp. We can split them into groups with students in each: boys and girls. Moreover, they know each other in the following way: . One can check that all conditions are satisfied.
b) Suppose by contradiction that it is possible. Then every boy can be put into a pair with a girl if they know each other. Thus, there has to be exactly boys and girls. Similarly, all the boys can be divided in pairs if they know each other, so the amount of boys has to be even. That leads to a contradiction.
b) Suppose by contradiction that it is possible. Then every boy can be put into a pair with a girl if they know each other. Thus, there has to be exactly boys and girls. Similarly, all the boys can be divided in pairs if they know each other, so the amount of boys has to be even. That leads to a contradiction.
Final answer
a) Yes. b) No.
Techniques
Matchings, Marriage Lemma, Tutte's theorem