NEO01 - EDITORIAL (Unofficial)

Nice explanation! It is true that adding a larger number to a nonnegative partition is better than adding a smaller number, but the numbers outside the partition P should not be ignored since they contribute to the answer. Let the sum of numbers outside P be Q, then

h(P\cup\{a\})+(Q-a)=(P_{cnt}+1)(P_{sum}+a)+(Q-a)=P_{cnt}P_{sum}+P_{sum}+aP_{cnt}+Q
h(P\cup\{b\})+(Q-b)=(P_{cnt}+1)(P_{sum}+b)+(Q-b)=P_{cnt}P_{sum}+P_{sum}+bP_{cnt}+Q

If $a < b \implies h(P \cup {a}) + (Q-a) < h(P \cup {b}) + (Q-b) \implies$adding b is preferable to a. So it leads to the same conclusion :slight_smile:

1 Like

@meooow, you’re very correct with that. I did claim 2 first to make sure negatives are in single-element partitions before doing claim 3, but your one-step explanation is great since it’s shorter proof for all three claims! :smiley: