1985 USAMO Problems/Problem 4

Problem

There are $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\lfloor n/2\rfloor -1$ of them, each of whom knows both or else knows neither of the two. Assume that "know" is a symmetrical relation; $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$ .

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 $\frac{n(n - 1)^2}{4}$ such pairs. But there are $\frac{n(n - 1)}{2}$ possible pairs {Y, Z}. So we must be able to find one of them {A, B} which belongs to at most $\lfloor \frac{n-1}{2} \rfloor$ such pairs.

Hence there are at least $n - 2 - \lfloor \frac{n - 1}{2} \rfloor = \lfloor \frac{n}{2} \rfloor - 1$ 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

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

Page

Toolbox

Search

1985 USAMO Problems/Problem 4

Problem

Solution

See Also