5
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Commented Aug 17, 2020 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
    Commented Aug 17, 2020 at 11:41

2 Answers 2

2
$\begingroup$

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

$\endgroup$
10
  • $\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$ Commented Aug 17, 2020 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
    Commented Aug 17, 2020 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
    Commented Aug 17, 2020 at 14:53
  • 1
    $\begingroup$ @Maran I think I came up with one graph-theoretic one. Should I add another answer? $\endgroup$
    – cgss
    Commented Aug 17, 2020 at 16:03
  • 1
    $\begingroup$ @Maran I edited the answer. $\endgroup$
    – cgss
    Commented Aug 17, 2020 at 17:17
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .