In a group of kids there are $2022$ boys and $2023$ girls. Every girl is a friend with exactly $2021$ boys. Friendship is a symmetric relation: if A is a friend of B, then B is also a friend of A. Prove that it is not possible that all boys have the same number of girl friends. Proposed by the JMMO Problem Selection Committee
Problem
Source: 2023 Junior Macedonian Mathematical Olympiad P1
Tags: graph theory, combinatorics
10.06.2023 13:14
There are $2021 \cdot 2023$ pairs of friends in total, which is an odd number. But there are $2022$ boys, which is even, hence $2022 \nmid 2021 \cdot 2023$, and then all boys can't have the same number of girl friends.
10.06.2023 13:18
We count the number of pairs of friends of opposite sexes. There are $2023 \cdot 2021$ of those, as each girl has $2021$ boys friends. On the other hand, if all boys had the same number of girlf friends, let it be $x$, then we would have $2022x$ such pairs, and so $2023 \cdot 2021=2022x,$ a contradiction.
30.12.2024 13:54
10 sec solve 2023.2021=2022x
05.01.2025 13:50
We count the number of pairs (boy, girl) which are friends. Note that this is obviously $2021 \times 2023$. But if all boys had an equal number of friends, this number would be $\frac{2021 \times 2023}{2022}$ which isn't an integer, contradiction. $\square$