Cutting numbers into parts

Question

Let $x_1,x_2,\dots,x_n$ be positive integers written on a line, and $k\leq n$ a positive integer. Can we always cut the numbers into $k$ parts according to the line ordering to satisfy the following property: For each part, there is a number at one of the two ends of the part that if we remove it, then the sum of the numbers in the part is no greater than the sum of the numbers in any other part?

An idea is to use induction on $k$. For $k=1$ we don't need to cut anything, so the statement is trivially true. For larger $k$, if we can show that there is always an appropriate "cut point" to cut the first part, and then use the induction hypothesis to cut the remaining numbers into $k-1$ parts, we would be done. However, it is not obvious how to find this cut point or whether it always exists.

Another thing to note is that if $k=n$, we just cut the numbers into $n$ parts with one number each, and again this trivially works.

Answer 1

This is my first answer here :-)

Can we always cut the numbers into k parts according to the line ordering to satisfy the following property: For each part, there is a number at one of the two ends of the part that if we remove it, then the sum of the numbers in the part is no greater than the sum of the numbers in any other part?

Yes, we can.

I found out a simple algorithm, let me explain it. The idea is to reason by pseudo-induction (as k is bounded between 1 and n), but starting from k=n and going down.

I take n integers x1 x2 ... xn (I may edit the text format as soon as I have more experience) and x1 ≤ x2 ≤ ... ≤ xn.

Cutting in k=n is obvious, (x1) (x2) ... (xn).

Cutting in k=n-1 is obvious (x1, x2) (x3) ... (xn). The rule says that "if I remove x2 in (x1, x2) then the sum of the remaining items* is less than any of the rest". Here, x1 ≤ x3 ≤ ... ≤ xn, so it's ok.

( * By the way, I am not sure why you edited the question in "one of the two ends", as I will always remove the higher index [e.g. (x2) from (x1, x2)] to prove with ease that the property is valid.)

Now, I am going to explain the algorithm to find the cut j=k-1 parts, knowing the cut for k parts. I will note Pi (with 2≤i≤n) the part that contains (x1, ..., xi) and Si the sum of the elements of Pi.

I have a (P2) (x3) (x4) ... (xn) k-partition that complies to the property. I want to find a j-partition (with one less part) that complies to the property.

The algorithm splits here in several cases.

a) If S2≤x4, then (P3) (x4) ... (xn) is my solution for j parts. Plus, I can now reuse the a) algorithm starting with P3 instead of P2, and compare S3 to x5.

b) If S2>x4, then (P2) (x3, x4) (x5) ... (xn) is my solution for j parts. Now we can't apply a) again, so we must figure out the next step (j-1), with another two possibilities. Luckily, this is again about comparing S3 and x5 :

b1) If S3≤x5 then (P4) (x5) (x6) ... (xn) is my solution for j-1 parts (obvious), and I can get back to the a) algorithm.

b2) If S3>x5 then (P3) (x4, x5) (x6) ... (xn) is my solution for j-1 parts (almost as obvious: x4 < S2 < S3, and S2 < x3+x4 < x4+x5), and I can get back to the b) algorithm.

With a), b), b1) and b2), I have described the algorithm.

Giving two examples with numbers : n=8: 13 14 27 30 35 86 117 354
k=8: (13) (14) (27) (30) (35) (86) (117) (354) -- trivial
k=7: (13 14) (27) (30) (35) (86) (117) (354) -- using a
k=6: (13 14 27) (30) (35) (86) (117) (354) -- using a
k=5: (13 14 27) (30 35) (86) (117) (354) -- using b
k=4: (13 14 27 30 35) (86) (117) (354) -- using b1
k=3: (13 14 27 30 35) (86 117) (354) -- using b
k=2: (13 14 27 30 35 86 117) (354) -- using b1
k=1: trivial

n=8: 13 14 27 30 35 69 117 354
k=8: (13) (14) (27) (30) (35) (69) (117) (354) -- trivial
k=7: (13 14) (27) (30) (35) (69) (117) (354) -- using a
k=6: (13 14 27) (30) (35) (69) (117) (354) -- using a
k=5: (13 14 27) (30 35) (69) (117) (354) -- using b
k=4: (13 14 27 30) (35 69) (117) (354) -- using b2
k=3: (13 14 27 30 35) (69 117) (354) -- using b2
k=2: (13 14 27 30 35 69 117) (354) -- using b1
k=1: trivial

Thanks for reading!

Answer 2

We can always cut the numbers in such a way.

To avoid the hassle of dealing with tiebreaking, replace each $x_i$ by $x'_i=2^nx_i+2^{i-1}.$ Note $\sum_{i\in S} x'_i\leq \sum_{i\in T}x'_i$ implies $\sum_{i\in S} x_i\leq \sum_{i\in T}x_i,$ but distinct subsets have distinct sums. (Alternatively, work with real numbers and invoke compactness/general position.)

