1985 USAMO Problems/Problem 4

Problem

There are people at a party. Prove that there are two people such that, of the remaining people, there are at least of them, each of whom knows both or else knows neither of the two. Assume that "know" is a symmetrical relation; denotes the greatest integer less than or equal to .

Solution

Consider the number of pairs (X, {Y, Z}), where X, Y, Z are distinct points such that X is joined to just one of Y, Z. If X is joined to just k points, then there are just k(n - 1 - k) ≤ (n - 1)2/4 such pairs (X, {Y, Z}). Hence in total there are at most such pairs. But there are possible pairs {Y, Z}. So we must be able to find one of them {A, B} which belongs to at most such pairs.

Hence there are at least points X which are joined to both of A and B or to neither of A and B. (If confused by the floor, consider n = 2m and n = 2m+1 separately!)

~John Scholes

See Also

1985 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.