USAMO $1989$, Problem $2$

Question

Problem $2$ from USAMO, $1989$: 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 six games with $12$ distinct players.

My attempt at a solution: Since there are $20$ players, each of whom has played at least one game, the least number of matches which must be organised to accommodate all players would be $10$. Now, $4$ more matches are left, which can be played by at most $8$ of these $20$ players. Thus, at least $12$ of the players get to play no more than $1$ match, and hence there must exist a set of six games with $12$ distinct players. This, I believe, will be the guiding principle of a rigorous proof.

I have the following doubts clouding my mind:

1. Is my reasoning sound, i.e., free of any pitfalls?
2. If correct, how to frame the above reasoning in a mathematically rigorous proof?

Edit: As pointed out by Ben in the comments, the statement in italics is unjustified. I overlooked a lot of possibilities while framing this proof, it seems. Thus, I would like to get some hints to proceed with more reasonable proof.

Answer 1

I am afraid there is a pitfall. If you try to prove that there are 6 games with 12 distinct players amongst those who have played exactly 1 game you will fail. Here's an example:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

While there are 6 games with 12 distinct players, only 5 games are between the players with exactly one game.

So here's a hint: split the players in two groups, those with one game and those with more. Then pair players with one game,after pair players with one game with players with more and finally players with more games.

EDIT: Second approach

If every person is seen as a vertex and every game as an edge, the question asks to prove that there is a matching of size at least $6$. Equivalently, we can prove that the size of the maximum matching $MM$ is of size at least $6$. Note that a maximum matching partitions the vertices into two sets, one with edges in the $MM$, of size $2\cdot |MM|$, and one without, of size $20 - 2\cdot |MM|$ for our problem. Since all vertices are of degree at least $1$, we conclude that there are at least $20 - 2\cdot |MM|$ edges between the two partitions. Now,

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$

Answer 2

Not my argument, but I like it:

$14$ two-person games make $14\cdot 2=28$ places to participate. Now, under condition, if all participate in this game just one time, there will be $8$ places to play more as there are $20$ players of this tournament. If the players play in those $8$ positions, there will be $8$ games where any player plays more than once. So, if we delete those $8$ games, there are 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\cdot 2=12$ distinct players within this shedule.

Source