Cutting numbers into parts
Solution 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