Problem

Source: MOP 2005 Homework - Black Group #12

Tags: graph theory, combinatorics unsolved, combinatorics



A group consists of $n$ tourists. Among every three of them there are at least two that are not familiar. For any partition of the group into two busses, there are at least two familiar tourists in one bus. Prove that there is a tourist who is familiar with at most two fifth of all the tourists.