MathDB

Suppose that in a certain society, each pair of persons can be classified as either amicable or hostile. We shall say that each member of an amicable pair is a friend of the other, and each member of a hostile pair is a foe of the other. Suppose that the society has

\, n \,

persons and

\, q \,

amicable pairs, and that for every set of three persons, at least one pair is hostile. Prove that there is at least one member of the society whose foes include

\, q(1 - 4q/n^2) \,

or fewer amicable pairs.

Problem Statement