Q6 Matemática  (Baltic Way 2000)

Fredek administra um hotel particular. Ele afirma que sempre que $n\ge 3$ hóspedes visitam o hotel, é possível selecionar dois hóspedes que tenham igual número de conhecidos entre os demais hóspedes, e que também tenham um conhecido em comum ou um desconhecido comum entre os hóspedes. Para quais valores de $n$ Fredek está certo? (Conhecimento é uma relação simétrica.)