Let n be the unique integer such that 2n−1 ≤ k < 2n. Let S(n) be the set of numbers less than 10n that are written with only the digits {0, 1} in the decimal system. Evidently |S(n)| = 2n > k and hence there exist two numbers x, y ∈ S(n) such that k | x − y. Let us show that w = |x − y| is the desired number. By definition k | w. We also have w < 1.2 · 10n−1 ≤ 1.2 · (23√2)n−1 ≤ 1.2 · k3√k ≤ k4. Finally, since x, y ∈ S(n), it follows that w = |x−y| can be written using only the digits {0, 1, 8, 9}. This completes the proof.

ramakrishna wrote: Let n be the unique integer such that 2n−1 ≤ k < 2n. $ \cdots$ Why should $ k$ be odd? ramakrishna wrote: $ \cdots$ Evidently |S(n)| = 2n $ \cdots$ I don't understand this.

Take $m$ such that $2^{m-1}\le n<2^m$. There are $2^m>n$ numbers with $m$ digits or less and whose digits are all $0$ or $1$, so by the Pigeonhole Principle two of them must be equivalent $\mod n$. Hence, their difference is congruent to $0\mod n$, and is less or equal to \[\frac{10^m}{9}=16^{m-1}\left(\frac{10}{16}\right)^{m-1}\left(\frac{10}{9}\right)<16^{m-1}\le n^4\] for $m>1$. But the difference between any two numbers with digits $0$ and $1$ consists only of the digits $0$, $1$, $8$, and $9$.