6
$\begingroup$

Karim Benzema likes to remember a small soccer tournament in which he participated many years ago. Karim remembers the following:

  • There was a certain number $N$ of teams participating in the tournament. (But Karim does unfortunately not remember the value of $N$.)
  • Each team played exactly one match against each of the other teams.
  • For a win/draw/loss a team respectively scored 3/1/0 points.
  • At the end of the tournament, Karim's team had gained more points than any of the other teams.
  • At the end of the tournament, Karim's team had won fewer matches than any of the other teams.

Question: What is the smallest possible value $N\ge2$ that would be compatible with Karim's recollections?

$\endgroup$
10
$\begingroup$

This is possible with $N = 8$ teams. Karim's team won 2 games, and tied the other 5, for a total of 11 points. The other teams won three games each, lost three games, and either tied or lost to Karim's team. The teams that tied Karim's team did best, for a total of 10 points (3 wins, 1 tie).

To prove this is the minimum, work with the number of wins Karim's team had.

With 0 wins for Karim's team, each other team must have had at least 1 win and 1 loss, playing each other. So they played at least two games, so there must be at least 3 of them. For $N=4$, Karim's team got 3 points in ties, while the others got 1 win, 1 tie, for a total of four points. Adding more teams adds at least as many points to the other teams as it does to Karim's, so that won't help.

Similarly, with 1 win for Karim's team, the others must win 2 games and lose 2 games, so there must be at least 5 of them. Karm's team scores 7 points (1 win, 4 ties). The teams that tie Karim's team score 7 points (2 wins, 1 tie). Again, adding more teams gives at least as many points to the other teams as it does to Karim's, so that won't help.

Thus, Karim's team must have won at least two games. That works for $N=8$, as described above.

$\endgroup$
  • $\begingroup$ damn you were exactly 41 seconds faster than me $\endgroup$ – The Dark Truth Oct 8 '15 at 13:40
4
$\begingroup$

N=8

First we look at all teams except Karim's so $N-1$ teams.

If they had all won exactly one time against one other team, lost exactly one time (to minimize the highest amount of points) and played a draw in all $N-3$ other games(-1 since they can't play against themself, -1 won, -1 lost), then Karim's Team could only get a maximum of $N-1$ points (all games played with draw) while all other teams get exactly $N$ points (N-3 draw + 1 win).

To maximize the possible interference from Karim's Team against the other Teams lets say that they won exactly half of their games against each other and lost exactly half their matches against each other. Then from $N-2$ games (-1 excluding Karin's team, -1 can't play against themself) they would win exactly $\frac{N-2}{2}$ games and lose the same amount of games.

Now Karim's team should not lose against another team, therefore each other Team could only get 1 extra point from Karin's Team in a draw for a maximum of $3\times\frac{N-2}{2}+1=\frac{3N}{2}-2$ points.

Karims Team can have at most $\frac{N-2}{2}-1=\frac{N}{2}-2$ wins and $N-1-(\frac{N}{2}-2)=\frac{N}{2}+1$ draws for a total of $3*(\frac{N}{2}-2)+(\frac{N}{2}+1)=2N-5$ points.

As Karim's team needs at least one point more that the Rest they need $\frac{3N}{2}-1$ points.

The Rest is simple calculation:

$2N-5=\frac{3N}{2}-1$

$\frac{N}{2}-5=-1$

$\frac{N}{2}=4$

$N=8$

$\endgroup$
2
$\begingroup$

I'm thinking that the answer is:

he recollected wrong

To have more points, but fewer wins than the other teams means that his team had a lot of ties. Let's assume they have 0 wins and all ties. That's an average of 1 point per game.
In a game with a winner and loser, a team, on average, gets 1.5 points.
If there are 4 teams, and each of the other teams has a win, a loss, and a tie (you), they all beat you in points.
If there are 5 teams, with a win, loss, tie (you) and variable, they are already at your point total, with 1 game left.

Keep on extrapolating up, and that win advantage keeps your team from having the most points.
Edit
Ah, I see where I went wrong. I was thinking that wins weren't useful, since they'd be offset by wins of the other team. And they are, but the other team gets losses to match the wins, even for the offset wins.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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