Answer: $k=2n-1$. To see that at least $2n-1$ groups may be necessary, simply consider $a_1 = a_2 = \dots = a_{2n-1} = \frac{n}{2n-1}$. To see $2n-1$ groups is sufficient, consider a minimal partitions into groups with sums $g_1 \le g_2 \le \dots \le g_m$. That implies that $g_i+g_j > 1$ for any distinct $i$, $j$. Moreover, $g_1 + \dots + g_m = n$. Then \[ 2n = (g_1+g_2) + (g_2+g_3) + \dots + (g_m+g_1) > 1+1+\dots+1 = m \] as required.

easy and simple.

lyukhson wrote: Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$. We can generalize this. If for some $d$ real numbers $a_i$ which sum up to $x$, the smallest value of such $k$ is $\lceil2x\rceil-1$. If $a_i>\dfrac 12$, then it forms a group itself. Now, for other $a_i$'s, we keep adding, and when we have the sum greater than $\dfrac 12$, we stop. Now, there is a catch, the last group may have a sum less than $\dfrac 12$ in this way, so we can merge the two if we see their sum is less than or equal to $1$. After the whole process, if we are left with just one group, we have nothing to do. If not, let's say the number of leftwith groups is $y$. Without loss of generality, we can say that, the last two have sum greater than $1$ and the first $y-2$ groups have sums greater than $\dfrac x2$ each. Thus, $x>\dfrac{y-2}2+1\implies y\leq\lceil2x\rceil-1$. More generalization: How about we consider the sum of each group is at most $c$?

Can't this be applied to IMO 2014 #5?

Yes, it can't. In the case of IMO 2014 #5 the numbers are special - namely egyptian fractions; so the considerations of the above do not apply.

The answer is $2n-1$.This can be proven by induction.Base case $n=1$ and $n=2$ is trivial.Suposse that it holds for $ n $.Now let's prove it for $n+1$.Let: $a_1+a_2+ \cdots +a_d=n+1$.It is trivial that there exist numbers such that their sum is greater than or equal to $1$ and less than $2$, so we put them into 2 groups(this can be proven with a greedy algorithm) and now we have numbers whose sum is less or equal to $n$ so we just divide them into 2n-1 groups.That is $2n+1=2(n+1)-1$ groups so the task is proven.

SmartClown i don't get your argument, what if we have numbers whose sum is between 1,2 to be 0.55,0.55,0.55,0.1 We cannot put these in 2 groups

The greedy algortihm goes like this: We sort the numbers from the biggest to the smallest. Now we take the biggest and put it in one group. If it is greater than $\frac{1}{2}$ we move on to the next group.If it isn't then we continue putting biggest remaining numbers in the group until the sum gets between $0,5$ and $1$ which will surely happen so we will get two groups whose sum is greater than $\frac{1}{2}$ which is what we wanted.

The answer is $2n-1$. First we prove that we need at least $2n-1$ groups, which happens when we consider the case where every $a_i=\frac{n}{2n-1}$. Now we prove by induction that $2n-1$ groups is sufficient for any partition of $a_i$'s. The base case, $n=1$, is easy. Now suppose that for $n=k$ we can use $2k-1$ groups. Let us look at the case of $n=k+1$. Now order the $a_i$'s from smallest to largest. Call the new ordering $b_1, b_2, b_3, ..., b_d$. We start with a sum $c_0=0$. If $c_j<1$, then we define $c_{j+1}=c_j+b_{j+1}$. If $c_j\geq1$, then we stop. Let $c_m$ be the final sum. It is easy to see that $c_m<2$. By our definition, $c_{m-1}<1$, so $b_1, b_2, ... b_{m-1}$ can go in one group. We also know that $b_m\leq1$, so $b_m$ can go in another group. We have 2 total groups so far. Now let us look at $b_{m+1}, b_{m+2}, ..., b_d$. Since $2>c_m\geq1$, we know that $k-1<b_{m+1}+b_{m+2}+...+b_d\leq{k}$. Let us add a "placeholder" number $b_{d+1}$ such that $b_{m+1}+b_{m+2}+...+b_d+b_{d+1}=k$. Since $k-1<b_{m+1}+b_{m+2}+...+b_d\leq{k}$, we know that $0\leq{b_{d+1}}<1$, so we know have a set of numbers between $0$ and $1$ of $b_{m+1}, b_{m+2},...,b_d, b_{d+1}$ that add up to $k$. By our inductive hypothesis, we need at most $2k-1$ groups such that the sum of the numbers in each group is at most $1$. Now we take the 2 groups we made before of $c_{m-1}$ and $b_m$ along with our partition of the numbers $b_{m+1}, b_{m+2},...,b_d, b_{d+1}$ into $2k-1$ groups, remove $b_{d+1}$ from its group, and we have a valid partition of the numbers $b_1, b_2, b_3, ..., b_d=a_1, a_2, ..., a_d$ into $2k-1+2=2k+2-1=2(k+1)-1$ groups, and our induction is complete.

