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.

  • $\begingroup$ I think that going from "at least 12 of the players get to play only 1 match" to "there exists a set of six games with 12 distinct players" is unjustified. $\endgroup$ – Ben Grossmann Aug 17 '20 at 11:40
  • $\begingroup$ @BenGrossmann Any hints on how I could fill this gap? It seems intuitively true, but again proofs in plain English are mostly shaky. $\endgroup$ – Manan Aug 17 '20 at 11:41

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

  • $\begingroup$ What do you mean by "pair players with one game"? It sounds like you're trying to construct an arrangement of games that fits the description, whereas the goal is to prove that every arrangement of 14 games among 20 players with each player in at least one game will have these 6 games $\endgroup$ – Ben Grossmann Aug 17 '20 at 14:07
  • $\begingroup$ @BenGrossmann Let's take a random player $A$ with exactly one game. If that game was another player $B$ with exactly one game then the pair(or match if you prefer) $A - B$ will be one of the 6 we are looking for. $\endgroup$ – cgss Aug 17 '20 at 14:22
  • 1
    $\begingroup$ Yes, that is correct. Perhaps some pidgeonhole arguments can improve the exhausting search but in general lines that is the idea. I guess there will be other approaches as well. I am considering a graph-theoretic approach. If you have another approach feel free to share. $\endgroup$ – cgss Aug 17 '20 at 14:53
  • 1
    $\begingroup$ @Maran I think I came up with one graph-theoretic one. Should I add another answer? $\endgroup$ – cgss Aug 17 '20 at 16:03
  • 1
    $\begingroup$ @Maran I edited the answer. $\endgroup$ – cgss Aug 17 '20 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.