Maths Olympiad Prep

Library / /68 of 70

Combinatorics Difficulty 8.9 Shortlist Prove it Romania

Given an integer N4N \ge 4, determine the largest value the sum
i=1k/2+1(ni/2+1) \sum_{i=1}^{\lfloor k/2 \rfloor + 1} (\lfloor n_i/2 \rfloor + 1)
may achieve, where k,n1,,nkk, n_1, \dots, n_k run through the integers subject to k3,n1nk1k \ge 3, n_1 \ge \dots \ge n_k \ge 1, and n1++nk=Nn_1 + \dots + n_k = N.

Solution

The required maximum is 2(N+2)/3\lfloor 2(N + 2)/3 \rfloor.

For more convenience, given a list of kk real numbers, the sublist consisting of the 1+k/21 + \lfloor k/2 \rfloor largest entries will be referred to as the upper half of the list, and its complement, i.e., the sublist consisting of the (k+1)/21\lfloor (k+1)/2 \rfloor - 1 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 ss in the statement, we list a sequence of operations which transform any given partition of NN 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 ss, whence the conclusion. In what follows, n1,,nkn_1, \dots, n_k will denote a generic partition of NN into at least three positive integers; the obvious verifications are omitted.

If the number of unit entries in the partition is less than (k+1)/21\lfloor (k+1)/2 \rfloor - 1, i.e., the lower half has some entry ni>1n_i > 1, splitting nin_i into 1 and ni1n_i - 1 increases length by 1, and ss by at least 1 if kk is odd, and preserves it otherwise; in either case, ss does not decrease.

If the number of unit entries in the partition exceeds (k+1)/2\lfloor (k+1)/2 \rfloor, i.e., the upper half has at least two unit entries, replacing two 1's by one 2 increases ss by 1 if kk is odd, and preserves it otherwise; in either case, ss does not decrease, and since N>3N > 3 the resulting partition has length at least three. (In fact, the length of the resulting partition would be less than three only in case N=3N=3, 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 NN 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, ss 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 ni>1n_i > 1, splitting nin_i into 1 and ni1n_i - 1 increases length by 1, and ss by 1 if kk is odd, and preserves it otherwise; in either case, ss 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 ni>1n_i > 1, replacing that unit entry and nin_i by 2 and ni1n_i - 1 preserves length, increases ss 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 NN 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 ss 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 ni>2n_i > 2, splitting nin_i into 1, 1 and ni2n_i - 2 increases length by 2, preserves ss 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 ni>2n_i > 2, splitting nin_i into 2 and ni2n_i - 2 increases length by 1, and ss by 1 if kk is odd, and preserves it otherwise; in either case, ss 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 NN 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 ss, and all partitions have length at least three. For this 'standard' partition, it is readily checked that s=2(N+2)/3s = \lfloor 2(N+2)/3 \rfloor and the conclusion follows.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.