2

I have just correctly solved this programming problem. The problem is the following:

$N$ teams play a round-robin tournament, i.e. each pair of teams plays exactly one game and the winner gets 3 points, the loser gets 0 points, and both teams get 1 point in case of a draw. Q1: What is the minimum score the 1st place can get? Q2: What is the maximum score the last place can get?

I started tackling this problem by brute-force calculations and the results were that the minimum score for the first place is achieved when all games result in a draw, therefore the answer to the first question is $N-1$. The maximum score for the last place is achieved when all the teams have won exactly half of their matches and lost in the other half (if $N$ is even, then each team plays exactly one draw). So the answer for the second question is $3(N-2)/2 + 1$ and $3(N-1)/2$ for even and odd $N$ respectively. So I plucked in these equations into my program and got Accepted.

These results are purely empirical, but they are correct. I tried to prove them by using weighed graphs and playing around with matrices but was not able find a useful trail. Can someone please set me on the right direction?

Armen Tsirunyan
  • 869

1 Answers1

2

Hints:

Minimum score of the winner: You have shown that the answer is at most $N-1$ by constructing an example. What remains is to show that the answer cannot be less than $N-1$. Based on the minimum number of points given to the teams in a single game, find the minimum number of points given in the tournament in total, i.e., the sum of the scores of the teams. Now assume that the winner got less than $N-1$ points...

Maximum score of the loser: Again we need to show that the loser cannot get more points than what you have constructed. Find the maximum number of points given in the tournament in total. Then you can find the maximum average of the scores of the teams. You know that there must be a team that didn't get more points than the maximum average. This involves rounding so you need to split to cases $N$ odd or even.

(The first question can also be proved by considering the average as I did in the second question, and the second question can also be proved by considering only the sum and using proof by contradiction, as I did in the first question. I think the choices I made make the proofs simpler, but someone might say that it is more elegant to use similar proofs for both questions.)

JiK
  • 5,815
  • 19
  • 39