Consider a round robin tournament between 8 teams. A win gives 3 points, tie gives 1 point (to both teams) and loss gives 0 points.
If the match between two teams, say A & B, is a tie, then A & B can't end up with the same number points after the tournament.
The task is to find the maximum number of ties in the tournament.
I have no idea other than bashing all the cases. Please help me how to do it?
On
It's not possible to have more than one team draw all their matches.
It's not possible for more than one team to have six draws and one win (two such teams must have drawn their match, since neither lost).
Similarly, it's not possible for more than one team to have six draws and one loss, or for more than one team to have five draws and two wins, or five draws and two losses.
It's possible for the remaining three teams to have five draws, one win and one loss, but this can only happen if none of the matches between these three teams are drawn.
This means that at least six non-draws are required. Actually, all the above can happen simultaneously and you should be able to find a way to achieve this.
[edit to include an example, since another answer claims this is impossible]
Say A draws all their matches (7 points), B beats E but draws all other matches (9 points), C beats D and E but draws the rest (11 points), D loses to C but draws the rest (6 points), E loses to B and C but draws the rest (5 points), F beats G but loses to H (8 points), G beats H but loses to F (8 points), H beats F but loses to G (8 points).
Every pair of teams which drew their match finish on a different number of points. F and G finish on the same number, but didn't draw, and neither did G and H, or F and H.
Start by considering the possible outcomes for a player. All players play seven other players and they can tie, win or lose games.
This table shows the score achieved in different situations:
\begin{array}{|c|c|c|c|c|} \hline &Ties & Wins & Loses & Score \\ \hline A&7& 0& 0&7\\ \hline B&6& 0 &1 &6\\ \hline C&6& 1 &0 &9\\ \hline D&5& 0 &2 &5\\ \hline E&5& 1 &1 &8\\ \hline F&5& 2 &0 &11\\ \hline G&4& 0 &3 &4\\ \hline H&4& 1 &2 &7\\ \hline I&4& 2 &1 &10\\ \hline J&4& 3 &0 &13\\ \hline K&3& 0 &4 &3\\ \hline L&3& 1 &3 &6\\ \hline M&3& 2 &2 &9\\ \hline N&3& 3 &1 &12\\ \hline O&3& 4 &0 &15\\ \hline & & & &\\ \hline & & & &\\ \hline \end{array}
I could go further but there is no need because we want to maximise the number of ties.
We now want to choose 7 of these outcomes that yield seven different scores. We also want to pick outcomes from nearer the top of the table so that we maximise the number of ties.
So it's obvious we want outcomes A, B, C, D, E and F four our first six players. As well as having lots of ties, their scores are all different to each other.
Now we need to pick two more outcomes for the remaining players.
We can choose outcome G but not outcome H (because we already have an outcome with score of 7). We can choose outcome I instead.
Now we have eight different outcomes for our eight players... or do we?
Let's list the outcomes we have and sum our columns:
\begin{array}{|c|c|c|c|c|} \hline &Ties & Wins & Loses & Score \\ \hline A&7& 0& 0&7\\ \hline B&6& 0 &1 &6\\ \hline C&6& 1 &0 &9\\ \hline D&5& 0 &2 &5\\ \hline E&5& 1 &1 &8\\ \hline F&5& 2 &0 &11\\ \hline G&4& 0 &3 &4\\ \hline I&4& 2 &1 &10\\ \hline & & & &\\ \hline Total& 42& 6 & 8&\\ \hline \end{array}
Can you see the problem? There are more players losing than winning, but surely these should be equal!
Choosing outcome J instead of outcome I fixes that problem:
\begin{array}{|c|c|c|c|c|} \hline &Ties & Wins & Loses & Score \\ \hline A&7& 0& 0&7\\ \hline B&6& 0 &1 &6\\ \hline C&6& 1 &0 &9\\ \hline D&5& 0 &2 &5\\ \hline E&5& 1 &1 &8\\ \hline F&5& 2 &0 &11\\ \hline G&4& 0 &3 &4\\ \hline J&4& 3 &0 &13\\ \hline & & & &\\ \hline Total& 42& 7 & 7&\\ \hline \end{array}
That gives us a feasible set of outcomes and shows that the maximum possible number of ties is 42.