Can we Cut a Necklace? - Problem Of The Week # 215

[Ackbach]

Here is this week's POTW:

-----

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, \dots, x_n$ satisfy
$$\sum_{i=1}^k x_i\le k-1 \qquad \text{for} \; k=1, 2, \dots, n.$$

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 215 - May 10, 2016

This was Problem A-4 in the 1995 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

Let $s_{k} = x_{1} + \cdots + 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} + \cdots + x_{i} \leq i(n-1)/n$, but the right side may be replaced by $i-1$ since the left side is an integer.