v_Enhance wrote: Answer: $k=2n-1$. To see that at least $2n-1$ groups may be necessary, simply consider $a_1 = a_2 = \dots = a_{2n-1} = \frac{n}{2n-1}$. To see $2n-1$ groups is sufficient, consider a minimal partitions into groups with sums $g_1 \le g_2 \le \dots \le g_m$. That implies that $g_i+g_j > 1$ for any distinct $i$, $j$. Moreover, $g_1 + \dots + g_m = n$. Then \[ 2n = (g_1+g_2) + (g_2+g_3) + \dots + (g_m+g_1) > 1+1+\dots+1 = m \]as required. Why considering such a minimum partition will give $g_i+g_j > 1$ for all $i,j$.

Take any partition of groups, and if there are any two groups both with sum $\le 0.5$, merge them. Now, Suppose we have $x$ groups with sum $> 0.5$ and at most $1$ group with size $\le 0.5$. Observe that $x/2 < n$, so there are at most $2n - 1$ sets with sum $> 0.5$. Suppose they each exceed $0.5$ by $\varepsilon_i$, then our last set has sum $1/2 - \sum_{i = 1} ^ {2n - 1} \varepsilon_i$. In particular, you can group this with any of the other $2n - 1$ sets to get a set with sum at most $1$. Hence, $2n - 1$ is sufficient. To show it's necessary, just take $2n - 1$ of the $a_i = 0.5 + \varepsilon$ and the last one be $0.5 - (2n - 1) \varepsilon$.

The answer $\boxed{2n-1}$. To see that we do need these many groups, consider $a_i=\frac{n}{2n-1}$ and $d=2n-1$ for all $1\le i\le d$. Suppose the $a_i$ are given. There exists some splitting, namely letting each $a_i$ be in its own group. Now, consider the splitting with least number of parts. Suppose the sum of each of its parts are $b_1,\ldots,b_r$ where $r$ is the number of parts. Since this is the smallest splitting, combining parts must make the sum go over $1$, so $b_i+b_j>1$ for all $1\le i<j<r$. Summing over all such pairs $i,j$, we see that \[(r-1)(b_1+\cdots+b_r)>\binom{r}{2},\]so $(r-1)n>r(r-1)/2$, so $r<2n$. Thus, the splitting with the least number of parts has at most $2n-1$ parts, as desired. $\blacksquare$

