Maths Olympiad Prep

Library / /64 of 136

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

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 XX, one can perform a sequence of these operations that will transform XX to a one-digit number.

Solution

By the pigeonhole principle, two of the numbers 1,11,111,1, 11, 111, \dots leave the same remainder when divided by XX. Their difference, which is of the form 11100011\cdots100\cdots0, is divisible by XX. Therefore, we can transform XX to 11100011\cdots100\cdots0, and then to 11111\cdots1 by deleting the zeros.

If the current number is 11, we are done. Otherwise, we have
111k times×82=9111(k2) times02. \underbrace{11\cdots1}_{k \text{ times}} \times 82 = \underbrace{911\cdots1}_{(k-2) \text{ times}} 02.
So we can transform 11111\cdots1 to 911102911\cdots102, and then to 91112911\cdots12. Next, note that
9111m times2×9=82000m times8. \underbrace{911\cdots1}_{m \text{ times}} 2 \times 9 = \underbrace{8200\cdots0}_{m \text{ times}} 8.
So we can transform the number to 8200088200\cdots08, and then to 828828. Afterwards, we apply the operations as follows.
828×252070027×410818×5909 828 \xrightarrow{\times 25} 20700 \rightarrow 27 \xrightarrow{\times 4} 108 \rightarrow 18 \xrightarrow{\times 5} 90 \rightarrow 9
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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.