Get ready Part 21

Let $S$ be the set of all bead values. If $x \ge 1$ for all $x \in S$ , then $\sum_{x \in S}x \ge n > n-1$ . Thus we can find $x_1 \in S$ with $x_1 \le 0$ .

Suppose that $2 \le K \le n$ and we have found distinct $x_1,x_2,...,x_{K-1} \in S$ such that $\sum_{j=1}^q x_j \le q-1$ for all $1 \le q \le K-1$ . If it were true that $x + \sum_{j=1}^{K-1}x_j \ge K$ for all $x \in S \backslash \{x_1,x_2,...,x_{K-1}\}$ , then $\begin{aligned} n-1 & = \; \sum_{x \in S} x \; = \; \sum_{j=1}^{K-1}x_j + \sum_{x \not\in\{x_1,x_2,...,x_{K-1}\}}x \\ & \ge \; \sum_{j=1}^{K-1}x_j + (n+1-K)\left(K - \sum_{j=1}^{K-1}x_j\right) \; = \; K(n+1-K) - (n-K)\sum_{j=1}^{K-1}x_j \\ (n-K)\sum_{j=1}^{K-1}x_j & \ge \; K(n+1-K) - (n-1) \; = \; (K-1)(n-K) + 1 \\ \sum_{j=1}^{K-1}x_j & \ge \; K-1 + \frac{1}{n-K} \; > \; K-2 \end{aligned}$ which is a contradiction. Thus we can find $x_K \in S \backslash\{x_1,x_2,...,x_{K-1}\}$ such that $\sum_{j=1}^Kx_j \le K-1$ . Hence, by induction, we can label the elements $S$ as $x_1,x_2,...x_n$ such that $\sum_{j=1}^kx_j \le k-1$ for all $1 \le k \le n$ .

Let $y_i = x_i-1.$ If we label the beads with the $y_i,$ then the labels sum to $-1,$ and we want to string them out so that the partial sums are always at most $-1.$

Here is an algorithm for finding the place to cut. Pick a random bead to start at, call it bead 1, and write down the partial sums as we go around. Call those sums $s_1, s_2, \ldots, s_n = -1.$ Now, cut just after the bead $a$ that produced the largest partial sum $s_a.$ (If multiple beads produce the same largest partial sum $s_a,$ cut after the last one.) The partial sums of the resulting series will all be negative: if $b > a,$ the $(b-a)$ th partial sum of your string will be $s_b-s_a,$ and if $b \le a,$ the $(n-a+b)$ th partial sum will be $-1 + s_b-s_a.$ These partial sums will always be negative integers by construction, so they'll always be $\le -1.$

Here's an example: suppose my $y_i$ are $2,-1,1,4,-2,1,1,-4,-3,0,1,-1.$ The corresponding partial sums are $2,1,2,6,4,5,6,2,-1,-1,0,-1.$ Cut after the seventh bead (the bead that produced the last $6$ ). Then the partial sums of the resulting string are $-4,-7,-7,-6,-7$ and then $-5,-6,-5,-1,-3,-2,-1.$

I solved this problem by remembering the brainteaser about starting with an empty tank and driving in a circular loop with gas stations along the way, with just enough gas in the stations to make it around once. The proof above is reminiscent of the proof that you can always find a gas station to start at in order to make it around the loop without running out of gas.