1989 USAMO Problems/Problem 2

Revision as of 21:35, 10 January 2008 by Azjps (talk | contribs) (fix)

Problem

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

Solution

Consider a graph with $20$ vertices and $14$ edges. The sum of the degrees of the vertices is $28$; by the Pigeonhole Principle at least $12$ vertices have degrees of $1$ and at most $8$ vertices have degrees greater than $1$. If we keep deleting edges of vertices with degree greater than $1$ (a maximum of $8$ such edges), then we are left with at least $6$ edges, and all of the vertices have degree either $0$ or $1$. These $6$ edges represent the $6$ games with $12$ distinct players.

See also

1989 USAMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5
All USAMO Problems and Solutions
Invalid username
Login to AoPS