$\mathrm{n}$ and $\mathrm{r}$ are positive integers. Find the smallest $\mathrm{k}$ for which we can construct $\mathrm{r}$ subsets $\mathrm{A}_{1}, \mathrm{~A}_{2}$, $\ldots, A_{r}$ of $\{0,1,2, \ldots, n-1\}$ each with $k$ elements such that each integer $0 \leq m<n$ can be written as a sum of one element from each of the $r$ subsets.

## Answer

the smallest integer such that $\mathrm{k}^{\mathrm{r}} \geq \mathrm{n}$.
We can form at most $\mathrm{k}^{r}$ distinct sums, so $\mathrm{k}^{r}$ must be $\geq n$.

Now consider $\mathrm{A}_{1}=\{0,1,2, \ldots, \mathrm{k}-1\}, \mathrm{A}_{2}=\{0, \mathrm{k}, 2 \mathrm{k}, \ldots,(\mathrm{k}-1) \mathrm{k}\}, \mathrm{A}_{3}=\left\{0, \mathrm{k}^{2}, 2 \mathrm{k}^{2}, \ldots,(\mathrm{k}-1) \mathrm{k}^{2}\right\}, \ldots, \mathrm{A}_{\mathrm{r}}=\left\{0, \mathrm{k}^{\mathrm{r}-1}, 2 \mathrm{k}^{\mathrm{r}-1}, \ldots,(\mathrm{k}-1) \mathrm{k}^{\mathrm{r}-1}\right\}$. Then for any non-negative integer $\mathrm{m}<\mathrm{k}^{\mathrm{r}}$, we can write $\mathrm{m}$ with $\mathrm{r}$ digits in base $\mathrm{k}$ (using leading zeros as necessary) and hence as a sum of one element from each $A_{i}$. This subset works for $(k-1) k^{r-1}<n \leq k^{r}$. For smaller $n$ above $(k-1)^{r}$ we cannot use all the elements given above, but we do not need them, so we just replace the elements which are too large by arbitrary elements under n.

For example, suppose $\mathrm{n}=17, \mathrm{r}=4$. We need $\mathrm{k}=3$. So we form $\mathrm{A}_{1}=\{0,1,2\}, \mathrm{A}_{2}=\{0,3,6\}$, $\mathrm{A}_{3}=\{0,9,18\}, \mathrm{A}_{4}=\{0,27,54\}$. Now $18,27,54$ are unnecessary, so we pad out $\mathrm{A}_{3}$ and $\mathrm{A}_{4}$ with other elements. We could take $\mathrm{A}_{3}=\{0,1,9\}, \mathrm{A}_{4}=\{0,1,2\}$.