In a football tournament there are $8$ teams, each of which plays exacly one match against every other team. If a team $A$ defeats team $B$, then $A$ is awarded $3$ points and $B$ gets $0$ points. If they end up in a tie, they receive $1$ point each. It turned out that in this tournament, whenever a match ended up in a tie, the two teams involved did not finish with the same final score. Find the maximum number of ties that could have happened in such a tournament.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
NoYoo-hooForMe
04.05.2010 18:16
uglysolutions wrote: In a football tournament...
We will refer to the $8$ teams as $A$, $B$, $C$, $D$, $E$, $F$, $G$, and $H$, and when we say that a team finishes with a $m$-$n$ record, we mean they won $m$ games, lost $n$ games, and tied the rest of their games. We will also call a game a "decisive game" if it resulted in a clear winner/loser--ie not a tie game.
Let's assume that the problem conditions can be met with just $5$ decisive games. In this case we first show that no one team can be involved in more than $2$ decisive games. Assume, to the contrary, that $A$ is involved in $3$ decisive games. Thus, $A$ has the same outcome with $2$ of its decisive opponents--say $B$ and $C$--with a possibly different decisive outcome with another team, $D$. Therefore at least one of $B$ and $C$ must be involved in one more decisive game. If that game involves those two teams, that leaves only one decisive game for the remaining $4$ teams--and hence at least two teams must finish with a record of all ties. On the other hand, if $B$ or $C$ plays its decisive game with a different team, that leaves $3$ teams with no decisions yet accounted for. If $2$ of those teams play a decisive game with each other, there will necessarily be teams with the same record who do not play each other to a decision--and if not there will be two or more teams who tie all their games.
In any event, the assumption that $A$ is involved in $3$ decisive games leads to a contradiction, so we can assume that no team is involved in more than $2$ decisive games.
This leaves only $6$ possible records: $2$-$0$, $1$-$1$, $0$-$2$, $1$-$0$, $0$-$1$, and $0$-$0$. Furthermore the problem condition that two teams with the same record must play each other to a decision means that one cannot have more than $3$ teams with a $1$-$1$ record, and no more than $1$ team with any other possible record. This uniquely establishes the records of all $8$ teams and in a way that involves $6$ decisive games--so it is not possible to satisfy the problem conditions with just $5$ decisive games.
On the other hand this shows clearly how the problem conditions can be met with $6$ decisive games: $A$ beats $B$, $B$ beats $C$, $C$ beats $A$, $D$ beats $F$, $D$ beats $G$, $E$ beats $F$, and all other games end in ties. This gives the following point totals: $A$, $B$, and $C$ get $8$ points each, $D$ gets $11$ points, $E$ gets $9$ points, $F$ gets $5$ points, $G$ gets $6$ points, and $H$ gets $7$ points. Only $A$, $B$, and $C$ get an equal number of points, but since all games between $A$, $B$, and $C$ end in decisions, this meets the problem conditions.
Thus there must be a minimum of $6$ decisive games. Since a total of $8*7/2=28$ games are played, there must be a maximum of $22$ tie games.
NoYoo-hooForMe
05.05.2010 01:16
uglysolutions wrote: In a football tournament...
An interesting variant of this problem: suppose that a more traditional scoring system is used where a win is worth $2$ (not $3$) points, a tie is worth $1$ point, and a loss is worth $0$ points. What is the maximum number of ties in that case?
Note that my prior solution doesn't work if a win is $2$ points, since it assumes that a record of $1$ win, $1$ loss, and $5$ ties results in a different point total from a record of $7$ ties--but if a win is worth $2$ points then both records result in $7$ points.
What is the maximum number of ties in this case?
NoYoo-hooForMe
05.05.2010 01:50
uglysolutions wrote: In a football tournament...
We first show that it is not possible to meet the problem conditions if there are only $7$ decisive games. First, some team must be involved in at least $3$ decisive games. Suppose not. Then the only possible records are $2$-$0$, $1$-$1$, $0$-$2$, $1$-$0$, $0$-$1$, and $0$-$0$. There can be no more than $1$ team with any given record, except that there can be up to $3$ teams with a record of $1$-$1$. It is also easy to show that one cannot simultaneously have teams with a record of $1$-$1$ and $0$-$0$ (these result in the same point total). As a result there can be no more than $7$ teams--but there are $8$ teams. So the assumption that no team was involved in more than $2$ decisive games is false.
Accordingly assume that team $A$ is involved in $3$ decisive games. This leaves a total of $2*7-3=11$ decisions for the other $7$ teams to be involved in. If each of the other $7$ teams is involved in at least $1$ decision, then there must be at least $3$ such teams involved in exactly $1$ decision, and $2$ of those must have the same record. This is not allowed--so we can assume that exactly one of the other $7$ teams (besides $A$) is not involved in any decisions (has a $0$-$0$ record). Let us say that $B$ has a $0$-$0$ record.
Then none of the other $6$ teams will be allowed to have a $1$-$1$ record. It is then pretty easy to show that either at least $3$ of those teams must be involved in exactly $1$ decision, or at least $3$ of those teams must be involved in exactly $2$ decisions, and so (given that $1$-$1$ records are not possible) at least $2$ such teams must have the same record, and we have a contradiction.
So the problem conditions cannot be met if we have $7$ decisive games.
On the other hand, with $8$ decisive games, the problem conditions can be met. Supposed $A$ beats $B$, $A$ beats $G$, $A$ beats $H$, $B$ beats $C$, $C$ beats $D$, $E$ beats $G$, $E$ beats $H$, $F$ beats $H$, and all other games end in ties. Then $A$ has a record of $3$-$0$ and $10$ points, $B$ has a record of $1$-$1$ and $7$ points, $C$ has a record of $1$-$1$ and $7$ points, $D$ has a record of $0$-$1$ and $6$ points, $E$ has a record of $2$-$0$ and $9$ points, $F$ has a record of $1$-$0$ and $8$ points, $G$ has a record of $0$-$2$ and $5$ points, and $H$ has a record of $0$-$3$ and $4$ points. Only $B$ and $C$ have an equal point total ($7$ points each), but the game between $B$ and $C$ does not end in a tie, so the problem conditions are met.
Under the assumptions of this problem variant, the maximum number of tie games is $28-8=20$ tie games.