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

Solución. Si tenemos subconjuntos $A_1,A_2,\ldots,A_r$ de $k$ elementos cada uno, entonces el número de sumas distintas $x_1+x_2+\ldots+x_r$ con $x_1\in A_1$, $x_2\in A_2$, ..., $x_r\in A_r$ será como máximo $k^r$, ya que podemos elegir de entre $k$ elementos para cada $x_i$, pero podría haber sumas repetidas. Por lo tanto, deducimos que si todos los enteros $x$ tales que $0\leq x\leq n-1$ se pueden expresar de esta forma, se tendrá que cumplir necesariamente que $k^r\geq n$ o, equivalentemente, $k\geq n^{1/r}$. Como $k$ tiene que ser un número entero, obtenemos que $k\geq\lceil n^{1/r}\rceil$. Si demostramos que se pueden construir los subconjuntos con $k=\lceil n^{1/r}\rceil$ elementos, este será el mínimo de $k$ que nos piden y habremos terminado.

Para $k=\lceil n^{1/r}\rceil$ construimos los $r$ subconjuntos \[A_m=\{a\,k^{m-1}:0\leq a\in\leq k-1\},\qquad\text{para } 1\leq m\leq r-1.\] Cada $A_m$ tiene $k$ elementos, exactamente los números que en base $k$ tienen $m$ cifras siendo las $m-1$ menos significativas todas cero (observemos que $0\in A_m$ para todo $m$). Todo número entre $0$ y $k^r-1$ se expresa de forma única como suma de un elemento de cada subconjunto (de $A_1$ tomamos el que tiene la cifra de sus unidades en base $k$, de $A_2$ el que tiene la cifra de sus decenas, y así sucesivamente). Ahora bien, el número máximo que puede expresarse de esta forma es $k^r-1=\lceil n^{1/r}\rceil^r-1\geq (n^{1/r})^r-1=n-1$, lo que concluye la demostración.