Problem

Source: Argentina TST 2009

Tags: combinatorics unsolved, combinatorics



There are several contestants at a math olympiad. We say that two contestants $ A$ and $ B$ are indirect friends if there are contestants $ C_1, C_2, ..., C_n$ such that $ A$ and $ C_1$ are friends, $ C_1$ and $ C_2$ are friends, $ C_2$ and $ C_3$ are friends, ..., $ C_n$ and $ B$ are friends. In particular, if $ A$ and $ B$ are friends themselves, they are indirect friends as well. Some of the contestants were friends before the olympiad. During the olympiad, some contestants make new friends, so that after the olympiad every contestant has at least one friend among the other contestants. We say that a contestant is special if, after the olympiad, he has exactly twice as indirect friends as he had before the olympiad. Prove that the number of special contestants is less or equal than $ \frac{2}{3}$ of the total number of contestants.