Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have a round robin tournament with $n$ teams where each team get in every single 1-1 match:

  • $3$ points for a win,
  • $1$ point for a tie,
  • $0$ points for a loss.

I would like to decide the truth of this conjecture:

If the tournament ends with all the teams with the same score then every team had as much wins as losses.

It is certainly true for $n=3$ but even checking the case n=4 is nontrivial.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

There's a counterexample with 8 teams: A, B, C, X, Y, Z, M, S

  • S wins against M
  • M wins against A, B, and C
  • A wins against Y and Z
  • B wins against Z and X
  • C wins against X and Y
  • X wins against M and A
  • Y wins against M and B
  • Z wins against M and C
  • Everything else ties.

Teams ABCXYZ each win twice and lose twice for a score of $2\times0+3\times1+2\times3=9$.

Team M wins against ABC and loses to XYZS, for a score of $4\times0+0\times1+3\times3=9$.

Team S wins once and ties 6 times, for a score of $0\times 0+6\times1+1\times3=9$.


How I found this: First, for easier counting I changed the rules by subtracting $n-1$ points from each team such that ties give $0$ points, and wins and losses each $2$ and $-1$. That makes it easier to see which possible combinations of wins and losses add up to the same. Then I'm looking for a directed graph with no 2-loops such that the value of each node is the same.

Since there are as many wins as losses, in a counterexample there must be at least one team that win more times than they lose. But that team cannot possibly have less than $2$ points, so let's see which way we can make a node with value 2: They are: $1W+0L$, $2W+2L$, $3W+4L$ and so forth -- so if we have one of $1W+0L$ and $3W+4L$ the number of wins/losses add up right.

From there it was just a matter of puzzling out where to add $2W+2L$ nodes to the graph such that we don't need more than one match to take place between the same two teams.

share|improve this answer
    
Nice solution! So is $n=8$ actually the minimum $n$ such that the statement is false? –  Marco Sep 25 '12 at 19:34
    
Yes, $n=8$ is minimal. A counterexample has to contain a team that lose more times than they win. If they are to make at least 2 points on my modified scale, they can't possibly have played less than non-tied 7 matches. That team together with all its opponents make at least 8 teams in the tournament. –  Henning Makholm Sep 25 '12 at 20:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.