Let $M$ be the largest integer such there there are cuts $0=c_0<c_1<\dots<c_k=x_1+\dots+x_n$ with $c_j-c_{j-1}\geq M$ for all $1\leq j\leq k.$ Fix a choice of such $c_0,\dots,c_k.$

For any real $m>0$ we can try the strategy of taking from the left until we get a sum of at least $m,$ take these numbers as one part, then repeat. If this uses up all the numbers exactly, then we have a cut satisfying the required property, which we are supposing doesn't exist. The strategy will fail either by undershooting - not using up all the numbers - or by overshooting - using up all the numbers and not ending up with enough parts (any unmade cuts are placed after $x_n$ for the analysis).

For $m=M$ the cuts $0=t_0<t_1<\dots<t_k$ produced by this strategy satisfy $t_i\leq c_i,$ because if we have the induction hypothesis $t_{i-1}\leq c_{i-1}$ then $c_i-c_{i-1}\geq M$ implies $c_i-t_{i-1}\geq M,$ which means the strategy will choose $t_i\leq c_i.$

For $m=M+1,$ denote the cuts obtained by $t'_0,\dots,t'_k.$ It must be different, because otherwise all the parts are at least $M+1.$ But it can only be different if $t_i-t_{i-1}=M$ for some $i,$ where the strategy for $m=M+1$ would instead take exactly one more number. Note $c_j-c_{j-1}=M$ for some $j$ as well. I claim $i=j.$ We have $i\geq j$ because $c_j=t_i\leq c_i.$ Since the $M+1$ strategy only takes one more number for $t'_{j+1},$ we have $t'_{i+1}\leq c_{j+2},$ which if $i>j$ would give $t'_z\leq c_z$ for $z>i,$ meaning that $t'$ gives a partition with minimum at least $M+1,$ a contradiction.

We have shown that there are cuts $t_0<\dots<t_j=c_j$ giving $j$ parts with sums greater than $m,$ such that removing the rightmost element from any of these parts gives a sum of less than $m.$ Symmetrically we can use the reverse strategy starting from the right, to get cuts $c_{j+1}=T_{j+1}<\dots<T_k$ giving $k-j-1$ parts with sums greater than $m,$ such that removing the leftmost element from any of these parts gives a sum of less than $m.$ Putting these together, the cuts $t_0<\dots<t_j<T_{j+1}<\dots<T_k$ have the required property.

Answer 3

Solution with scrambled numbers on a line

Let $x_1,x_2,…,x_n$ be positive integers written on a line, and k≤n a
positive integer. Can we always cut the numbers into k parts according to
the line ordering to satisfy the following property: For each part, there is
a number at one of the two ends of the part that if we remove it, then the
sum of the numbers in the part is no greater than the sum of the numbers in
any other part?

Yes, we can! (bis)

a) Play the game to understand how it works.

I played, starting from k=n parts, trying to group two of them at every step until k=2. Here is what I ran into :

A basic try

Another try

Please, don't tell me about the colors I used.

b) Then, think about sums

I found out an interesting way of displaying them. This will help to figure out how to cut the chain of numbers $(x_1, x_2, ..., x_n)$ in pieces.

For 1 ≤ i ≤ j ≤ n, let's define $X_{i,j}=\sum_{k=i}^j x_k$ to describe all the sums of all adjacent numbers from $x_i$ to $x_j$; with the convention that $X_{i,i}=x_i$.

If we write down the array of the $X_{i,j}$, the chain of numbers is in the diagonal, and the upper-right part of the matrix are the sums - you can read horizontally on line i how $x_i$ sums up to his right neighbours (up to $x_n$) and you can read vertically on column j how $x_j$ sums up to his left neighbours (down to $x_1$). You can also notice that there are many pathways that describe the subsums of the groups that we are trying to describe (e.g. you can read horizontally $x_1+x_2+x_3$ or vertically $x_3+x_2+x_1$)

Using the table to form two groups of numbers

Using the table to form three groups of numbers

Using the table to show eventual multiple solutions

c) Any proof in sight?

The key is to understand that it is always possible to transform three parts L, M and R (left, middle and right) in two (either (LM)vs.R or (L)vs.(MR) or something very close if you try to tamper with the actual numbers that are in L, M and R).

Hint of demonstration : I got something ab absurdum. I tried to build some set of numbers where 0 ≤ R-L ≤ M+1 (this way, you create a "big jump" with M which is bigger than the difference between R and L). Even if you create artificial zero boundaries (0 0 L 0 0) (M) (0 0 R 0 0), you'll realize that there is always a possibility to make two number groups that keep the property.

With this experience, though I didn't write a proof of what I am writing here, I am confident that I can solve any set of numbers in about the time you need to write these down by hand on a piece of paper. I will enter the numbers in a table to make the array appear, compute their sum and divide it by k to get a view of the size I want to find in the array, then solving is just greying a few squares in the array and drawing a few k-1 lines to cut your string of numbers in k groups.

I enjoyed my time trying to figure this out. I hope I made it clear enough.

I hope this helps!