/sci/ - Science & Math

[http://math.harvard.edu/putnam(...) !!84u21X0KjW+ No.10702142]

Suppose that in a certain society, each pair of persons can be classified as either [math] amicable [/math] or [math] hostile [/math]. We shall say that each member of an amicable pair is a [math] friend [/math] of the other, and each member of a hostile pair is a [math] foe [/math] of the other. Suppose that the society has [math] \, n \, [/math] persons and [math] \, q \, [/math] 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 [math] \, q(1 - 4q/n^2) \, [/math] or fewer amicable pairs.