International Mathematical Olympiad Shortlisted Problems

Answer. $k=2n-1$.

Solution 1. If $d=2n-1$ and $a_1=\cdots =a_{2n-1}=n/(2n-1)$, then each group in such a partition can contain at most one number, since $2n/(2n-1)>1$. Therefore $k⩾2n-1$. It remains to show that a suitable partition into $2n-1$ groups always exists. We proceed by induction on $d$. For $d⩽2n-1$ the result is trivial. If $d⩾2n$, then since $$\left(a_1+a_2\right)+\dots +\left(a_{2n-1}+a_{2n}\right)⩽n$$ we may find two numbers $a_i$, $a_{i+1}$ such that $a_i+a_{i+1}⩽1$. We "merge" these two numbers into one new number $a_i+a_{i+1}$. By the induction hypothesis, a suitable partition exists for the $d-1$ numbers $a_1,\dots ,a_{i-1},a_i+a_{i+1},a_{i+2},\dots ,a_d$. This induces a suitable partition for $a_1,\dots ,a_d$.

Solution 2. We will show that it is even possible to split the sequence $a_1,\dots ,a_d$ into $2n-1$ contiguous groups so that the sum of the numbers in each group does not exceed $1$. Consider a segment $S$ of length $n$, and partition it into segments $S_1,\dots ,S_d$ of lengths $a_1,\dots ,a_d$, respectively, as shown below. Consider a second partition of $S$ into $n$ equal parts by $n-1$ "empty dots". Assume that the $n-1$ empty dots are in segments $S_{i_1},\dots ,S_{i_{n-1}}$. (If a dot is on the boundary of two segments, we choose the right segment). These $n-1$ segments are distinct because they have length at most $1$. Consider the partition: $$\left\{a_1,\dots ,a_{i_1-1}\right\},\left\{a_{i_1}\right\},\left\{a_{i_1+1},\dots ,a_{i_2-1}\right\},\left\{a_{i_2}\right\},\dots ,\left\{a_{i_{n-1}}\right\},\left\{a_{i_{n-1}+1},\dots ,a_d\right\}.$$ In the example above, this partition is $\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 $1$. For the sets $\left\{a_{i_t}\right\}$ this is obvious since $a_{i_t}⩽1$. For the sets $\left\{a_{i_t+1},\dots ,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 $S$ and its nearest empty dot. Therefore the sum of their lengths cannot exceed $1$.

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