I encountered a Putnam problem and had a couple of questions about the proposed solutions:
Suppose we have a necklace of $n$ beads. Each bead is labelled 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, \dots, x_n$ satisfy $$ \sum_{i=1}^{k} x_i \leq k-1 \ \ \text{for} \ \ k = 1,2, \dots, n$$
One solution could be to use induction. Another solution could be the following:
Number the beads $i=1, \dots, n$ starting from an arbitrary position. Let $z_i$ be the label of the $i^{th}$ bead such that $z_i = z_{n+i}$. Let $S_j = z_1 + \dots + z_j-j(n-1)/n$, so $S_{n+j} = S_j$. Then the sum of the labels on the beads $m+1, m+2, \dots, m+k$ is $S_{m+k}-S_m +k(n-1)/n$. So we want to choose $m$ as large as possible. Then: $$S_{m+k} - S_m +\frac{k(n-1)}{n} \leq k-\frac{k}{n}$$ where we can replace the RHS with $k-1$ since the LHS is an integer.
First of all, what is the motivation of defining $S_j$ as it is? Also how does $S_{n+j} = S_j$? We know that $$S_{n+j} = z_1 + \dots + z_j + \dots + z_n + \dots z_{n+j} -(n+j)(n-1)/n$$
$$ = S_{j} + z_{j+1}+ \dots + z_n + \dots +z_{n+j} - n(n-1)/n$$
Also how is $S_{m+k} - S_m +\frac{k(n-1)}{n} \leq k-\frac{k}{n}$? Is it because $S_{m+k}-S_m$ could be negative?
Here are some clarifications.
First of all, the big idea of defining $S_j$ in this way is that we can also write $$S_j = (z_1 - \tfrac{n-1}{n}) + (z_2 - \tfrac{n-1}{n}) + \dots + (z_j - \tfrac{n-1}{n})$$ where $\frac{n-1}{n}$ is the average value of $x_1, \dots, x_n$ (since they add up to $n-1$) so $S_j$ sums up the excesses: how much the first $j$ terms are bigger than average. I guess ultimately the motivation behind the definition of $S_j$ is "it works", but the definition doesn't entirely come out of the blue sky. In the end, we'll choose $m$ so that $S_m$ is large (which means that $z_1, \dots, z_m$ tend to be larger than average) and then break the necklace so we start at $z_{m+1}$ and end with $z_m$: putting the larger-than-average terms on the end of the necklace.
This alternate form of $S_j$ above also explains why $S_{n+j} = S_j$: if you add up $z_i - \frac{n-1}{n}$ over $i=1, \dots,n$, you get $0$, because the sum of the deviations from the mean over all $n$ terms is $0$. Or we can continue from your derivation: in $$S_{n+j} = S_j + (z_{j+1} + z_{j+2} + \dots + z_{n+j}) - \frac{n(n-1)}{n},$$ the leftover $z$'s include every label on the necklace once, so they add up to $n-1$, while $-\frac{n(n-1)}{n}$ simplifies to $-(n-1)$.
Finally, you're missing a key step towards the end of the proof. After noticing that $$z_{m+1} + z_{m+2} + \dots + z_{m+k} = S_{m+k} - S_n + \frac{k(n-1)}{n},$$ we want to choose $m$ so that the value of $S_m$ is the largest of any of $\{S_1, S_2, \dots, S_n\}$ and therefore at least as large as any $S_i$. In particular, $S_m$ will be at least as large as $S_{m+k}$ for any $k$.
Then we have $S_{m+k} - S_m + \frac{k(n-1)}{n} \le \frac{k(n-1)}{n}$ because $S_{m+k} \le S_m$, so $S_{m+k} - S_m \le 0$.