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.

There are $N$ players, and each player plays a match with everyone else exactly once. There is no tie. Each player's score is the number of matches he wins. What constraints can their scores be?

Is every system of scores in which all scores are between $0$ and $N-1$, the sum of scores equal to $N(N-1)/2$, and at most one $0$ score and at most one $N-1$ score achievable in such a matching setting, or there are actually more constraints? If it is the former, how to prove? If it is the latter, what other constraints will sufficient guarantee the set of scores be valid?

For example, for $4$ players, the set of scores cannot be $(3,3,0,0)$ since there can only be one player who wins 3 games.

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

The structures that you are looking at are known as tournaments in graph theory. The number of distinct score sequences for a given number of vertices is in the OEIS.

Your conditions are all necessary but not quite sufficient. The theorem that you are looking for is called Landau's Theorem:

A given non-decreasing sequence of non-negative integers $v_1\leq v_2\leq v_3\cdots\leq v_n$ is a score sequence of a tournament if and only if for each integer $k$ with $1\leq k\leq n$$$\sum_{i=1}^kv_i\geq\binom{k}{2}$$ with equality when $k=n$.

All of the graph theory books that I own contain proofs of this theorem, and there are many different proofs available online. Finally, note that there may be many non-isomorphic tournaments that share a single score sequence.

share|improve this answer
    
The second proof in the paper available here is especially elementary. –  Brian M. Scott May 16 '12 at 2:45
add comment

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.