Browse · MathNet
PrintFinal Round of the 73rd Czech and Slovak Mathematical Olympiad (March 17–20, 2024)
Czech Republic 2024 counting and probability
Problem
Ten boys and ten girls met at a party. Suppose that every boy likes a different (positive) number of girls and that every girl likes a different (positive) number of boys. Find the largest non-negative integer such that it is always possible to form disjoint couples of a boy and a girl that like each other. (Josef Tkadlec)
Solution
We shall prove that the answer is .
To begin with, note that the problem statement implies that the boys like girls in some order, so there exists a boy that likes all the girls. Analogously, there must exist a girl that likes all the boys, so putting the two together always yields an admissible couple.
In the second part of the solution, we shall construct a configuration where it's impossible to form more than one such couple. Number the boys and the girls by numbers and suppose that the boy likes the girl if and only if , while the girl likes a boy number if and only if or (see the diagram below for the case , with boys on top and girls on bottom). With such an assignment, the -th boy likes girls and the -th girl likes boys. Also, it
is clear that the first boy is the only one that can be paired up with a girl that he likes so that she also likes him back, hence it is impossible to form two disjoint admissible couples and we are done.
To begin with, note that the problem statement implies that the boys like girls in some order, so there exists a boy that likes all the girls. Analogously, there must exist a girl that likes all the boys, so putting the two together always yields an admissible couple.
In the second part of the solution, we shall construct a configuration where it's impossible to form more than one such couple. Number the boys and the girls by numbers and suppose that the boy likes the girl if and only if , while the girl likes a boy number if and only if or (see the diagram below for the case , with boys on top and girls on bottom). With such an assignment, the -th boy likes girls and the -th girl likes boys. Also, it
is clear that the first boy is the only one that can be paired up with a girl that he likes so that she also likes him back, hence it is impossible to form two disjoint admissible couples and we are done.
Final answer
1
Techniques
Matchings, Marriage Lemma, Tutte's theoremColoring schemes, extremal arguments