Maths Olympiad Prep

Library / /14 of 14

Combinatorics Difficulty 9.2 IMO level Prove it IMO

Let nn be a positive integer. Find the smallest integer kk with the following property: Given any real numbers a1,,ada_{1}, \ldots, a_{d} such that a1+a2++ad=na_{1}+a_{2}+\cdots+a_{d}=n and 0ai10 \leqslant a_{i} \leqslant 1 for i=1,2,,di=1,2, \ldots, d, it is possible to partition these numbers into kk groups (some of which may be empty) such that the sum of the numbers in each group is at most 11.

Solution

Answer. k=2n1k=2n-1.

Solution 1. If d=2n1d=2n-1 and a1==a2n1=n/(2n1)a_{1}=\cdots=a_{2n-1}=n/(2n-1), then each group in such a partition can contain at most one number, since 2n/(2n1)>12n/(2n-1)>1. Therefore k2n1k \geqslant 2n-1. It remains to show that a suitable partition into 2n12n-1 groups always exists.
We proceed by induction on dd. For d2n1d \leqslant 2n-1 the result is trivial. If d2nd \geqslant 2n, then since
(a1+a2)++(a2n1+a2n)n \left(a_{1}+a_{2}\right)+\ldots+\left(a_{2n-1}+a_{2n}\right) \leqslant n
we may find two numbers aia_{i}, ai+1a_{i+1} such that ai+ai+11a_{i}+a_{i+1} \leqslant 1. We "merge" these two numbers into one new number ai+ai+1a_{i}+a_{i+1}. By the induction hypothesis, a suitable partition exists for the d1d-1 numbers a1,,ai1,ai+ai+1,ai+2,,ada_{1}, \ldots, a_{i-1}, a_{i}+a_{i+1}, a_{i+2}, \ldots, a_{d}. This induces a suitable partition for a1,,ada_{1}, \ldots, a_{d}.

Solution 2. We will show that it is even possible to split the sequence a1,,ada_{1}, \ldots, a_{d} into 2n12n-1 contiguous groups so that the sum of the numbers in each group does not exceed 11. Consider a segment SS of length nn, and partition it into segments S1,,SdS_{1}, \ldots, S_{d} of lengths a1,,ada_{1}, \ldots, a_{d}, respectively, as shown below. Consider a second partition of SS into nn equal parts by n1n-1 "empty dots".
Figure 1
Assume that the n1n-1 empty dots are in segments Si1,,Sin1S_{i_{1}}, \ldots, S_{i_{n-1}}. (If a dot is on the boundary of two segments, we choose the right segment). These n1n-1 segments are distinct because they have length at most 11. Consider the partition:
{a1,,ai11},{ai1},{ai1+1,,ai21},{ai2},,{ain1},{ain1+1,,ad}. \left\{a_{1}, \ldots, a_{i_{1}-1}\right\},\left\{a_{i_{1}}\right\},\left\{a_{i_{1}+1}, \ldots, a_{i_{2}-1}\right\},\left\{a_{i_{2}}\right\}, \ldots,\left\{a_{i_{n-1}}\right\},\left\{a_{i_{n-1}+1}, \ldots, a_{d}\right\}.
In the example above, this partition is {a1,a2},{a3},{a4,a5},{a6},,{a7},{a8,a9,a10}\left\{a_{1}, a_{2}\right\},\left\{a_{3}\right\},\left\{a_{4}, a_{5}\right\},\left\{a_{6}\right\}, \varnothing,\left\{a_{7}\right\},\left\{a_{8}, a_{9}, a_{10}\right\}. We claim that in this partition, the sum of the numbers in each group is at most 11.
For the sets {ait}\left\{a_{i_{t}}\right\} this is obvious since ait1a_{i_{t}} \leqslant 1. For the sets {ait+1,,ait+11}\left\{a_{i_{t}+1}, \ldots, a_{i_{t+1}-1}\right\} this follows from the fact that the corresponding segments lie between two neighboring empty dots, or between an endpoint of SS and its nearest empty dot. Therefore the sum of their lengths cannot exceed 11.

Solution 3. First put all numbers greater than 12\frac{1}{2} in their own groups. Then, form the remaining groups as follows: For each group, add new aia_{i}'s one at a time until their sum exceeds 12\frac{1}{2}. Since the last summand is at most 12\frac{1}{2}, this group has sum at most 11. Continue this procedure until we have used all the aia_{i}'s. Notice that the last group may have sum less than 12\frac{1}{2}. If the sum of the numbers in the last two groups is less than or equal to 11, we merge them into one group. In the end we are left with mm groups. If m=1m=1 we are done. Otherwise the first m2m-2 have sums greater than 12\frac{1}{2} and the last two have total sum greater than 11. Therefore n>(m2)/2+1n>(m-2)/2+1 so m2n1m \leqslant 2n-1 as desired.

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 and solution reproduced as published; topic and difficulty added by this site.