Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a single round-robin chess tournament with $n$ players where the winner/loser gets $2/0$ points and on even both players get $1$ point, we sort the final amount of individual points ($p_1 \leq p_2 \leq \ldots \leq p_n$).

I am looking for a sharp lower bound $f(k)$ for $p_k$ with $1 \leq k \leq n$ and without any knowledge about the other points.

My approach: It is trivial that $f(1)=0$, because one player can lose against all others. Besides $f(2)=1$ because if a player has $0$ points he will be always unique with that property and on the last place, however it is possible that two players draw against each other and lose against all others. Besides it is certainly true that $f(k)\leq k-1$, because if $k>1$, $k$ players can draw against each other and lose against all others, making $p_k=k-1$. However I can not show that this bound is sharp because when $k$ is high, they might be other effects to consider i am unable to see yet.

share|cite|improve this question
up vote 4 down vote accepted

Note that the bottom $k$ contestants will play each other - a total of $\frac{k(k-1)}2$ games, and there are two points awarded for each game, so between them they will obtain at least $k(k-1)$ points.

The top club amongst them cannot score less than the average number of points, so must gain at least $(k-1)$.

share|cite|improve this answer
beautiful :), thank you ( I will accept this as soon as I can ) – Listing Apr 6 '12 at 15:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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