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
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 g1,g2,...,gn are the n girls and b1,b2,...,bm are the m boys. Assume the statement is incorrect, in other words, every boy bi won their match against every girl gj, 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.
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.