Given an integer , determine the largest value the sum
may achieve, where run through the integers subject to , and .
Solution
The required maximum is .
For more convenience, given a list of real numbers, the sublist consisting of the largest entries will be referred to as the upper half of the list, and its complement, i.e., the sublist consisting of the smallest entries, as the lower half of the list. Notice that the lower half of a list consisting of at least three real numbers is never empty.
To maximize the sum in the statement, we list a sequence of operations which transform any given partition of into at least three positive integers into another such whose lower half is all 1, and the upper half is all 2 except possibly one unit entry; moreover, each operation yields a partition into at least three positive integers, and does not decrease , whence the conclusion. In what follows, will denote a generic partition of into at least three positive integers; the obvious verifications are omitted.
If the number of unit entries in the partition is less than , i.e., the lower half has some entry , splitting into 1 and increases length by 1, and by at least 1 if is odd, and preserves it otherwise; in either case, does not decrease.
If the number of unit entries in the partition exceeds , i.e., the upper half has at least two unit entries, replacing two 1's by one 2 increases by 1 if is odd, and preserves it otherwise; in either case, does not decrease, and since the resulting partition has length at least three. (In fact, the length of the resulting partition would be less than three only in case , and the partition we start with is 1, 1, 1 — the unique partition of 3 into three positive integers. This is, however, ruled out by hypothesis.)
Consequently, a partition of into at least three positive integers can be transformed into another such whose lower half is all 1, and the upper half has at most one unit entry; moreover, does not decrease in the process, and the lengths of the partitions involved are at least three. Henceforth, all partitions are assumed to have such a structure.
If the upper half has no unit entry, but has some odd entry , splitting into 1 and increases length by 1, and by 1 if is odd, and preserves it otherwise; in either case, does not decrease, and the outcome is a partition into at least three positive integers, whose lower half is all 1, and the upper half has exactly one unit entry and fewer odd entries exceeding 1.
If the upper half has exactly one unit entry and some odd entry , replacing that unit entry and by 2 and preserves length, increases by 1, and the resulting partition has length at least three, an all 1 lower half, and the upper half has fewer odd entries exceeding 1 and no unit entry.
Consequently, every partition of into at least three positive integers can be transformed into another such with an all 1 lower half, and an all even upper half except possibly one unit entry; moreover, at each stage, the length of the partition is at least three, and does not decrease. Henceforth, all partitions are assumed to have such a structure.
If the upper half has no unit entry, but has some entry , splitting into 1, 1 and increases length by 2, preserves and yields a partition into at least three positive integers, whose lower half is all 1, and the upper half is all even except for exactly one unit entry and has fewer entries exceeding 2.
Finally, if the upper half is all even except for exactly one unit entry, and has some entry , splitting into 2 and increases length by 1, and by 1 if is odd, and preserves it otherwise; in either case, does not decrease, and the outcome is a partition of length at least three, whose lower half is all 1, and the upper half is all even with fewer entries exceeding 2.
Consequently, any given partition of into at least three positive integers can be transformed into another such whose lower half is all 1, and the upper half is all 2 except for at most one unit entry; moreover, the transformation does not decrease , and all partitions have length at least three. For this 'standard' partition, it is readily checked that and the conclusion follows.