Bulgarian Mathematical Competitions

Solution:
We shall prove the assertion by induction on $N = a_{1} + a_{2} + \cdots + a_{m}$. For $N = 1$ we have $m = 1$, $a_{1} = 1$ and $b_{1} = 1$ is the required number.

Let us assume that the assertion is true for every collection with sum less than $N$ and let $a_{1}, a_{2}, \ldots, a_{m}$ be such that $a_{1} + a_{2} + \cdots + a_{m} = N$.

If all numbers $a_{1}, a_{2}, \ldots, a_{m}$ are even then the numbers $\frac{a_{1}}{2}, \frac{a_{2}}{2}, \ldots, \frac{a_{m}}{2}$ have sum $\frac{N}{2}$ and by the induction hypothesis there exists a collection $b_{1}, b_{2}, \ldots, b_{n}$ which satisfies the condition. Then the required numbers for $a_{1}, a_{2}, \ldots, a_{m}$ are $2 b_{1}, 2 b_{2}, \ldots, 2 b_{n}$.

Suppose now that at least one of the numbers $a_{1}, a_{2}, \ldots, a_{m}$ is odd. Without loss of generality we can assume that $a_{m}$ is the smallest odd number in the collection. Let us consider the numbers $a_{1}', a_{2}', \ldots, a_{m-1}'$ defined by
$$a_{i}' = \begin{cases} \frac{a_{i}}{2} & , \text{ if } a_{i} \text{ is even } \\ \frac{a_{i} - a_{m}}{2} & , \text{ if } a_{i} \text{ is odd } \end{cases}$$
The sum of the new numbers $a_{i}'$ is less than $N$ and the induction hypothesis implies the existence of numbers $b_{1}', b_{2}', \ldots, b_{k}'$ which satisfy the conditions. We shall prove that the numbers $2 b_{1}', 2 b_{2}', \ldots, 2 b_{k}', a_{m}$ are the required numbers for the collection $a_{1}, a_{2}, \ldots, a_{m}$.

If two nonintersecting subsets of $\{2 b_{1}', 2 b_{2}', \ldots, 2 b_{k}', a_{m}\}$ have equal sums then $a_{m}$ (as the only odd number) does not belong to these sets. Dividing by $2$ we obtain two nonintersecting subsets of $\{b_{1}', b_{2}', \ldots, b_{k}'\}$ with equal sums which is a contradiction. Also, it is easy to see that every $a_{i}$, $i = 1, 2, \ldots, m$ can be represented as a sum of some of the numbers $2 b_{1}', 2 b_{2}', \ldots, 2 b_{k}', a_{m}$ which completes the induction step.