1989 USAMO Problems/Problem 2
The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players
Consider a graph with vertices and edges. The sum of the degrees of the vertices is ; by the Pigeonhole Principle at least vertices have degrees of and at most vertices have degrees greater than . If we keep deleting edges of vertices with degree greater than (a maximum of such edges), then we are left with at least edges, and all of the vertices have degree either or . These edges represent the games with distinct players.
|1989 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|