5
$\begingroup$

$8$ people participate in a tournament, so that each person plays with all the other people once. If a person wins against another, then the winner gets $2$ points, while the losing team will get none. If they tie, they each get $1$ point, respectively. When finished, the people are ranked depending on how many points they have in total. How many points does a person need to have, to secure their spot in the best four players.

I know that the maximum possible amount of points one can achieve is $14.$ I also know a score of $12$ gurantees you to be in the top $5.$ I'm not really sure how to continue with this information, how would I do this problem?

$\endgroup$
2
  • 1
    $\begingroup$ Imagine that there are five competitors (including yourself) that go undefeated against the other three. What would it take to be certain of being better than at least one of the other four? $\endgroup$
    – pokep
    Aug 2, 2020 at 22:47
  • $\begingroup$ Indeed, you might as well assume that there are only five players, and then add 6 points to all of their scores at the end (since the hardest situation is when they all beat the other three players from the original tournament). $\endgroup$ Aug 2, 2020 at 22:53

1 Answer 1

7
$\begingroup$

Note that there are a total of $56 = 2\binom{8}{2}$ total points given out in the tournament. If anyone gets at least $11$ points, then they are guaranteed to be in the top 4. Suppose for contradtiction otherwise, that there are at least $5$ people who earn $11$ points. Then that would mean there's only $56 - 5\times 11 = 1$ point left over that could have been won by one of the 3 remaining players. This is impossible though because these players also play against each other, and so within these $3$ players there must have been $6 = 2\binom{3}{2}$ points allocated from these games.

Now we show that getting $10$ points isn't enough to be in the top 4 (assuming arbitrary tie-breaking). We show that there is a scenario where there are five players who get $10$ points each. Label the players 1 through 8.

  • Player 1 beats 2, 3, 6, 7, 8
  • Player 2 beats 3, 4, 6, 7, 8
  • Player 3 beats 4, 5, 6, 7, 8
  • Player 4 beats 5, 1, 6, 7, 8
  • Player 5 beats 1, 2, 6, 7, 8
  • Player 6 beats 7
  • Player 7 beats 8
  • Player 8 beats 6

This scenario works.

$\endgroup$
0

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.