1989 USAMO Problems/Problem 2

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 $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.

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 $m$ games with both slots filled and $n$ games with only one slot filled, so $2m+n=20$ . Since there are only 14 games, $m+n \leq 14 \Longrightarrow 2m+n \leq 14+m \Longleftrightarrow 20 \leq 14+m \Longrightarrow m \geq 6$ , so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.

Solution 3

Assume the contrary.

Consider the largest set of disjoint edges $E$ . By assumption it has less than $6$ edges, i.e. maximum $10$ vertices. Call it a vertex set $V$ .

$10$ vertices remain outside $V$ and each has to be attached to at least one edge. Now, if any two vertices outside $V$ are connected by, say, edge $e$ , we could have included $e$ in $E$ and gotten a larger disjoint set, so - a contradiction. Therefore the only option would be that all vertices outside $V$ are connected each by one edge to some vertices inside $V$ . That would take $10$ edges, but $E$ already includes $5$ - again a contradiction.

All possibilities yield a contradiction, so our assumption can not be correct.

(Cases when largest set $E$ is smaller than $6$ are equivalent and weaker)

Solution 4

Assume, for the sake of contradiction, that there is no set of 6 games with 12 distinct players. Then the largest possible collection of games with all distinct players must consist of at most 5 games, involving at most 10 players. So suppose we have 5 such games with 10 distinct players. This leaves 10 other players who must still appear in the schedule. Since there are a total of 14 games, there are $14-5=9$ games remaining to cover these 10 players.

Each game has 2 players, so the 9 games account for 18 ``player slots. If every one of the 10 unused players is to appear at least once, then by the pigeonhole principle, some game among these 9 must contain two of the 10 unused players. But then that game, together with the original 5 disjoint games, would give 6 games with 12 distinct players. This contradicts our assumption that no such collection exists. Therefore, there must in fact exist a set of 6 games with 12 distinct players. [/quote]

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

Page

Toolbox

Search