Tournament championship proof

Question

Let's define a tournament as a contest among $n$ players where each player plays a game agains each other player and there are no draws. Now let me define a tournament champion.

A tournament champion is a player $c$ where, for each other player $p$ in the tournament, either

• $c$ won his/her game against $p$, or
• there’s a player $q$ where $c$ won his/her game against $q$ and $q$ won his/her game against $p$.

I need to prove the following:

Let T be an arbitrary tournament and p be any player in that tournament. Prove the following statement: if $p$ won more games than anyone else in $T$ or is tied for winning the greatest number of games, then $p$ is a tournament champion in $T$.

My proof is:

Let $c$ be any player in $T$ that won more games than anyone else or is tied for winning the greatest number of games. We want to show that $c$ is also a champion in $T$. In order to show this we proceed by contradiction. Assume that $c$ is not a champion. Then, there should exist a player $p$ which won $c$ and for any other player $q$ that won $p$ $c$ lost his/her game against $q$.

Assume that each player should play $N$ games and that there were $n$ such players $q$ that won $p$. It means that the maximum number of victories of $c$ is $cv = N - n - 1$, because he/she lost his/her games against all $q$s and against $p$. Notice that $n$ represents the number of losses of $p$, therefore the minimum number of victories of $p$ is $pv = N - n$. We see that $pv > cv$ and this means that $c$ didn't won the greatest number of games (and wasn't tied for winning the most games), but it contradicts our assumption that $c$ won the most games. Consequently, $c$ is a champion.

Could you please review my proof and say what's wrong with it and how it can be improved. I'm especially interested in variable introduction - do I do that right? And can I do something like this?

Assume that each player should play $N$ games and that there were $n$ such players $q$ that won $p$.

I'm not sure if I can manipulate a group of $n$ objects in the proof, because as I saw earlier other proofs do something like

Let $k$ be any number/player/whatever in $T$

Answer 1

Your proof is correct. In particular, the way in which you introduced $N$ and $n$ is fine. Your argument could be presented more clearly and efficiently, but that’s partly because you’re not writing in your first language. Here is a more polished version of the same argument.

Let $T$ be a tournament with $n$ players, so that each player plays $n-1$ games, and let $c$ be a player in $T$ who won at least as many games as any other player in $T$; we want to show that $c$ is a champion. If not, there is another player, $p$, who beat $c$ and also beat every player whom $c$ beat. Thus, if $c$ beat $m$ players, $p$ beat at least $m+1$ players, contradicting our hypothesis that no player won more games than $c$.

We don’t actually need to argue by contradiction here: essentially the same argument proves the contrapositive, i.e., that if $c$ is not the champion, then some player won more games than $c$. It’s even possible to give a direct proof that a player who won at least as many games as any other player is a champion:

Assume that no player won more games than $c$, let $p$ be any other player, and suppose that $p$ beat $c$. Let $n_c$ be the number of games won by $c$ and $n_p$ the number won by $p$. Let $A$ be the set of players other than $c$ and $p$. Then $p$ beat $c$ and $n_p-1$ members of $A$, and $c$ beat $n_c\ge n_p>n_p-1$ members of $A$, so there is at least one $a\in A$ such that $c$ beat $a$, and $p$ did not beat $a$. But that means that $a$ beat $p$. Thus, every player who beat $c$ was beaten by someone whom $c$ beat, and therefore $c$ is a champion.

Answer 2

May be the other proof is saying the following:

For any $q \in T$, that won over $p$. It must be the case that $q$ won over $c$, since $c$ is not a champion. Thus, all $q$'s that won over $p$, also won over $c$. Moreover, $p$ won over $c$. Thus, $c$ is not the one who won the maximum number of times. Hence, the contradiction.

Your proof is also correct. There is not much difference.