Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|improve this answer
    
beautiful :), thank you ( I will accept this as soon as I can ) –  Listing Apr 6 '12 at 15:39

Your Answer

 
discard

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.