Putnam 1995, Problem A-4

Suppose we have a necklace of \( n \) beads. Each bead is labeled with an integer and the sum of all these labels is \( n-1 \). Prove that we can cut the necklace to form a string whose consecutive labels \( x_1, x_2, \ldots, x_n \) satisfy
\[
\sum_{i=1}^k x_i \leq k-1 \quad \text{for } k = 1, 2, \ldots, n.
\]

Solution:
Let \( s_k = x_1 + \dots + x_k - k(n-1)/n \), so that \( s_n = s_0 = 0 \). These form a cyclic sequence that doesn't change when you rotate the necklace, except that the entire sequence gets translated by a constant. In particular, it makes sense to choose \( x_i \) for which \( s_i \) is maximum and make that one \( x_n \); this way \( s_i \leq 0 \) for all \( i \), which gives \( x_1 + \dots + x_i \leq i(n-1)/n \), but the right side may be replaced by \( i - 1 \) since the left side is an integer.