## Task 1.

For a given natural number $n$, find the smallest natural number $k$ with the following property:

If $a_{1}, a_{2}, \ldots, a_{d}$ are real numbers, $0 \leqslant a_{i} \leqslant 1, a_{1}+a_{2}+\cdots+a_{d}=n$, then it is possible to distribute these $d$ numbers into $k$ groups such that the sum of the numbers in each group is at most 1 (some groups may be empty).
## Solution.

The solution is $k=2n-1$.

If $d=2n-1$ and $a_{1}=\cdots=a_{2n-1}=\frac{n}{2n-1}$, then each group of the partition can contain at most one number because $\frac{2n}{2n-1}>1$. Therefore, $k \geqslant 2n-1$. It remains to show that there is always a corresponding partition into $2n-1$ groups.

We prove this by induction on $d$. For $d \leqslant 2n-1$, the claim is obvious. If $d \geqslant 2n$, then because

$$
\left(a_{1}+a_{2}\right)+\cdots+\left(a_{2n-1}+a_{2n}\right) \leqslant n
$$

there exist two numbers $a_{i}, a_{i+1}$ such that $a_{i}+a_{i+1} \leqslant 1$. "Combine" these two numbers into a new number $a_{i}+a_{i+1}$. By the induction hypothesis, the corresponding partition exists for $d-1$ numbers $a_{1}, \ldots, a_{i-1}, a_{i}+a_{i+1}, a_{i+2}, \ldots, a_{d}$. This induces a corresponding partition for $a_{1}, \ldots, a_{d}$.