Nice and easy. Here's my solution: We claim that the minimum possible value of $k$ is $2n-1$. To see that $k \geq 2n-1$, take $d=2n-1$ and $a_i=\frac{n}{2n-1} \text{ } \forall i \in \{1,2, \dots ,d\}$. Now, we show that this value of $k$ can always be achieved. This is obvious for $d \leq 2n-1$ (Take each of the $a_i$'s as a group). So from now on we consider only $d \geq 2n$. Our solution will rely upon the following Lemma- LEMMA Suppose $n \in \mathbb{N}$ and $d \geq 2n$ be a positive integer. Given $d$ real numbers $a_1,a_2, \dots ,a_d \in [0,1]$ satisfying $a_1+a_2+ \dots +a_d=n$, we must have $a_i+a_j \leq 1$ for some $i \neq j$. Proof of Lemma- The Lemma is quite trivial tbh. Assume to the contrary that $a_i+a_j>1$ for every $i \neq j$. Adding up these inequalities for all possible pairs, we have $$(d-1) \left(\sum_{i=1}^d a_i \right)>\binom{d}{2} \Rightarrow (d-1)n>\frac{d(d-1)}{2} \Rightarrow d<2n$$which contradicts the fact that $d \geq 2n$. Thus, our Lemma is true. $\Box$ Return to the problem at hand. We induct on $d \geq 2n$. The base case $d=2n$ follows easily from our Lemma (Take $(a_1,a_j)$ with $a_i+a_j \leq 1$ as one group, and put each of the other $a_i$'s into the remaining $2n-2$ groups). Assume that the result is true for $d=2n+m-1$. In the case of $d=2n+m$, form a new element $A=a_i+a_j$ where $a_i+a_j \leq 1$ is chosen as in our Lemma. Then we can apply our inductive hypothesis on $A$ along with the remaining real numbers to get the required $2n-1$ partitions. Hence, done. $\blacksquare$ REMARK: I realised after doing the problem by the inductive approach in my solution, that the problem can be done without mentioning induction also, as we didn't really benefit from the inductive hypothesis. In that case, we'd get a solution quite similar to the one given above. Nevertheless, I am including my solution as I found it a quite interesting approach to induct on $d$ instead of $n$ (which some of the users have done previously).

Cute problem! lyukhson wrote: Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$. We will show that the minimum is $k=2n-1.$ To see that this is the minimum, consider the case when $a_i=\tfrac{n}{2n-1}$ for all $i.$ We will now show that this value of $k$ is the optimal for any minimal partition. Let $s_1, s_2, \cdots s_k$ be a minimal partition of $a_i.$ Then $s_i<1$ and by minimality, $s_i+s_j>1$ for all $i \ne j.$ Thus $$n=(s_1+s_2)+(s_3+s_4)+\cdots+(s_{k-1}+s_k) > \frac{k}{2} \implies 2n>k \quad \text{(if k is even)}$$$$n=(s_1+s_2)+(s_3+s_4)+\cdots+(s_{k-2}+s_{k-1})+s_k > \frac{k-1}{2}+s_k \implies 2n>k-1+2s_k \implies 2n \ge k+2s_k >k \quad \text{(if k is odd)}$$Hence, we are done. $\square$

Answer is $k=2n-1$. For a construction, just take each group to consist of $\tfrac{n}{2n-1} \le 1$. Now we will show that $k \ge 2n-1$ is necessary. The key is to take an optimal partition, you cannot group together two or more groups to form another one. Thus, if $S_1, \dots, S_k$ are the sums of the numbers in the group (written in increasing order), we have $S_i+S_j>1$ for any distinct $i$ and $j$. Summing this inequality globally returns \[ 2\binom{k}{2} < n(2k-2), \]or \[ k > 2n, \]as desired. Remark: Always try the local idea of ``making collections of blocks compact", so that the optimal number of blocks is used. This is extremely useful in the so-called ``weighted blocks problems".

We claim the answer is $\boxed{2n-1}$, with contruction $a_i= \frac{n}{2n-1}$, for $1 \le i, \le 2n-1$, since it is impossible to combine since $a_j+a_k >1$ for all $1 \le j, k \le 2n-1$. To prove this is maximal, if we combine $a_i$s that are less than $.5$ we will eventually have all $a_i$s greater than $.5$, or have one that is less than $.5$ call it $a_x$, and the rest greater than $1-a_x$. In the first case, we must have an amount of $a_i$s less than $2n$ or less than or equal to $2n-1$ and we are finished for this case. In the second case we have at most $\frac{n}{1-a_x}+1$ terms total however notice that for $a_x$ to not be able to "complete" any other term then $ 1- a_x > \frac{n}{2n-1}$ or $2n > \frac{n}{1-a_x}+1$ so we are able to finish in this case. $\square$

The answer is $\boxed{2n-1}$. Construction simply take $2n-1$ copies of $\frac{n}{2n-1}$. No two can be in the same box else the sum is over 1. so at least $2n-1$ boxes required. Proof of minimality: Say some set required over $2n-1$ boxes.clearly each box has to have sum over $\frac{1}{2}$ else 2 boxes can be merged. but this way the sum is more than $\frac{1}{2} \cdot 2n = n$. contradiction. So we are done.

I claim the answer is $2n - 1$. Bound: Take $a_i = \frac 12 + \frac{1}{4(2n - 1)} $ for $1 \le i \le 2n - 1$, $a_{2n} = \frac 14$. None of the first $2n - 1$ elements of $a$ can be in the same group, so we are done. Construction: Assume we have $k > 2n - 1$ groups as the minimum. Then we can always separate each of the groups into $n$ sets, with each set containing at least $2$ groups. One of these sets must have sum of groups at most $1$, so we can just combine those groups to get a smaller answer, contradiction.

I claim that the answer is $2n-1$. First, I will prove that we need at least $2n-1$. This can be done by considering the $d=2n-1$, with $a_1=a_2=\dots=a_d=\frac{n}{2n-1}$. Note that no two of these $a_i$'s can go together in a single group, since $\frac{2n}{2n-1}>1$. Therefore they must each go in there own group, which requires at least $2n-1$ groups, as desired. I now will prove that $2n-1$ groups always suffices. First, consider our $d$ real numbers as line segments of length $a_i$ each, and consider the number line spanning from $0$ to $2n-1$. Our problem is then equivalent to placing these $d$ segments on this number line so that a) no two line segments overlap and b) no line segment can intersect an integer point except at an endpoint (i.e., if our line segment has length $a_i$, if we place it so that its leftmost point is $x$, then there can be no integer between $x$ and $x+a_i$, NON-inclusive). These two problems are equivalent because if we can do the latter, then we can take the groups of $a_i$'s corresponding to the line segments in each of the $2n-1$ of our $[k,k+1]$ intervals (integer $k$) and consider them as our $2n-1$ groups. Now, we can always do this as follows. First, without regard for our second condition, since $\sum a_i=n$, we can pack the $d$ line segments from $0$ to $n$. Then, there will be some "overflow," or line segments that intersect integer points at non-endpoint places. Note that there are at most $n-1$ of these segments, one for each of the integers $1$, $2$, $\dots$, $n-1$ (but not $0$ or $n$, because they are endpoints of line segments). Then, note that we still have the $n-1$ intervals $[n,n+1]$, $[n+1,n+2]$, $\dots$, $[2n-2,2n-1]$ left completely empty. We can take these $\leq n-1$ "overflow" segments and move them so that each one is in its own one of these $n-1$ "remaining" empty intervals. This makes it so that no two line segments overlap, and none of our $d$ line segments intersect an integer point other than an endpoint, as desired. Therefore we can always split our $d$ numbers into $2n-1$ groups so that the sum of the numbers in each group is $\leq 1$, finishing the problem. This problem is similar to this problem (China 1990): In an arena, each row has $199$ seats. One day, $1990$ students are coming to attend a soccer match. It is only known that at most $39$ students are from the same school. If students from the same school must sit in the same row, determine the minimum number of rows that must be reserved for these students.

We claim that the smallest integer is $k=2n-1$. To see why $k\ge 2n-1$, consider $a_1=\dots = a_{2n-1}=0.5+\epsilon$ and $a_{2n}=n-(2n-1)a_1$ for sufficiently small $\epsilon$.Then, no two of the $a_i$ for $1\le i \le 2n-1$ terms can be in the same group, implying that we need atleast $2n-1$ groups. We now show that it is always possible to partition these numbers into $2n-1$ groups as desired. We simply order the numbers $a_1\ge a_2 \ge \dots \ge a_d$ in decreasing order, and groups $G_1 , G_2, \dots , G_{2n-1} $and choose the largest unplaced number and place in the smallest index group which has space for it. Say this algorithm eventually fails. Say we successfully placed $a_1, \dots, a_{r-1}$ into groups and we have no space for $a_r$ (note $r \ge 2n$). Then, let $S_i$ denote the sum of the numbers already placed in group $G_i$. Then, for all $1\le i \le 2n-1$, $1-S_i < a_r$. Summing these equations gives, \[(2n-1)a_r > 2n-1-(a_1+\dots + a_{r-1}) \ge 2n-1 (n-a_r)\]which upon rearrangement implies $a_r > \frac{1}{2}$. But then, \[a_1+a_2+\dots + a_r > \frac{r}{2} \ge \frac{2n}{2} = n\]which is a clear contradiction.

We claim our answer is $k = \boxed{2n-1}$, which is constructable with $a_1 = \ldots = a_{2n-1} = \frac{n}{2n-1}$ and noticing the sum of any two or more is $\ge \frac{2n}{2n-1} > 1$, so they must all be a lone group. If $d \leq 2n-1$, clearly we have $d \leq k$ groups. Otherwise, we can always fuse two numbers $a_i$ and $a_j$ to get a sum of less than 1 by averaging principle. Thus we can induct down to $d = 2n-1$ numbers at most 1, from which we let each individual term be a lone group. $\blacksquare$

100th post

For $n=1$, just group up the terms into $1$ group with sum $1$. For $n \ge 2$ consider $$a_1= a_2 = \cdots = a_{2n-1} = \frac{n}{2n-1}$$Since combining any two of these two terms gives us a sum $>1$ we know that $k \ge 2n-1$. Now suppose that we have $\ge 2n$ terms. The average sum of two terms chosen at random is at most $\frac{2n}{2n}=1$ so by the averaging principal we can combine two terms into a group with sum $\le 1$. We can keep repeating this process until we have $2n-1$ terms. So our answer is $\boxed{2n-1}$.

The answer is $k = 2n - 1.$ Necessity: Take the real numbers $\frac{n}{2n-1}, \frac{n}{2n-1}, \dots, \frac{n}{2n-1}$ with $2n-1$ elements on this list. If $k < 2n-1,$ two numbers must go in the same group, making the sum $\frac{n}{2n-1} + \frac{n}{2n-1} > 1.$ Sufficiency: The construction is clear for $d \le 2n-1$ (just put each number into its own group, and make the spare groups empty). For $d \ge 2n-1,$ we will induct on $d,$ with the base case $d = 2n-1$ described above. Reorder the list as $a_1 \le a_2 \le \dots \le a_d.$ Now, the trick is that $a_1 + a_2 \le 1.$ Suppose otherwise; then $a_1 + a_2 > 1,$ and similarly $a_{2i-1} + a_{2i} > 1$ for all $1 \le i \le n$ since $d \ge 2n.$ Summing these inequalities up gives $a_1 + \dots + a_{2i} > n,$ which is a contradiction. Therefore, $a_1 + a_2 \le 1,$ so we can create a new list $a_1 + a_2, a_3, a_4, \dots, a_d$ with $d-1$ elements satisfying that each element is between $0$ and $1,$ inclusive. Applying our inductive hypothesis, we conclude our proof of sufficiency. Thus our answer is $k = 2n-1,$ as claimed.

Let the sums be $s_1,s_2,.....,s_t$. Then $s_i+s_{i+1}>1$ for $i=1,2,....,t$ and $s_{t+1}=s_1$. Now summing cyclically gives us that $2n>t$ or $2n-1 \geq t$. If $t=2n-1$ then for construction purposes take $s_i=s_j$ for all $i,j$ in $\{ 1,2,.....,t \}$ giving us that all of them are equal to $\frac{n}{2n-1}$ which is a valid construction.

The answer is $\boxed{k=2n-1}$. Note that $2n-1$ is needed by setting $a_1=a_2=\dots=a_{2n-1}=\frac{n}{2n-1}$. No group can have more than one elements, so we need a group for every element which implies the conclusion. To see that $2n-1$ is sufficient, we induct on $d$. Notably when $d \leq 2n-1$ the answer is in the process described above, so our base cases are concluded. Assume it is true for some $d_0 \geq 2n-1$. Now we have $a_1+a_2+\dots+a_{d_0+1} = n$. The key claim is that there exists some pair of $a_i, a_j$ such that their sum is at most $1$. Assume the contrary for the sake of contradiction, then doing a global sum gives us that $\sum a_i > \frac{\binom{d_0+1}{2}}{d_0} = \frac{d_0+1}{2} \geq n$, which is impossible. Therefore we can reduce this to the $d_0$ case which is covered by our inductive hypothesis, so we are done.

Claim 1: If $k \leq 2n - 2$, it can't work. For this part, we simply provide a construction. Consider $y = 0.50000....1$, such that $(2n - 1)y < n < 2n \cdot y$. Now consider the real numbers $a_1 = y, a_2 = y, \dots, a_{2n - 1} = y, a_{2n} = n - (2n - 1)y$. Note that $n - (2n - 1)y < n - (2n - 1)\cdot 0.5 = 0.5$, so we can pair $a_{2n}$, with at maximum one number, let this be $a_{2n - 1}$. However, for $a_1, \dots, a_{2n - 2}$, we cannot have any two $a_{i}, a_{j}$ in one subset since $a_{i} + a_{j} > 1$. So, each number will take up one subset and therefore, $\geq 2n - 2 + 1 = 2n - 1$ subsets are required. Claim 2: $k = 2n - 1$ works: Say, $k = m > 2m - 1$ works. Let the sum of set $1$ be $s_1$, sum of set $2$ be $s_2$, and so on. For the sake of contradiction, $s_i + s_j > 1$, for all $i, j$. Then, $(s_1 + s_2) + (s_1 + s_3) + \dots + (s_1 + s_m) + (s_2 + s_3) + \dots (s_{m - 1} + s_m) > \binom{m}{2} = \frac{m(m - 1)}{2}$. However, note that this sum is also equal to $(m - 1)(s_1 + s_2 + ... + s_m) = n(m - 1)$. So, $n(m - 1) > \frac{m(m - 1)}{2} \implies 2n > m$, a contradiction. Therefore, WLOG, let $s_1 + s_2 \leq 1$, and we can merge these two sets. We can keep merging sets until we eventually hit $k = 2n - 1$, as required, so done.

We claim the answer is $2n-1$ Why $2n-1$ is minimum :- Consider the fractions $2n-1$ terms that are $\frac{n}{2n-1}$ each which sum to $n$ note that they can't be in a single group because then the sum will be greater than $1$. Hence there must be at least $2n-1$ different groups Why $2n-1$ always works:- Assume there are greater than $2n-1$ groups, note that pairwise their sum should be greater than $1$ else just we could merge two groups up till it satisfies the pairwise greater than $1$ property, If there's less than $2n-1$ groups then we are done, else add everything cyclically to get n = $s_1 + s_2 + .... +s_{2n-1} + s_{2n} +.....$ $>$ $\frac{2n}{2}$ $= n$ Which is a contradiction and so we are done.

We claim that the answer is $k=2n-1.$ For the construction, notice that letting $$a_1=a_2=\cdots = a_{2n-1} = \frac{2n+1}{4n},$$then $a_{2n}=\frac{1}{4n}.$ Then clearly we require at least $2n-1$ groups. Now, for the bound, we proceed with induction on $d.$ The base cases, $1 \leq d \leq 2n-1,$ are all trivial. Now assume that the proposition holds for $d=k \geq 2n-1.$ Note that if there does not exist $a_i, a_j$ such that $a_i+a_j \leq 1,$ it follows that $a_i+a_j > 1$ for all $i, j.$ Then summing this up yields $$\binom{k-1}{1} \sum 2a_i \geq \binom{k}{2} \implies n > k \geq 2n-1,$$a contradiction. Thus there exists $a_i, a_j$ with a sum less than or equal to $1,$ and by the inductive hypothesis we are done. QED