IMO Team Selection Contest

Partition 2019 inhabitants into 673 groups, each containing 3 inhabitants. Suppose that each inhabitant appoints two other members of the same group. As no group member is appointed thrice, the company cannot send three cards to one group member. Hence in every group, two different members get a card and at most one member will become sad. The inhabitant who does not belong to any group will become sad, too. Altogether, at most 674 inhabitants will become sad.

We show now that this is the least possible number. More precisely, we show that, in the case of $n$ inhabitants, the company can make $\lfloor \frac{n}{3} \rfloor$ inhabitants sad. Call inhabitants $X$ and $Y$ competitors if somebody appoints them together to the company. By conditions of the problem, there are as many pairs of competitors as inhabitants or less (if several inhabitants appoint the same pair or some inhabitant appoints no pair). Thus it suffices to

* If every inhabitant has exactly 2 competitors then choose an arbitrary inhabitant $X$ and leave out $X$ along with both competitors. Among the remaining $n-3$ inhabitants, there are at most $n-3$ pairs of competitors (besides two pairs containing $X$, removing either competitor canceled one more pair). By the induction hypothesis, one can find $\lceil \frac{n-3}{3} \rceil$ remaining inhabitants with no pair of competitors. Adding $X$ to them results in $\lceil \frac{n}{3} \rceil$ inhabitants with no pair of competitors.

* If an inhabitant $X$ has at most 1 competitor then there must exist an inhabitant $Y$ with at least 3 competitors. Let $Z$ be the competitor of $X$ if $X$ has a competitor and an arbitrary inhabitant different from $X$ and $Y$ otherwise. After leaving out $X$, $Y$ and $Z$, we have $n-3$ inhabitants and at most $n-3$ pairs of competitors (removing $Y$ cancels at least 3 pairs of competitors). By the induction hypothesis, one can find $\lceil \frac{n-3}{3} \rceil$ remaining inhabitants with no pair of competitors. Adding $X$ to this set results in a group of $\lceil \frac{n}{3} \rceil$ inhabitants with no pairs of competitors. This proves the desired claim.