Problem

Source: 5th Memorial Mathematical Competition "Aleksandar Blazhevski - Cane" - Senior - Problem 1

Tags: graph theory, combinatorics



This year, some contestants at the Memorial Contest ABC are friends with each other (friendship is always mutual). For each contestant $X$, let $t(X)$ be the total score that this contestant achieved in previous years before this contest. It is known that the following statements are true: $1)$ For any two friends $X'$ and $X''$, we have $t(X') \neq t(X''),$ $2)$ For every contestant $X$, the set $\{ t(Y) : Y \text{ is a friend of } X \}$ consists of consecutive integers. The organizers want to distribute the contestants into contest halls in such a way that no two friends are in the same hall. What is the minimal number of halls they need?