Let \(n=2m+1\). To avoid dealing with halves, we’ll also multiply everything by 2: a win is 2 points, a draw is 1.
Although the problem talks about draws, everything becomes transparent once we count the other games instead. Let \(h_i\) be the number of games played by player \(i\) that were not draws, and let \(w_i\) be player \(i\)’s number of wins.
The total score is now twice the number of matches, i.e., \(n(n-1)\). Thus, the average score per player is \(n-1\).
Player \(i\) draws \(n-1-h_i\) games and wins \(w_i\), so their score is \((n-1-h_i)+2w_i\). Let \(t_i = 2w_i - h_i\), then \(t_i\) is the difference between this player’s score and the average.
We can observe that the values \(t_i\):
That last inequality is the key insight: a draw never moves you away from the average, only a game with a winner does. A player who finished \(k\) points away from the average must have played at least \(k\) games that had a winner.
In order to make all scores distinct, we will need to have enough games with a winner, and this will give us a tight upper bound on the number of draws possible.
Clearly, if all \(t_i\) are distinct, the smallest possible sum of their absolute values corresponds to the situation where the set of all \(t_i\) is exactly the set \(E=\{-m,\dots,-1,0,1,\dots,m\}\).
Thus, if we look at each player and count how many of their games had a winner, the total must always be at least \(\sum E = m(m+1)\). And as each game is counted twice (once for the winner, once for the loser), every valid tournament must have at least \(m(m+1)/2\) games that are not draws.
One possible construction:
We have just constructed a tournament with as many draws as possible.
Each tournament with fewer draws is also possible. Probably the easiest way to construct them is to just handwave it: start greedily turning random draws into a win + a loss such that after each update the scores are still distinct, and backtrack if you get stuck. The good states are so dense that in practice this solution quickly constructs all solutions, and it’s really easy both to implement and to test – once it reaches the state with 0 draws, we know that we are done, as we must have seen all intermediate states along the way.
Below we show an alternative: one possible deterministic construction.
Take three players where \(x\) beats \(y\) and both \(x\)–\(z\) and \(z\)–\(y\) are drawn. Now, rewrite the triangle as follows: \(x\) beats \(z\), \(z\) beats \(y\), and \(x-y\) is now a draw. Clearly, the new point totals are the same as before, but now we have one fewer draw. Whenever we can apply this move, we can use it to reduce the number of draws.
Triangle rotations alone cannot reach small values of \(d\), because for those the players need to be farther away from the average – which means that we can no longer preserve the score totals.
One possible way how to deal with the smaller values of \(d\) is to change already the starting configuration to one with fewer draws. Instead of starting with the tournament with the most draws possible, we can choose a value \(b\) and start with a tournament such that:
Clearly, the top \(b\) players are resolved – they will always remain top \(b\) players with mutually distinct scores, regardless of how we change the games among the rest. And thus, among the remaining players we can now freely apply the triangle rule.
It can be shown that if we start with the smallest \(b\) such that the starting tournament has \(d\) or more draws, it will always be possible to reduce their count to exactly \(d\) draws – we can always find enough triangles to rotate.
