Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Supondremos sin pérdida de generalidad que $a_1\lt a_2\lt\ldots\lt a_n$. Tenemos $n$ sumas distintas de subconjuntos de un elemento, que van en orden creciente de $a_1$ hasta $a_n$. Podemos producir $n-1$ sumas mayores, también en orden creciente $a_n+a_1,a_n+a_2,\ldots,a_n+a_{n-1}$. Podemos añadir $n-2$ sumas mayores $a_n+a_{n-1}+a_1,a_n+a_{n-1}+a_2,\ldots,a_n+a_{n-1}+a_{n-2}$ y así sucesivamente hasta llegar a la suma $a_1+a_2+\ldots+a_n$, lo que garantiza que todas estas sumas son distintas. Tenemos un total de $1+2+\ldots+n=\frac{n(n+1)}{2}$ sumas distintas.

Nota. La cota es óptima ya que si tomamos $S=\{1,2,3,\ldots,n\}$, las sumas de subconjuntos de los elementos de subconjuntos de $S$ recorren precisamente todos los enteros desde $1$ hasta $1+2+\ldots+n=\frac{n(n+1)}{2}$.