Form all numbers from limited digits Let $M$ be a subset of the digits $\{0,1,\ldots,9\}$, and $N$ the set of numbers formed with digits in $M$. 
Suppose that all numbers from $1 $ to $99999999$ either belong to $N$ or can be written as a sum of two numbers in $N$. What is the minimum size of $M$?
If $M$ contains $0,1,3,4,5$, then it already suffices because $2=1+1,6=3+3,7=4+3,8=4+4,9=5+4$, so every digit can be formed. 
 A: $M$ must contain five elements.  If it were four and included zero, you can't get all the single digits.  You must have $1$ and either $2$ or $3$.  Adding one more digit will miss one of $7,8,9$.  If it does not contain zero, the only sets that get all the single digits are $\{1,2,3,6\}, \{1,2,3,7\},  \{1,2,4,7\}, \{1,2,5,7\}, \{1,2,5,8\}$ and $\{1,3,4,5\}$.  None can represent $911$ as $9$ is not included so you must have two numbers in the sum.  Only $\{1,2,4,7\}$ can get a $1$ in the units place, but it cannot get the $1$ in the tens because of the carry from $4+7$ in the units place.
A: Obviously Ross' answer is better, but since I'd already written the code and it might be of some residual interest to know which set of digits does best in representing the most numbers, here are the results of a brute-force enumeration.
No set of four digits allows all numbers to be represented. The set that can represent the most is $\{1,2,4,5\}$, with $ 52714756$ numbers. The runners-up are $\{2,3,5,6\}$ with $48006520$ numbers and $\{0,1,3,4\}$ with $43046720$ numbers. Note the pattern $\{d-2,d-1,d+1,d+2\}$. Here's the code.
