
10.4. A positive integer is called simple if its ordinary decimal representation consists entirely of zeroes and ones. Find the least positive integer $k$ such that each positive integer $n$ can be written as $n=a_{1} \pm a_{2} \pm a_{3} \pm \cdots \pm a_{k}$, where $a_{1}, \ldots, a_{k}$ are simple.


Solution. We can always write $n=a_{l}+a_{2}+\cdots+a_{9}$ where $a_{j}$ has 1 's in the places where $n$ has digits greater or equal to $j$ and 0 's in the other places. So $k \leq 9$. To show that $k \geq 9$, consider $n=10203040506070809$. Suppose $n=a_{l}+a_{2}+\cdots+a_{j}-a_{j+l}-a_{j+2}-\cdots-a_{k}$, where $a_{l}, \ldots, a_{k}$ are simple, and $k<9$. Then all digits of $b_{l}=a_{l}+\cdots+a_{j}$ are not greater than $j$ and all digits of $b_{2}=a_{j+l}+\cdots+a_{k}$ are not greater than $k-j$. We have $n+b_{2}=b_{l}$. We perform column addition of $n$ and $b_{2}$ and consider digit $j+1$ in the number $n$. There will be no carry digit coming from lower decimal places, since the sum there is less that $10 \ldots 0+88 \ldots 8=98 \ldots 8$. So in the column of $j+1$ we get the sum of $j+1$ and the corresponding digit in $b_{2}$. The resulting digit should be less than $j+1$. Thus in the corresponding place in $b_{2}$ we have at least $9-j$. But $9-j \leq k-j$, implying $k \geq 9$. Hence, we have proved that the maximal $k$ is 9 .
