Private hotel and its guests
Source: Baltic Way 2000 Problem 6
February 13, 2009
combinatorics unsolvedcombinatorics
Problem Statement
Fredek runs a private hotel. He claims that whenever guests visit the hotel, it is possible to select two guests that have equally many acquaintances among the other guests, and that also have a common acquaintance or a common unknown among the guests. For which values of is Fredek right? (Acquaintance is a symmetric relation.)