1995 USAMO Problems/Problem 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 persons and 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 or fewer amicable pairs.
Consider the graph with two people joined if they are friends.
For each person , let be the set of its friends and the set of its foes. Note that any edge goes either: from to (type 1), from to (type 2) or from a point of to another (type 3), but there's no edge joining two points of (since they would form a triangle with ). Let the number of type 1, type 2, type 3 edges of be respectively, so that is the degree of and we want to show that for some , we have .
Since each edge is of one of those types, we have . Thus That is, what we want is equivalent to proving that for some vertex , the set of edges touching either or a vertex joined to is at least . Obviously now we'll sum over all vertices . In the resulting sum, an edge joining is counted once for each edge that have, that is, it is counted times, where is the degree of . Thus each vertex contributes to the overall sum with for each edge it has, and since it has edges, it contributes with . Thus the considered sum is equal to (That's Cauchy.) Since we are summing over vertices, one of the summands is at least by pigeonhole, which is what we wanted to prove.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|1995 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|