1995 USAMO 第 5 题

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.

假设在某个社会中，每一对人都可以分为友好的或敌对的。我们可以说，友好配对中的每个成员都是对方的朋友，而敌对配对中的每个成员都是对方的敌人。假设社会有 $\, n \,$ 人和 $\, q \,$ 友好对，并且对于每三人一组，至少有一对是敌对的。证明社会中至少有一名成员的敌人包括 $\, q(1 - 4q/n^2) \,$ 或更少的友好对。