Problem

Source: Baltic Way 2009

Tags: combinatorics proposed, combinatorics



In a party of eight people, each pair of people either know each other or do not know each other. Each person knows exactly three of the others. Determine whether the following two conditions can be satisfied simultaneously: – for any three people, at least two do not know each other; – for any four people there are at least two who know each other.