Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Assume we've a tournament with $93$ teams. And between every $19$ teams, there is one team that has lost all of its $18$ games to other teams, and there is one team that has won all of its $18$ games against the other teams. Between all teams, there is one match and only possible results for a match is win and lose.
My own idea is to try to give a proof by contradiction, by assuming two teams share same number of games won.
Definition top/bottom element: In a set $S$ a team is the top element if it has won against everyone else. It is the bottom if it has lost against everyone else.
Definition: Let's say that a set of teams is $k$ absolute if every subset of size $k$ of these teams has both a top and a bottom element.
To prove: You want to show your teams form a total order in terms of the win/lose relation. Here is a general proof that a total order exists for any $n$ teams which are $k$ absolute whenever $n \geq 2k > 4$. In your case, $n, k$ are $93, 19$ respectively, fitting the above inequality.
Proof: Suppose you have $n \geq 2k$ nodes. We can prove they form a total order as follows. Pull off the top node to get a $k$ absolute set of $n-1$ elements. Then pull off the top node again to get a $k$ absolute set of $n-2$ elements. Repeat until you're left with $k$ elements. You are allowed to do this until you get to $k$ by the "top" part of the top-bottom lemma. This gives you that there are teams with $k+1, k+2, \dots, n$ wins. Now, do the same for the least elements, again using the top-bottom lemma- this time the "bottom" part. You end up showing there are teams with $1, 2, \dots, k$ wins; you can stop at $k$ even if $n > 2k$ becausee you've already shown the wins from $k+1$ onwards. Together, then these results show that we have some team with $1$ win, another with $2$ etc. all the way up to $n$. This implies uniqueness by the pigeonhole principle because we have $n$ pigeons (teams) and $n$ holes (number of wins) and there exists a team for each number of wins.
Lemma (Top/Bottom): We show that every $k$ absolute set $U$ of $n$ teams with $n \geq k > 2$ elements has a top and a bottom element. We prove this as follows. Let $S$ be the largest subset of $U$ that has a top element. We know by $k$ absoluteness of $U$ that $|S| \geq k$. Now, suppose $S \neq U$, towards a contradiction. Let $t$ be the top element of $S$. Then we can choose some $u \in U$ s.t. $u > t$. Now, we can show that $u$ is the top element in $S \cup \{u\}$. To show this, consider any subset of $S$ of size $|S| - 1$ that also contains $t$. Call it $S'$. Because $k > 2$, every element in $S$ belongs to some such $S'$; a crucial point made by commenter Steve Kass is that this is not the case for $k = 2$. Now, by $k$ absoluteness, there must be a top element of $S' \cup \{u\}$. Well, because $t$ is greater than all elements existing other than $u$, none of them can be the top. Nor can $t$ be the top since $u>t$. So $u$ is the top element. So, $u$ is greater than all elements of $S'$. Since we've already mentioned that every element of $S$ is in some $S'$, because $k>2$, we know then that $u > s$ for every $s \in S$. Thus the set $S \cup \{u\}$ of size strictly greater than $S$, has a top element $u$, contradicting our assumption that $S$ was the top. Thus, $U$ must have a top element. The exact same argument can be applied for a bottom element.
