4
$\begingroup$

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.

$\endgroup$
13
  • 1
    $\begingroup$ I'm going to see how far I get using the Pigeonhole principle... $\endgroup$ Jan 14 '18 at 20:06
  • 1
    $\begingroup$ The pigeonhole principle would be great for proving that two teams did have to have the same number of wins. But it's not immediately clear how it can be bent the other direction, to show that a set of things must all be different. $\endgroup$ Jan 14 '18 at 20:13
  • 1
    $\begingroup$ @StevenStadnicki you're right I'm realising the same thing. $\endgroup$ Jan 14 '18 at 20:14
  • 2
    $\begingroup$ I have a feeling that you need to show the teams form a totally ordered set... $\endgroup$ Jan 14 '18 at 20:30
  • 1
    $\begingroup$ I have no idea either. I'm just annoyingly thinking aloud. But the question is equivalent to asking you to prove that the teams form a total order in terms of their wins. Uniquness implies that the wins go $92, 91, \dots, 0$, which in turn implies total order... $\endgroup$ Jan 14 '18 at 20:35
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I'm pretty sure there's a better way to explain this and that it's a known proof in lattice theory or something that I saw years ago, but hopefully you get the rough idea. $\endgroup$ Jan 14 '18 at 21:54
  • $\begingroup$ I think this is pretty close to a proof (and is the same as what I came up with while thinking on this in the shower), but there are a couple of tiny things: (1) your 'clearly' could use some fleshing out ($t$ can't be the top element of the subset because $u\gt t$, and nothing else can be because $t$ is still greater than everything else in the subset), and (2) this procedure doesn't quite work as written: consider an 'order' $0\lt 1\lt 2\lt\ldots39\lt 40\lt 0$. Then the procedure you've written will never find a top element. $\endgroup$ Jan 14 '18 at 22:32
  • $\begingroup$ (Assuming that you start with the set $\{0\ldots18\}$ $\endgroup$ Jan 14 '18 at 22:34
  • 1
    $\begingroup$ Maybe I’m missing something, but consider a set of $n=3$ teams, each of which has played the other two teams with a $1$-$1$ record. (A beat B, B beat C, and C beat A; the tournament graph is a $3$-cycle.) This (or any) tournament is $2$-absolute, because within any subset of two teams, there is a top and bottom element (the winner and loser of the single match between those two teams. So the graph of any $n$-team tournament is $2$-absolute, and with $k=2$, $n>2k>2$ for any $n>4$. Then your work concludes than any $n$-tournament is transitive so long as $n>4$. I don’t think this is correct. $\endgroup$
    – Steve Kass
    Jan 14 '18 at 22:35
  • $\begingroup$ @SteveKass dammit! I meand $k>2$ aka $2k > 4$ thank you for the correction! I also went through the case of $2$ absoluteness and realised it was special. $\endgroup$ Jan 15 '18 at 7:32

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.