I have a collection of typewritten pages that formed the basis of a third year problem solving course offered about 25 years ago at U. Waterloo. I've been slowly working through the problems and have come up with a solution to one of the questions but was wondering if anyone had a better solution.
The question is: Find the smallest natural number composed only of ones and zeros which is divisible by 225.
My solution: We are looking for a positive integer $k$ so that $N=225k$ has only ones and zeroes in the digits. Since any multiple of 5 has a 0 or 5 for the last digit, then k must be even. But $2\times 225=450$, so it really means that $k$ must be a multiple of 4. Now $N=900K$, where $4K=k$.
Let $100K=\sum_{i=0}^\infty a_i 10^i$, where (potentially) an infinite number of the $a_i$'s vanish.
The solution method is to look at each term $a_i$ starting with $a_0$ and choose the $a_i$ so that the ones digit of the product $9a_i + c_{i-1}$ is a one or zero, where $c_{i-1}$ is the carry from the previous product. This forms a tree, starting with $a_0$ at the root. The smallest $N$ is found from the smallest limb of the tree.
Each of the following congruences are $\mod 10$.
We choose $a_0$ so that $9a_0 \equiv 0$ or $9a_0 \equiv 1$. Only $a_0=9$ works here, so there is a carry of 8 when considering $a_1$. Then we have the congruences $9a_1+8\equiv 0$ or $9a_1+8\equiv 1$.
This gives two options to consider for $a_1$: either $a_1=8$ with a carry of 8 or $a_1=7$ with a carry of 7. The first just leads to a larger number for $N$, so we ignore it and move on to $a_2$. This has four options, but the only one we can use that has smallest $N$ is $a_2=6$ with a carry of 6.
Continuing in this way leads to $K=12345679$ and $k=4\times 12345679 = 49072716$, which means that $N=11111111100$. This was verified by a simple computer program I wrote that checked all of the smaller multiples.
Question for the group: For different numbers from 225, this leads to very dense and deep trees when solving for $a_i$. In fact, I had a originally solved this question using 255 instead of 225 because I misread it, which had a much denser tree because none of the branches could be eliminated at each step. Does anyone know of a cleaner/simpler solution?