MathDB
Proving an identity for set of scores in a tournament

Source:

November 3, 2010
combinatorics unsolvedcombinatorics

Problem Statement

We have pp players participating in a tournament, each player playing against every other player exactly once. A point is scored for each victory, and there are no draws. A sequence of nonnegative integers s1≤s2≤s3≤⋯≤sps_1 \le s_2 \le s_3 \le\cdots\le s_p is given. Show that it is possible for this sequence to be a set of final scores of the players in the tournament if and only if (i)∑i=1psi=12p(p−1)(i)\displaystyle\sum_{i=1}^{p} s_i =\frac{1}{2}p(p-1) and\text{and} (ii) for all k<p,∑i=1ksi≥12k(k−1).(ii)\text{ for all }k < p,\displaystyle\sum_{i=1}^{k} s_i \ge \frac{1}{2} k(k - 1).
Back to ProblemsView on AoPS