Happy new year! I’m reading Peter Winklers “Mathematical Puzzles: a Connoisseur’s Collection” and found this nice problem:
Prove that all natural numbers have a nonzero multiple whose base-10 representation consists only of zeros and ones
Here’s the very elegant proof:
Show solution
Given a natural number $n$, consider $\{111, 1111, 11111, \dots\}$, a set of 'all-ones' numbers which begins with the first all-ones number greater than $n$ and contains $n+1$ elements, with each successive element adding a 1. Since there are only $n$ integers (modulo $n$) and the set has $n+1$ elements, it follows that at least two elements of the set must be congruent modulo $n$. If you subtract one from the other, you'll get a number congruent to zero modulo $n$ (a multiple of $n$) which begins with a string of ones and ends with a string of zeros.I really enjoyed this one - it’s not terribly often that you see the pigeonhole principle come up in number theory. The problem is hard to solve any other way, but the trick in the solution makes it trivial. I’d highly recommend the book to anyone looking to do a little bit of math for fun!