At any given point in time two players have finished the same number of games

Question

I am reading the following problem, which falls under the Pigeonhole principle.

A chess tournament has $n$ participants and any two players play one game against each other. Then it is true that at any given point in time, there are two players who have finished the same number of games.

My approach:
I assume the opposite, i.e., that we never have players with the same number of matches at any time.
This means that at any point in time all players have completed different number of matches. This implies that there will be only $1$ player that has finished $1$ match but that is impossible since it takes $2$ person to finish a match. Hence the opposite must be true i.e. that we have always at least two players with the same number of matches.

At this point I think my proof is wrong. Because I am not sure if my approach actually makes the point be proven for any point in time. Additionally I don't think I am applying the pigeonhole principle.

What do you think of my proof and how can it be improved?

Answer 1

At a given point, it is possible that each participant had played more than one match. So your solution as stated is not generic.

Writing my comment as an answer, a generic approach based on Pigeonhole principle will be to assume that at a given point, m participants have played matches $(2 \le m \le n)$. The minimum number of matches a participant could have played is $1$ and the maximum number of matches a participant could have played is $(m−1)$. That is $(m-1)$ distinct number of matches played by $m$ different participants. So, at least two participants must have played equal number of matches.

Answer 2

You can prove something more general: for any tournament structure for $n \ge 2$ players in which games are played, provided that no pair of players is allow to play twice, then at any time instant there are always at least two players who have completed the same number of games.

We can prove this by modeling it as a graph theory problem. Pick a time instant and form a graph with $n$ nodes, one for each player, and add edges between pairs of players who have already played their game. A classic application of the pigeonhole principle is to show that any graph with $n \ge 2$ nodes has two nodes of the same degree (a quick Google search will turn up many proofs of this result). The degree of a node in this graph corresponds to the number of games a player completed, so this shows that you’ll always find two players who have completed the same number of games.

This doesn’t even require everyone to play everyone else - it also works for single-elimination matches, for example.

Answer 3

Your approach, to assume the opposite, in order to prove that that yields a contradiction, is good.

MathLover's answer has the right idea but fails to account for the possibility that a player hasn't played any games yet.

Call the total number of players $m$. The number of games a player has played so far is one of the $m$ integers in the range 0 to $m-1$. If none of them have played the same number of games, then, for each of those integers $k$, there is exactly one player who has played $k$ games. This means that one player $P$ has not played anybody. It also means that another player has played $m-1$ games, and has therefore played every other player, including $P$, even though $P$ hasn't played anybody else. This is a contradiction.