Tennis League (USAMO 1989)

[Zawadx]

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.

[Thanic Nur Samin]

Hint:

Pigeonhole principle and edge deletion

[nahin munkar]

14 two-person games make $14*2=28$ place to participate. Now,under condition,if all participate in this game just one time,there will be 8 place to play more as there r $20$ players of this tournament . if the players play in those 8 position,there will be 8 games where any player plays more than once. so, If we delete those $8$ games, there r such $(14-8=6)$ games in where one player plays not more than once.So,there must be a set of 6 games with $(6*2)$ or $12$ distinct players within this shedule......(proved)

[Zawadx]

14 two-person games make $14*2=28$ place to participate. Now,under condition,if all participate in this game just one time,there will be 8 place to play more as there r $20$ players of this tournament . if the players play in those 8 position,there will be 8 games where any player plays more than once. so, If we delete those $8$ games, there r such $(14-8=6)$ games in where one player plays not more than once.So,there must be a set of 6 games with $(6*2)$ or $12$ distinct players within this shedule......(proved)

Well done.

I've also seen a very cool solution involving counting the edges/vertices (a great tactic if the problem can be rephrased as a graph):

We can represent this as a graph of $20$ vertices and $14$ edges. For the sake of contradiction, assume in any set of $6$ edges, there is at most $11$ vertices. Thus, the sum $S$ of the number of vertices over all sets of $6$ edges is
\[S \leq \binom{14}{6}\times 11.\]
Now each edge is represented $\binom{13}{5}$ times over all the sets of $6$ edges. Every edge has two vertices, and therefore $S=\binom{13}{5}\binom{14}{1}\cdot 2$. Thus,

$\begin{align*}
\binom{13}{5}\binom{14}{1}\times 2&\leq \binom{14}{6}\times 11 \\
\binom{14}{6}\times 2 \times 6&\leq \binom{14}{6}\times 11 \\
12&\leq11
\end{align*}$


A contradiction.