1995 USAMO Problems/Problem 5

Problem

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.

Solution

Consider the graph with two people joined if they are friends.

For each person $X$ , let $A(X)$ be the set of its friends and $B(X)$ the set of its foes. Note that any edge goes either: from $X$ to $A(X)$ (type 1), from $A(X)$ to $B(X)$ (type 2) or from a point of $B(X)$ to another (type 3), but there's no edge joining two points of $A(X)$ (since they would form a triangle with $X$ ). Let the number of type 1, type 2, type 3 edges of $X$ be $x_1, x_2, x_3$ respectively, so that $x_1$ is the degree of $X$ and we want to show that for some $X$ , we have $x_3 \leq q(1-4q/n^2)$ .

Since each edge is of one of those types, we have $x_1+x_2+x_3=q$ . Thus $x_3 \leq q(1-4q/n^2) \Longleftrightarrow \\ x_3 \leq q-4q^2/n^2 \Longleftrightarrow \\ q-x_1-x_2 \leq q-4q^2/n^2 \Longleftrightarrow \\ x_1+x_2 \geq 4q^2/n^2.$ That is, what we want is equivalent to proving that for some vertex $X$ , the set of edges touching either $X$ or a vertex joined to $X$ is at least $4q^2/n^2$ . Obviously now we'll sum $x_1+x_2$ over all vertices $X$ . In the resulting sum, an edge joining $X, Y$ is counted once for each edge that $X, Y$ have, that is, it is counted $D(X)+D(Y)$ times, where $D(X)=x_1$ is the degree of $X$ . Thus each vertex $X$ contributes to the overall sum with $D(X)$ for each edge it has, and since it has $D(X)$ edges, it contributes with $D(X)^2$ . Thus the considered sum is equal to $\sum_{X \in G} D(X)^2 \geq \frac{(\sum_{X \in G} D(X))^2}{n}=\frac{(2q)^2}{n}=4q^2/n.$ (That's Cauchy.) Since we are summing over $n$ vertices, one of the summands is at least $4q^2/n^2$ 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)
Preceded by Problem 4	Followed by Last Problem
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1995 USAMO Problems/Problem 5

Problem

Solution

See Also