There is the tournament for boys and girls. Every person played exactly one match with every other person, there were no draws. It turned out that every person had lost at least one game. Furthermore every boy lost different number of matches that every other boy. Prove that there is a girl, who won a match with at least one boy.
Problem
Source: Polish Junior Math Olympiad 2nd Round 2020
Tags: combinatorics
wutf2
22.10.2020 23:36
It seems like those classic problems for lunch, i.e., despite being easy, is very fun. Suppose there are $n$ girls and $m$ boys, say $g_1, g_2, ..., g_n$ are the $n$ girls and $b_1, b_2, ..., b_m$ are the $m$ boys. Assume the statement is incorrect, in other words, every boy $b_i$ won their match against every girl $g_j,$ therefore, every boy's loss was against another boy, then the different amounts of losses vary from $0$ to $m-1,$ however it's said everyone lost at least once, implying no boy won against all the other boys, applying Pigeon Hole Principle follows there are $2$ boys with the same amount of losses, a contradiction. Hence, the statement is correct.
mathleticguyyy
23.10.2020 07:25
Suppose otherwise that every boi won every match against every gurl. Then, each boi will have lost at most $b-1$ matches, where $b$ is the total amount of bois. Though, since each boi has lost at least one match, there are $b-1$ possible amount of matches lost by any boi and $n$ bois with distinct amounts of matches lost, which is impossible.