IMO 1977 LL POL32

Origin: POL

Problem

In a room there are nine men. Among every three of them there are two mutually acquainted. Prove that some four of them are mutually acquainted.

Solution

It is a known result that among six persons there are 3 mutually ac- quainted or 3 mutually unacquainted. By the condition of the problem the last case is excluded. If there is a man in the room who is not acquainted with four of the oth- ers, then these four men are mutually acquainted. Otherwise, each man is acquainted with at least five others, and since the sum of numbers of acquaintances of all men in the room is even, one of the men is ac- quainted with at least six men. Among these six there are three mutually acquainted, and they together with the first one make a group of four mutually acquainted men.