
3. Let $X=\{0,1,2,3,4,5,6,7,8,9\}$. Let $S \subseteq X$ be such that any nonnegative integer $n$ can be written as $p+q$ where the nonnegative integers $p, q$ have all their digits in $S$. Find the smallest possible number of elements in $S$.


Solution: We show that 5 numbers will suffice. Take $S=\{0,1,3,4,6\}$. Observe the following splitting:

| $n$ | $a$ | $b$ |
| :--- | :--- | :--- |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 0 | 3 |
| 4 | 1 | 3 |
| 5 | 1 | 4 |
| 6 | 3 | 3 |
| 7 | 3 | 4 |
| 8 | 4 | 4 |
| 9 | 3 | 6 |

Thus each digit in a given nonnegative integer is split according to the above and can be written as a sum of two numbers each having digits in $S$.

We show that $|S|>4$. Suppose $|S| \leq 4$. We may take $|S|=4$ as adding extra numbers to $S$ does not alter our argument. Let $S=\{a, b, c, d\}$. Since the last digit can be any one of the numbers $0,1,2, \ldots, 9$, we must be able to write this as a sum of digits from $S$, modulo 10. Thus the collection

$$
A=\{x+y \quad(\bmod 10) \mid x, y \in S\}
$$

must contain $\{0,1,2, \ldots, 9\}$ as a subset. But $A$ has at most 10 elements $\left(\binom{4}{2}+4\right)$. Thus each element of the form $x+y(\bmod 10)$, as $x, y$ vary over $S$, must give different numbers from $\{0,1,2, \ldots, 9\}$.

Consider $a+a, b+b, c+c, d+d$ modulo 10. They must give 4 even numbers. Hence the remaining even number must be from the remaining 6 elements obtained by adding two distinct members of $S$. We may assume that even number is $a+b(\bmod 10)$. Then $a, b$ must have same parity. If any one of $c, d$ has same parity as that of $a$, then its sum with $a$ gives an even number, which is impossible. Hence $c, d$ must have same parity, in which case $c+d(\bmod 10)$ is even, which leads to a contradiction. We conclude that $|S| \geq 5$.
