1989 USAMO Problems/Problem 2

From AoPSWiki

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

Solution 1

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.

Solution 2

Let a slot be a place we can put a member in a game, so there are two slots per game, and 28 slots total. We begin by filling exactly 20 slots each with a distinct member since each member must play at least one game. Let there be games with both slots filled and games with only one slot filled, so . Since there are only 14 games, , so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.

See also