One may perform the following two operations on a positive integer:
(a) multiply it by any positive integer; or
(b) delete zeros in its decimal representation.
Prove that for every positive integer , one can perform a sequence of these operations that will transform to a one-digit number.
Solution
By the pigeonhole principle, two of the numbers leave the same remainder when divided by . Their difference, which is of the form , is divisible by . Therefore, we can transform to , and then to by deleting the zeros.
If the current number is , we are done. Otherwise, we have
So we can transform to , and then to . Next, note that
So we can transform the number to , and then to . Afterwards, we apply the operations as follows.
This completes the proof.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.