## The Vault: A gem from Russia

Here I present my first entry into the Vault, a collection of puzzles so well crafted, they provide the standard by which all other problems should be measured.

From the 1992 Tournament of the Towns:

Let n be a positive integer. Prove that there is a multiple of n, the sum of whose digits is odd.

__________

I am sure there are many ways of attacking this problem, but this was my approach. Do not be deceived by its apparent simplicity – this solution took me well over an hour to come up with.

Take your number n, and multiply it by an enormous power of ten, that is, stick a huge number of zeros at the end, much more than the number of digits of n. Now subtract n. What you are left with is still a very large number, but with a long string of 9s through the middle. Call this number A.

Now go back to the start. Take your number n, only this time multiply it by one more power of ten than you did last time, that is, stick one more zero at the end than you did before. Now subtract n. Again, you are still left with a very large number. Call this number B.

How are A and B related? They are both multiples of n and, like A, B also contains a long string of 9s through the middle. However, since we appended just a single extra zero, B contains precisely one more digit 9 than A. All the other digits in A and B are identical.

For example, if n = 253, we could attach 8 zeros to form 25,300,000,000, then subtract 253 to end up with A = 25,299,999,747. By adding an extra zero to form 253,000,000,000, we obtain B = 252,999,999,747. Notice that A and B are indeed identical, except that B contains an extra digit 9.

And now we are done: the digit sums of A and B differ by 9, so one out of A and B has an even digit sum, and the other, crucially, has an odd digit sum. Problem solved.

This truly is a masterpiece of mathematical composition. The problem statement fits on a single line, and can be understood by a primary school pupil, making it universally appealing. Yet, while the ideas used in its solution are not particularly complex, putting them together (at least for me) took an awfully long time. It is the sort of problem I aspire to invent.