First Round of the 73rd Czech and Slovak Mathematical Olympiad (take-home part)

a) For $k=5$, it may happen that there are no such couples, with one counterexample given as follows. Split the boys into two disjoint quintuples $A,B$ and the girls into two disjoint quintuples $C,D$. Consider the configuration where every boy from $A$ likes all the girls in $C$, every boy in $B$ likes all the girls in $D$, every girl in $C$ likes all the boys in $B$ and every girl in $D$ likes all the boys in $A$. Then every boy likes 5 girls, every girl likes 5 boys, but there is clearly no couple where both partners like each other.

b) For $k=6$, such a couple must exist: there are in total $10k=60$ couples (boy, girl) where the boy likes the girl and, by symmetry, 60 couples where the girl likes the boy. These two sets of couples can't possibly be disjoint, since there are $10\cdot 10=100$ couples in total and $60+60>100$, so there must be a couple where both the partners like each other.