The Polish Acquaintanceship Problem

A Polish problem longlisted for the 19th International Mathematical Olympiad in Yugoslavia, July 1977:

A room contains nine men. Among every three of them there are two who are mutually acquainted. Prove that four of them are mutually acquainted.

	Select Click for Answer
If one of the men is unacquainted with four of the others, then those four know one another and we’re done. If not, then this means that each man is mutually acquainted with at least five of the others. It can’t be exactly five in every case, because the total number of acquaintances in the room must be an even number. Hence someone is acquainted with at least six men. Among those six, three know one another, and they together with the man himself make four.