Difference between revisions of "1985 USAMO Problems/Problem 4"
(Created page with "== Problem == There are <math>n</math> people at a party. Prove that there are two people such that, of the remaining <math>n-2</math> people, there are at least <math>\lfloor...") |
|||
| Line 3: | Line 3: | ||
== Solution == | == 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 n(n - 1)2/4 such pairs. But there are n(n - 1)/2 possible {Y, Z}. So we must be able to find one of them {A, B} which belongs to at most <math>\lfloor \frac{n-1}{2} \rfloor</math> such pairs. |
| + | |||
| + | Hence there are at least <math>n - 2 - \lfloor \frac{n - 1}{2} \rfloor = \lfloor \frac{n}{2} \rfloor - 1 </math> 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 == | == See Also == | ||
Revision as of 01:53, 2 July 2024
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 n(n - 1)2/4 such pairs. But there are n(n - 1)/2 possible {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. 
