Party of 8 where each knows exactly 3 others
Source: Baltic Way 2009
November 27, 2010
combinatorics proposedcombinatorics
Problem Statement
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.